考量不同情形之動態平行機排程

The study on dynamic parallel machine scheduling problems

白哲全(Che-Chuan Pai)

指導教授 ： 蘇玲慧

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

https://doi.org/10.6840/cycu200100181

摘要

本論文主要研究單製程具有平行機台之排程問題，針對機器、工作與操作員分三種不同特性之排程加以探討。在考量在製品（WIP）的產出時間（Throughput Time）與服務水準之下，各針對所有工作完成時間（Makespan）與總延遲時間（Total Tardiness）為績效指標，以符合實際生產環境的需求。
首先，研究平行機動態排程，考慮工作非一次全部到達，及機器可開始加工時間非同時，以所有工作完成時間最小化為評量指標。其次再延伸問題，考量交期限制下所有工作的總延遲時間最小化。最後，針對工作具可分割性與設置時間之平行機排程，將工作的設置時間與加工時間分開。探討每位操作員負責的機器間，加工的工作可進行分割，並以所有工作完成時間最小化為績效指標。
由於本研究之問題均屬NP-Hard，基於求解的效率，提出啟發式排程演算法並個別建立數學模式，以驗證各啟發式排程演算法所得結果的正確性，及作為評估求解品質成效的基準。

關鍵字

平行機排程 ； 設置時間 ； 總延遲時間 ； 總完成時間 ； 工作可分割

並列摘要

The research addresses the problem of dynamic parallel machine scheduling. Three different
models are considered according to machines,jobs and operators.
In the first case, we consider the dynamic parallel machines in a single stage with the objective of makespan minimization. The problem is extended to the objective with total tardiness minimization. Finally, we consider the problem for the case in which the job is preemptive within each operator, provided that the setup time is separated from the processing time.
All three problems are known to be NP-hard even for the case of two identical parallel machines. An integer programming model and a heuristic algorithm are provided for each case. Experimental results show that the proposed heuristic algorithms are effective and efficient.

並列關鍵字

parallel machine scheduling ； makespan ； setup time ； total tardiness ； preemptive jobs

參考文獻

1. Alidaee, B., and D. Rosa, “Scheduling parallel machines to minimize total weighted and unweighted tardiness,” Computers Ops Res., 24(8), 775-788(1997).

2. Alidaee, B., and S. Gopalan, “A note on the equivalence of two heuristics to minimize total tardiness,” European Journal of Operational Research, 96, 514-517(1997).

3. Arkin, E. M., and R. O. Roundy, “Weighted-Tardiness scheduling on parallel machines with proportional weights,” Operations Research, 39(1), 64-81(1991).

4. Azizoglu, M., and O. Kirca, “Tardiness minimization on parallel machines,” Int. J. Production Economics, 55, 163-168(1998).

5. Azizoğlu, M., S. Kondakci and Ö. Kirca, “Bicriteria scheduling problem involving total tardiness and total earliness penalties,” International Journal of Production Economics, 23, 17-24(1991).