最小化總絕對完工時間差異之穩健單機排程

Robust Single Machine Scheduling to Minimize Total Absolute Difference in Completion Time

邱鵬憲(Peng-Hsien Chiu)

指導教授 ： 應國卿

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

摘要

在現實環境中為簡化求解問題的複雜度，管理者常以某一確定數值來決定每項工作的最佳加工順序，然而，現實生產環境中常面臨處理時間不確定的狀況，導致在確定性數值下所獲得的排序其實際的求解績效與最佳解相差甚遠，所以如何在處理時間具有不確定性的情況下進行工作的排序，成為排程理論與實務上的一個重要研究課題。
本研究主要在探討處理時間具有不確定性情況下的穩健單機排程問題(Robust Single Machine Scheduling Problem; RSMSP)，其目標函數為最小化總絕對完工時間差異(Total Absolute Difference in Completion Time; TADC)，本研究首先產生n=10,20,30,50,100,150,200七種不同大小工件數問題各30題共210組問題，再使用完全列舉法來求解n=10,20,30三種問題，再以成對交換法及模擬退火法(Simulated Annealing)來求解RSMSP，在n=10,20,30中與完全列舉法作比較來驗證是否可得到最佳解，最後求解完全列舉法無法求解之問題n=50,100,150,200，來比較二者演算法之求解效率，預期本研究的結果將能提出有效求解RSMSP最佳化的生產排程模式，以奠定相關排程理論的基礎。

關鍵字

穩健排程 ； 單機排程 ； 最小化總絕對完工時間差異

並列摘要

This study deals with the single machine scheduling problem (SMSP) with uncertain job processing times. The objective is to obtain robust job sequences with minimum worst-case total absolute difference in completion times among a set of possible scenarios. Rather than using probability distributions to model uncertain processing times, we described the processing time uncertainty with intervals, and incorporated a budget parameter to control the degree of conservatism, similar to the robust counterpart optimization approach proposed in the literature. Furthermore, a revision of the uncertainty set was proposed to address correlated uncertain processing times due to a number of common sources of uncertainty. We showed that the problem of determining worst-case total absolute difference in completion times can be reformulated as a linear program, and presented an efficient way of obtaining its solution. Simulated annealing (SA)-based algorithmic framework and paired exchange heuristic were developed to solve the robust single machine scheduling problem (RSMSP) problem of interest. Experimental results demonstrate that the proposed SA-based heuristic and paired exchange heuristic are effective and efficient in solving RSMSP with practical problem sizes. Simulation results indicate that the robust sequences outperform the optimal nominal sequences under different protection levels. Also shown in the numerical example is that the proposed approach allows the tradeoff between robustness and optimality.

並列關鍵字

Robust ； Single machine ； Total Absolute Difference in Completion Time(TADC)

參考文獻

[1] Allahverdi A. and J. Mittenthal, "Scheduling on M parallel machines subject to random breakdowns to minimize expected mean flow time," Naval Research Logistics, vol. 41, 1994, pp. 677-682.

[2] Boaz R. and M. K. Starr, "Synchonized manufacturing as in OPT: from practice to theory," Computers and Industrial Engineering, vol. 18, no. 4, 1990, pp. 585-600.

[3] Ben-Tal A. and Nemirovski, A., "Robust convex optimization," Mathematical Operations Research 23, 1998, pp. 769–805.

[4] Ben-Tal A. and Nemirovski, A., "Robust solutions to uncertain linear programs," Operations Research Letters 25, 1999, pp. 1–13.

[5] Ben-Tal A. and Nemirovski A., "Robust solutions of linear programming problems contaminated with uncertain data," Mathematical Programming vol. 88, 2000, pp. 411–424.