等效平行機台在機台限制且完工期限下總完工時間最小化排程問題

Scheduling on identical parallel machines to minimize total completion time with deadline constraint and machine eligibility

林正超(Cheng-Chao Lin)

指導教授 ： 蘇玲慧

中原大學/工學院/工業工程研究所/碩士(2007年)

https://doi.org/10.6840/cycu200700447

摘要

本研究針對等效平行機台(Identical Parallel Machine)之研究，工件在任一個機台上加工時間均為一致，但是某些工件只能在其機台限制（Machine Eligibility）上加工，工件需要在截止期限（Deadline）之前完成，目標為總完工時間（Total Completion Time）最小化。由於此問題為NP-hard，本研究對此問題擬提出有效的啟發式演算法，同時建立分支界限方法(Branch-and-Bound)，以驗證啟發式演算法之求解品質。
啟發式演算法利用SRPT-FM (Shortest Remaining Processing on Fastest Machine)和單一機台有截止期限最佳解法進行排列，針對執行時間短的工作 ，預先排入至機台上，預排所有工作，其最晚開始時間(Least Start Time)小於工作 的最晚開始時間(Least Start Time)，若有超過截止期限的工作將該工作進行與其他機台進行調換，或是將該機台上的其他工作與其他機台的工作進行交換測試，求得演算法的解為分支界限法之上限值；而分支界限法的下限值是將本研究轉換成線性規劃模式，並求得其對偶解，將此對偶解為分支界限法之下限值；最後結果本啟發式求解品質誤差都可以在1%以內。

關鍵字

截止期限 ； 等效平行機台 ； 機台限制 ； 總完工時間

並列摘要

This research considers the problem of scheduling identical parallel machine to minimizing total completion time with deadline constraint and machine eligibility. Jobs must complete its processing before or at its deadline and preemptions are not allowed. Every job is allowed to be processed on a specified subset of machines. The problem is strongly NP-hard for which the heuristic and the branch and bound are proposed. Some properties will be established and exploited to design the solution method of the heuristic and the branch and bound. And the computational results will be reported.

並列關鍵字

machine eligibility ； total completion time ； deadline ； identical parallel machine

參考文獻

Bagchi U. and Ahmadi, Reza H. 1986. An Improved Lower Bound For Minimizing Weighted Completion Times With Deadlines. Operations Research Society of America. Vol. 35,No. 2, 311-313.

Ching-Fang Liaw, Yang-Kuei Lin, Chun-Yuan Cheng, Mingchin Chen, 2003).Scheduling unrelated parallel machines to minimize total weighted tardiness. Computers and Operations Research 30, 1777-1789.

Garey, M.R. and Johnson, D.S. 1976. Scheduling Tasks with Nonuniform Deadlines on Two Processors. Journal of the Association for Computing Machinery , Vol. 23, No 3, 461-467.

Grissele C., Robert L. 2004. Armacost, Minimizing makespan on parallel machine with release time and machine eligibility restrictions. INT. J. PROD. RES. Vol. 42, No. 6, 1243-1256.

Pinedo, M., 1995., Scheduling Theory, Algorithms, and Systems (Englewood Cliffs: Prentice Hall.