平行機台顧客訂單最小化總完工時間及最大延 遲時間排程問題

Scheduling on parallel machines to minimize makespan and maximum lateness for the customer order problem

陳思吟(SSU-YIN CHEN)

指導教授 ： 蘇玲慧

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

https://doi.org/10.6840/cycu200900614

摘要

近年來由於消費需求型態的改變，企業面臨產品週期短且競爭激烈的環 境，有效率的生產排程不但可以提高工作效率、服務水準及市場之反應能力。 本研究計畫針對顧客訂單平行機台排程問題，探討使總完成時間及最大延遲時 間最小之顧客訂單平行機台排程問題。由於此問題是屬於NP-hard 問題，因此 本研究計畫目的在於發展多個快速有效率的啟發式演算法，計算這些啟發式方 法的最差狀態比值及進行模擬實驗，以提供學術界與產業界解決排程問題與供 應鏈管理的理論架構。

關鍵字

最差狀態比值 ； 最大延遲時間 ； 總完成時間 ； 顧客訂單 ； 平行機台排程

並列摘要

This research addresses customer orders scheduling problem on parallel
machines, where jobs are dispatched in batches. The objective is to minimize the
makespan and maximum lateness, designated as P | batch | Cmax and max P | batch | L ,
respectively. The problems we considered are NP-hard, therefore both heuristic and
optimal algorithms are provided. All heuristics based on simple scheduling rules, for
each problem are proposed and their tight worse case bounds are found. Some
empirical evaluations for the average-case performance of the heuristics are also
performed.

並列關鍵字

parallel machines ； customer order scheduling ； maximum lateness ； worst case ； makespan

參考文獻

[4] Garey M.R., and Johnson D.S., Computers and Intractability:A guide to the

[1] Blocher J.D., and Chhajed D., The customer order lead-time problem on

[2] Chu C., A branch and bound algorithm to minimize total weighted tardiness

[3] Du J., Leung J. Y.T., and Young G..H., Scheduling chain-structured tasks to

theory of NP-completeness., Freeman, New York., 1979.