有時間時窗限制與加權提早/延遲成本之單機排程研究

Single-Machine Scheduling with Time Windows and Weighted Earliness/Tardiness Penalties

陳立騫(Chen-Li Chien)

指導教授 ： 蘇玲慧

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

https://doi.org/10.6840/cycu200200423

摘要

本論文主要研究有時間時窗限制與加權提早/延遲成本之單機排程，當安排工作於其時間時窗內加工，無處罰成本產生，工作安排提早加工或延遲完工時，會產生其中一項加權處罰成本，而研究目標為總加權成本最小化。文中並指出本問題屬於NP-hard，因此所建立之數學規劃模式，需大量求解時間。針對此問題。首先我們提出五個在特定條件下決定加工次序之性質，並參考一針對SMET(Single Machine Earliness/Tardiness)問題所發展之演算法架構，提出啟發式排程演算法。我們也提出一程序，決定已知工作加工次序之工作開始加工時間。實驗測試後得知，啟發式演算法和最佳解比較之結果，其平均求解差異小於2.99%，較大工作數的情況，平均總加權成本低於API演算法4.106%。

關鍵字

單機 ； 時間時窗 ； 提早/延遲 ； 排程 ； 權重

並列摘要

This study deals with the single machine scheduling with time windows and weighted earliness/tardiness penalties problem. Jobs processed entirely within their respective windows incur no cost, otherwise the corresponding early or tardy cost incurred. This problem is proved to be NP-hard. An efficient heuristic and a mathematical programming model are presented. Several solution properties on which the heuristics and the mathematical programming models are based are developed. For small problem up to 12 jobs, the average deviation between the optimal and heuristic solution is less than 2.99%. Computational results show that the heuristic algorithm has an average error less than 2.99% when the number of jobs is small. For the larger problem, five heuristics based on API are proposed to find an approximate solution and are evaluated with the heuristic proposed in this paper. The results show that the proposed heuristic averages to 4.106% above the API heuristic.

並列關鍵字

Weighted ； Time windows ； Earliness/tardiness ； Single machine ； Scheduling

參考文獻

[1] Baker, K. R., and Scudder, G. D., “Sequencing with earliness and tardiness penalties: A review”, Operations Research 38 (1990) 22-36.

[2] Chen, Z.-L., and Lee, C.-Y., “Parallel machine scheduling with a common due window”, European Journal of Operational Research 136 (2002) 512-527.

[3] Garey, M. R., Tarjan, R. E., and Wilfong, G. T., “One-processor scheduling with symmetric earliness and tardiness penalties”, Mathematics of Operations Research 13 (1988) 330-348.

[4] Gabrel, V., “Scheduling jobs windows on identical parallel machine: New model and algorithms”, European Journal of Operational Research 83 (1995) 320-329.

[5] Kim, Y. D., and Yano, C. A., “Minimizing mean tardiness and earliness in single-machine problems with unequal due dates”, Naval Research Logistics 41 (1994) 913-933.