現在位置首頁 > 博碩士論文 > 詳目
論文中文名稱:用最大後悔值最小化求解生產排程問題 [以論文名稱查詢館藏系統]
論文英文名稱:Min-max Regret Optimization for Production Scheduling Problem [以論文名稱查詢館藏系統]
院校名稱:臺北科技大學
學院名稱:管理學院
系所名稱:資訊與運籌管理研究所
畢業學年度:99
出版年度:100
中文姓名:李昭慶
英文姓名:Cha-Hsing Lee
研究生學號:98938006
學位類別:碩士
語文別:中文
口試日期:2011-06-27
論文頁數:37
指導教授中文名:吳建文
指導教授英文名:Chien-wen Wu
口試委員中文名:陳鵬文;羅淑娟
中文關鍵詞:穩健排程穩健指派後悔值穩健多機排程ILS
英文關鍵詞:Robust scheduling ProblemRobust Assignment ProblemRegretRPMSPILS
論文中文摘要:本研究的問題是研究多台平行機器排程問題(Parallel Machines Scheduling Problem)的最大後悔值最小化,並使求出的解的後悔值為最小。在現實世界中,舉凡工作的優先權、工作的執行時間、機器的老舊程度、工人的技術和經驗等等,都會影響排程的情形。但這些資料(或是參數)很難預先得知其精確值。本研究針對此一困難,使用穩健最佳化的概念來解決現實生活中不確定性資料的問題。
本研究在分析此排程問題之後,發現可以將最大後悔值最小化的多台平行機器排程問題轉型為P||ΣC的指派問題,因此本研究將利用穩健指派問題的定義及Kasperski 提出的混合整數規劃模型來求解。本研究希望能使排程問題的求解模式更貼近現實面,對於生產排程決策能有所助益。
論文英文摘要:This paper deals with the Min-max Regret optimization for Production scheduling problem. We deal with the Robust Parallel Machines Scheduling Problem. The objective is to obtain robust job scheduling with minimum maximal regret. Several factors in the real-world affects the production schedule, like priority, processing time, machines condition, workers’ skill and experience etc. However, the exact values of these data can not be known precisely in advance. The goal of this thesis is to handle imprecise input data and minimize the maximal regret for scheduling with more than one processor.
We found this problem can be transformed into the P||ΣC assignment problem. Therefore, we introduce the Mixed Integer Programming model for the robust assignment problem from Adam Kasperski. We wish that the result can help managers on production scheduling to make better decisions.
論文目次:摘要 I
目錄 IV
表目錄 V
圖目錄 VI
第一章 緒論 1
1.1 研究背景與動機 1
1.2 研究目的 2
1.3研究基本假設 3
1.4 研究流程 4
第二章 文獻探討 6
2.1 排程問題之定義與描述 6
2.2 排程問題的參數研究 7
2.3 穩健排程 8
2.4 穩健指派 9
2.5 重複性區域搜尋演算法 11
2.6 End-Point演算法 15
第三章 問題描述分析與研究方法 17
3.1 問題描述 17
3.2 問題分析 17
3.3 數學模型 19
3.4 研究方法 22
3.4.1 限制規則 22
3.4.2 End-Point演算法 23
3.4.2.1 End-Point的說明與證明 23
3.4.2.2 End-Point Sum演算法 25
3.4.3 重複性區域搜尋演算法 26
3.4.3.1 演算法流程 26
第四章 實驗結果 28
4.1 實驗設計 28
4.2 實驗結果 28
第五章 結論與未來發展 32
5.1結論與貢獻 32
5.2未來研究發展 32
參考文獻 34
論文參考文獻:[1] Adam Kasperski, “Minmax Regret Minimum Assignment”, Fuzziness and Soft Computing, 2008, Volume 228/2008, 113-120.
[2] Adam Kasperski, “Sequencing Problem with the Total Flow Time Criterion”, Fuzziness and Soft Computing, 2008, Volume 228/2008, 183-195, DOI: 10.1007/978-3-540-78484-5_15.
[3] A. Kasperski, P. Zielin'ski, “An approximation algorithm for interval data minmax regret combinatorial optimization problems”, Information Processing Letters Volume 97, Issue 5, 2006, pp. 177-180.
[4] A. Kasperski, P. Zielin'ski, “Minimizing maximal regret in linear assignment problems with interval data”, Instytut Matematyki PWr., Wroclaw 2004, Raport serii PREPRINTY nr. 007.
[5] A. J. Hoffman1, H. M. Markowitz, “A note on shortest path, assignment, and transportation problems”, Naval Research Logistics Quarterly Vol. 10, Issue 1, 1963, pp. 375–379.
[6] Al-Fawzan, M. A. & Haouari M., “A Bi-objective Model for Robust Resource-constrained Project Scheduling”, International Journal of Production Economics, Vol. 96, 2005, pp. 175-187.
[7] Allahverdi A and J. Mittenthal, “Scheduling on M parallel machines subject6 to random breakdowns to minimize expected mean flow time”, Naval Research Logistics, vol. 41, 1994, pp. 677-682.
[8] Bagchi U. et al., “Minimizing mean absolute deviation of completion times about a common due date,” Nav. Res. Log. Qrr. Vol. 33, 1986, pp. 221-240.
[9] Ben-Tal A. and Nemirovski, A., “Robust convex optimization”, Mathematical Operations Research 23, 1998, pp. 769-805.
[10] Ben-Tal A. and Nemirovski, A., “Robust solutions to uncertain linear programs”, Operations Research Letters 25, 1999, pp. 1-13.
[11] Bertsimas D. and Sim M., “Robust discrete optimization and network flows”, Mathematical Programming, vol. 98, 2003, pp. 49-71.
[12] Bertsimas D. and Sim M., “The price of robustness”, Operations Research, vol. 52, no. 1, 2, 2004, pp. 35-53.
[13] Bowers, J. A., “Interpreting Float in Resource Constrained Projects”, International Journal of Project Management, Vol. 18,10, 2000, pp. 385-392.
[14] Byeon E.-S., Wu S.D. and Storer R.H., “Decomposition heuristics for robust job-shop scheduling”, IEEE Transactions on Robotics and Automation, vol. 14, no. 2,4, 1998, pp. 113-124.
[15] Cheng T. C. E. and Cai X. “On the complexity of completion time variance minimization problem, “ Asia-Pacific Journal of Operation Res. Vol. 10, 1992, pp.109-120.
[16] Dooley J. K. and and Mahmoodi F., “Identification of robust scheduling heuristic: application of Taguchi methods in simulation studies”, Computers and Industrial Engineering, vol. 22, no. 4, 1992, pp. 59-36.
[17] Framinan JM, Leisten R. An efficient constructive heuristic for flowtime
minimisation in permutation flow shops. OMEGA 2003;31:311-7.
[18] Gur Mosheiov *, “Simultaneous minimization of total completion time and total deviation of job completion times”, European Journal of Operational Research 157 (2004) 296–306.
[19] H.W. Kuhn, The Hungarian Method for the assignment problem, Naval Research
Logistic Quarterly, 2 (1955) 83-97.
[20] Hassene Aissi, Cristina Bazgan, and Daniel Vanderpooten, “Complexity of the min–max and min–max regret assignment problems”, Operations Research Letters Vo. 33, Issue 6, 2005, pp. 634-640
[21] I. Averbakh, V. Lebedev, Interval data minmax regret network optimization problems, Discrete Appl. Math. 138 (2004) 289–301.
[22] Jensen, M.T., “Generating robust and flexible job shops schedules using genetic algorithms”, IEEE Transactions on Evolutionary Computation, 6, 2003, pp. 275-288.
[23] Jordi Pereira & Igor Averbakh, “Exact and heuristic algorithms for the interval data robust assignment problem”, Computers & Operation Research, vol. 38, Issue 8, 8, 2011, pp.1153-1163.
[24] Leon V.J., Wu S.D. and Storer, R.H. “Robustness Measures and robust scheduling for job shops”, IEE Trans, vol. 26, no. 5, 1994, pp 32-43.
[25] Laurent El Ghaouiy, Francois Oustryy, and Herve Lebret, “Robust Solutions To Uncertain Semidefinite Programs”, Journal SIAM Journal on Optimization archive Vol. 9 ,No. 1, 1998, pp. 33-52.
[26] Liu JY, Reeves CR. Constructive and composite heuristic solutions to the P//ΣCi scheduling problem. European Journal of Operational Research 2001;132: 439-52.
[27] Mehta S.V. and Uzsoy R.M., “Predictable Scheduling of Job Shop Subjects to Breakdowns”, IEEE Transactions on Robotics and Automation, vol. 47, no. 1, 1998, pp. 365-37.
[28] Mohring, R. H., F. J. Radermacher, and G. Weiss, "Stochastic Sched- uling Problems I: General Strategies," Zeitsch?rift fur Oper. Res., 28 (1984), 193-260.
[29] Pinedo, M. L. and L. Schrage, “Stochastic Shop Scheduling: A Survey,” In M. A. H. Dempster, J. K. Lenstra, and A. H. G. Rinnooy Kan (Eds.), Deterministic a nd Stochastic Scheduling Reidel, Dordrecht, 1982.
[30] R. Montemanni, L.M. Gambardella, A.V. Donati, “A branch and bound algorithm for the robust shortest path problem with interval data”, Operations Research Letters 32 (2004) 225 – 232.
[31] Rajendran C, Chaudhuri D. “ A flowshop scheduling algorithm to minimize total
Flowtime”. Journal of the Operations Research Society of Japan 1991;34:28-45.
[32] Rajendran C, Chaudhuri D. “ An efficient heuristic approach to the scheduling of
jobs in a flowshop.” European Journal of Operational Research 1992;61:318-25.
[33] Rajendran C, Ziegler H. “ An efficient heuristic for scheduling in a flowshop to
minimize total weighted flowtime of jobs.” European Journal of Operational
Research 1997;103:129-38.
[34] Rajendran C. “Heuristic algorithm for scheduling in a flowshop to minimize total
flowtime.” International Journal of Production Economics 1993;29:65-73.
[35] Rajendran C, Ziegler H. Ant-colony algorithms for permutation flowshop
scheduling to minimize makespan/total flowtime of jobs. European Journal of
Operational Research 2004;155:426-38.
[36] Rajendran C, Ziegler H. Two ant-colony algorithms for minimizing total flowtime in permutation flowshops. Computers and Industrial Engineering 2005;48: 789-97.
[37] Richard L. Daniels and Panagiotis Kouvelis, “Robust Scheduling to Hedge
Against Processing Time Uncertainty in Single-stage Production”, Management Science, Vol. 41, No. 2 (Feb., 1995), pp. 363-376.
[38] Sevaux, M and Sorensen K., “A generic algorithm for robust schedules”, Paper presented at the 8th International Workshop on Project Management and Scheduling, Valencia, April 3-5, 2002.
[39] Shafaei R. and Brunn P., “Workshop scheduling using practical(inaccurate) data-Part2: An investigation of the robustness of the scheduling rules in a dynamic and stochastic environment”, International Journal of Production Research, vol. 4, 2002, pp 707-712.
[40] Sorensen K. “Tabu searching for robust solutions”, Metaheuristics International Conference, vol. 4, 2002, pp 707-712.
[41] Soyster A. L., “Convex programing with set-inclusive constrains and applications to inexact linear programing”, Operations Research 21, 1973, pp. 1154-1157.
[42] Stephen C. Graves “A Review of Production Scheduling”, Operations Research Vol. 29, No. 4, 1981, pp. 646-675.
[43] Stevenson W J., “Operation management”, McGraw-Hill Education, Seventh Edition, 2002.
[44] Tasgetiren MF, Liang Y-C, Sevkli M, Gencyilmaz G. A particle swarm optimization algorithm for makespan and total flowtime minimization in the permutation flowshop sequencing problem. European Journal of Operational Research 2007;177:1930-47.
[45] Velagapudi, K.N., “Robust Schedule for Manufacturing Systems”, Computers and Industrial Engineering, vol. 23, 1992, pp. 133-136.
[46] Wang, J., “Constraint-based Schedule Repair for Product Development Projects with Time-limited Constraints”, International Journal of Production Economics, Vol. 95, 2005, pp. 399-414.
[47] Widmer, M. & Hertz, A., “A New Heuristic Method for the Flow Shop Sequencing Problem”, European Journal of Operational Research, Vol. 41, 1989, pp.186-193.
[48] Wu S.D., Byeon E.-S. and Storer R.H., “A graoh-theoretic decomposition of the job shop scheduling problem to achieve scheduling robustness”, Operations Research, vol. 47, no. 1, 1999, pp.113-124.
[49] X.G. Dong, H.K. Huang and P. Chen, “An iterated local search algorithm for the permutation flowshop problem with total flowtime criterion”, Coputers & Operations Research, vol. 36, 2009, pp. 1664-1669.
[50] 王培珍,應用遺傳演算法與模擬在動態排程問題之探討,碩士論文,中原大學工業工程研究所,桃園,1995。
[51] 潘國丞,多目標平行機台零工式工廠重排程研究之探討,碩士論文,東海大學工業工程與經營資訊研究所,台中,2006。
[52] 羅國弘,生產排程的工作完成時間變異最小化之排程研究,碩士論文,逢甲大學統計與精算研究所,台中,1999。
[53] 邱鵬憲,最小化總絕對完工時間差異之穩健單機排程,碩士論文,國立台北科技大學工業工程與管理研究所,台北,2010。
[54] 林宇璠,物流中心訂單排序問題之研究,碩士論文,國立台北科技大學工業工程與管理研究所,台北,2010。
論文全文使用權限:不同意授權