多階段不等效平行機之排程研究

The Study on Multi-stage Non-Identical Parallel Machine Scheduling Problem

張毓仁(Yu-Jeng Chang)

指導教授 ： 蘇玲慧

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

https://doi.org/10.6840/cycu200100452

摘要

本論文主要研究多階段不等效平行機排程問題，針對所有工作在某些製程可選擇自製或外包機器加工的情況，在有交期時間的限制下，所產生的延遲懲罰成本與外包成本，將所此兩種成本總合視為總成本。而研究目標乃是最小化總成本。
首先，研究在某些製程方面，工作可選擇在自製或外包機器上加工，而在考慮各工作的延遲懲罰成本與具有不同外包情形下的成本下，如何對各工作加以排序，最後以在所有工作完成時的總成本最小化為績效指標。
由於本論文研究之問題屬於NP-Hard，基於求解效率，將提出啟發式演算法並建立數學規劃模式，以作為評估求解品質成效的基準。由實驗結果分析得知，第四個啟發式演算法能夠有效的求取排程順序解。

關鍵字

權重 ； 成本 ； 多階段 ； 排程 ； 不等效平行機

並列摘要

This paper addresses the multi-stage non-identical parallel machines scheduling problem. In some stages, there are two kinds of machines. One is out-sourcing and the other is self-manufactured.
Jobs are processed by out-sourcing or self-manufactured in some stages. The performance measure is the minimization of total cost, including the out-sourcing cost and the weighted tardiness cost.
This problem is known to be NP-hard, four heuristic algorithms are provided and an integer programming model is presented for benchmarking. Experimental results show that the proposed fourth heuristic algorithm is effective and efficient.

並列關鍵字

cost ； weight ； scheduling ； multi-stage ； non-identical parallel machine

參考文獻

1. Adamopoulos,G.I.,and C.P.Pappis,(1996)Scheduling with different, job- dependent earliness and tardiness penalties using the SLK method, European Journal of Operational Research,88,336-344.

2. Avraham,S.,（1997）Project segementation-a tool for project management,International Journal of Project Management, 15(1), 15-19.

3. Azizoglu,M., S.Kondakci and Ő.Kirca,(1991)Bicriteria scheduling problem involving total tardiness and total earliness penalties, International Journal of Production Economics,23,17-24.

4. Bertraand,J.W.M.,(1983)The effect of workload dependent due-dates on job shop performance,Management Science,29(7),799-816.

5. Chang,F.C.R.,（1996）A study of due-date assignment rules with constrained tightness in a dynamic job shop, Computer industrial Engineering 31,205-208.