平均遲誤時間最小化之穩健單機排程

Robust Single Machine Scheduling to Minimize Mean Tardiness

戚仁傑(Ren-Jie Chi)

指導教授 ： 應國卿

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

摘要

生產排程問題在生產管理是個相當重要的課題，大部分現實環境中的排程與排程理論通常有很大的落差，最主要的原因在於現實環境中的不確定性因素。本研究主要探討加工時間不確定下，平均遲誤時間最小化之單機穩健排程。利用Bertsimas與Sim (2004)提出的穩健對應最佳化模式（robust counterpart optimization；RCO），建構本研究之MILP模型。本研究實驗部份，使用前推排程法（Forward Scheduling；FS）與反覆貪婪演算法(Iterated Greedy Algorithm;IG)結合穩健排程，運用程式撰寫執行，並以不同工件數，分別設定小型與大型兩種問題，經由所得數據做分析與檢定兩種方法之間的差異。結果顯示，在小型問題中，前推排程法與反覆貪婪演算法都與最佳解近乎一致，且時間迅速。隨著工單數增加，反覆貪婪演算法與前推排程所求得解也都相差不大，但在求解時間上，反覆貪婪演算法之求解效率極高，所以在不確定性問題中，利用穩健排程方法來做排程規劃，不但可使解的品質穩定，且不需耗費太多時間，值得日後繼續研究，應用在生產排程之領域。

關鍵字

單機穩健排程 ； 不確定性 ； 平均遲誤時間 ； 反覆貪婪演算法

並列摘要

Production scheduling problems is a very important topic in production management. Most of the reality of scheduling is difference to scheduling theory, because real-world manufacturing usually operate in highly uncertain environments. 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 mean tardiness among a set of possible scenarios. We proposed a RCO formulation based on the idea of Bertsimas and Sim, and this RCO formulation can be reformulated as a mixed integer linear (MILP) program.The experiment of this study using the Forward Scheduling(FS) and Iterated Iterated Greedy Algorithm(IG) combined with robust scheduling, coding and implementation. We divide the number of the jobs into two different size problems of small size and large size. Furthermore, we analysis and test the experiment by FS and IG obtain the data. Experimental results demonstrate that the solutions of using FS and IG are approximately consistent with the optimal solution and very light computational efforts in small-sized problems. With the increase in the number of jobs, that the solution obtained with FS and IG is small gap, but it’s efficient in solving with IG. in the computation time. Therefore, using robustness to do scheduling not only steady the quality of the solution but also requires light computation time within the uncertainty problems. Should be continued research in future and application to production scheduling.

並列關鍵字

robust scheduling ； uncertainty ； mean tardiness ； iterated greedy.

參考文獻

[1] T. S. Abdul-Razaq, C. N. Potts, L. N. Van Wassenhove, "A survey of algorithms for the single machine total weighted tardiness problem," Discrete Applied Mathematics, 26, 1990, pp. 235-253.

[2] T. D. Fry, L. Vicens, K. Macleod and S. Fernandez, "A Heuristic Solution Procedure to Minimize on a Single Machine," The Journal of the Operational Research Society, vol. 40, no. 3, 1989, pp. 293-297.

[4] L. J. Wilkerson and J. D. Irwin, "An improved method for scheduling independent tasks," AIIE Transactions, vol. 3, 1971, pp. 239-245.

[5] J. E. Holsenback and R. M. Russell, "A heuristic algorithm for sequencing on one machine to minimize total tardiness," Journal of the Operational Research Society, vol. 43, 1992, pp. 53-62.

[6] M. Ben-Daya, S. O. Duffuaa and A. Raouf, "Minimizing mean tardiness to unspecified minimum number of tardy jobs," European Journal of Operational Research, 89, 1996, pp. 100-107.