考量有設置時間及交期最小化最大延遲時間之雙機平行機台且具單一操作員排程問題

Parallel machine scheduling with setup time and due date to minimize lateness time in a single server

陳彥斌(Yan-Bin Chen)

指導教授 ： 蘇玲慧

中原大學/電機資訊學院/工業與系統工程研究所/碩士(2013年)

https://doi.org/10.6840/cycu201300863

摘要

本研究探討雙機等效平行機台(Two Identical Parallel Machine)之排程問題，考慮有 個獨立工件在兩台機台上進行加工，考慮只有單一操作人員且工件具有整備時間及交貨時間之限制條件下，以最大延遲時間最小化為目標，數學表達形式為 。
在考慮工件具有交替的排序之下，提出一個整數規劃模式求最佳解，並利用EDD(Earliest Due Date)與SST(Smallest Slack Time)兩個演算法則與其比較，並探討兩個演算法與最佳解之求解誤差，找出適合兩個演算法的求解環境。本研究之實驗結果顯示在不同的工作數之下，兩個演算法與數學規劃模式之平均誤差在交貨時間落於兩組因子組合之下，求解誤差為最小，若考慮求解速率下我們可以說這兩個演算法在這兩組交貨時間範圍是適用的。

關鍵字

整備時間 ； 最大延遲時間 ； 單一操作人員 ； 等效平行機台

並列摘要

In this work studies we consider the problem of scheduling n jobs on two identical parallel machines with a single server and jobs have setup time and due date. Our objective is to minimize maximum lateness and problem is denoted as .
Consider the jobs are processed alternately on the machines, we developed a integer programming model to compute this scheduling problem, and to used Earliest Due Date and Smallest Slack Time two rules to compare result, and to discuss two algorithms’ solved error, find the appropriate two algorithms solving environment. In the experimental results we known that the two algorithms for solving the error under the two groups of the experimental factor with due date range, the errors are the smallest, so if we consider execution time we can say that these two algorithms in these two groups of factor with due date range is applicable.

並列關鍵字

identical parallel machine ； a single server ； maximum lateness ； due date ； setup time

參考文獻

Abdekhodaee, A. H., Wirth, A. (2002).“Scheduling parallel machines with a single server: some solvable cases and heuristics.”, Computers and Operations Research 29, 295-315.

Brucker, P., Knust, S., Wang, G. (2005).“Complexity results for flow-shop problems with a single server.”, European Journal of Operational Research 165, 398-407.

Cheng, T. C. E., Wang, G., Sriskandarajah, C. (1999).“One-operator–two-machine flowshop scheduling with setup and dismounting times.”, Computers and Operations Research 26, 715-730.

Eren, T. (2009).“A note on minimizing maximum lateness in an m-machine scheduling problem with a learning effect.”, Applied Mathematical Modelling 209, 186-190.

Gacias, B., Artigues, C., Lopez, P. (2010).“Parallel machine scheduling with precedence constraints and setup times.”, Computers and Operations Research 37, 2141-2151.