最小化總完工時間之穩健雙機排程模式

Robust Two-machine Flow Shop Scheduling Model for Minimizing Makespan

江崇宇(Chong-Yu Jiang)

指導教授 ： 應國卿

國立臺北科技大學/管理學院/工業工程與管理研究所/碩士(2011年)

摘要

在實務上，通常生產作業都存在高度的不確定性因素，若未將這些不確定性因素考慮至排程作業中，常會導致生產排程的績效不佳。回顧過去文獻，加工時間具有不確定性的單機排程問題較常被討論。因此，本研究探討雙機排程問題，加工時間具有不確定性，以最小化總完工時間為績效指標。利用Bertsimas與Sim [30]在2004年提出的穩健對應最佳化模式(Robust Counterpart Optimization)，建構本研究的穩健雙機排程問題(Robust Two-machine Scheduling Problems)。並且利用完全列舉法(Enumeration)來驗證模擬退火法(Simulated Annealing; SA)以及反覆貪婪(Iterated greedy; IG)演算法在求解穩健排程中彼此之績效。在實驗設計則以工件數大小區分為小型問題以及大型問題， 為小型問題， 則規類為大型問題。實驗結果顯示在小型問題中，SA與IG有相同的求解效果，並且當 下，完全列舉法、SA與IG不超過0.1秒就可求出最佳解。在大型問題中，IG的求解效果較SA佳，但所需的計算時間卻遠大於SA。

關鍵字

不確定性 ； 穩健雙機排程問題 ； 穩健對應最佳化 ； 模擬退火法 ； 反覆貪婪演算法

並列摘要

Real-world manufacturing systems usually operate in highly uncertain environments in which production schedules can not be executed exactly. Review of the literature, most of studies with respect to robust scheduling founded on single-machine scheduling problem with uncertain job processing times. Therefore, this study dealt with the two-machine flow shop scheduling problem (TMSP) with uncertain job processing times. The objective is to obtain a robust sequence with minimum worst-case total absolute difference in makespan among a set of possible scenarios. We used Robust Counterpart Optimization (RCO) method to reformulate the TMSP and solved it by a simulated annealing SA-based heuristic and IG algorithm. Numerical experiments demonstrated the SA-based heuristic and IG algorithm had the same effective in determining robust schedules that only need 0.1 second on small size problems. On the large size problems, IG is more effective than SA, while needs more computational time.

並列關鍵字

uncertain ； Robust Two Machine Scheduling Problems ； Robust Counterpart Optimization ； Simulated Annealing ； Iterated greedy algorithm.

參考文獻

[2] S. M. Johnson, "Optimal two-and three-stage production schedules with set-up time included," Naval Research Logistics Quarterly, vol. 1, 1956, pp. 61–68.

[3] R. L. Graham, E. L. Lawler, J. K. Lenstra and A. H. G. Rinnooy Kan, "Optimization and approximation in deterministic sequencing and scheduling: a survey, "Annals of Discrete Mathematics, vol. 5, 1979, pp. 287–326.

[4] M. R. Garey, D. S. Johnson and Ravi Sethi, "The Complexity Flowshop and Jobshop Scheduling," Mathematics of Operations Research, vol. 1, 1976, pp. 117–129.

[5] R. A. Dudck, S. S. Panwalker and M. L. Smith, "The Lessons of Flowshop Scheduling Research," Operational Research, vol. 40, 1992, pp. 7–13.

[7] G. B. Dantzig, "Linear Programming Under Uncertainty,"Management Science, vol. 1, 1955, pp. 197–206.