The single-machine early-tardy Problem with Idle Time and Time Windows Permitted

允諾怠時狀況下具有時間視窗的單機E/T問題

陳肇業(Jaw-Yeh Chen)

《明新學報》 34卷2期 (2008/08) Pp. 1-19

https://doi.org/10.29688/MHJ.200808.0002

摘要

本文中所討論的是具有權值過早／過遲懲罰的單一機器排程問題，時間視窗是任意的，相鄰工件間也允許怠時存在，且工件的截止時間可能相異。利用優勢法則可以做出關係矩陣，此矩陣可以用來消去極大量的無效解。在結合了關係矩陣及跳躍策略之後，解決這個問題的程序也接著被提出來。

關鍵字

排程理論 ； 時間視窗 ； 過早／過遲 ； 怠時 ； 優勢法則

並列摘要

In this article, a single-machine weighted earliness and tardiness problem with arbitrary time windows is considered. Idle time between two adjacent jobs is permitted and the due dates of jobs may be unequal. The dominance rules can be utilized to develop a relationship matrix which allows the branching algorithm to eliminate a high percentage of nonfeasible solutions. After this matrix is combined with a branching strategy, a procedure which can solve the problem is proposed.

並列關鍵字

Scheduling theory ； Time window ； Earliness/Tardiness ； Idle time ； Dominance rule

參考文獻

Abdul-Razaq, T. S.,Potts, C. N.(1988).Dynamic programming state-space relaxation for single machine scheduling.Journal of the Operational Research Society.39,141-152.

Baker, K. R.,Scudder, G. D.(1990).Sequencing with earliness and tardiness penalties: a review.Operations Research.38,22-36.

Chen, J.-Y.,Lin, S.-F.(2002).Minimizing weighted earliness and tardiness penalties in single-machine scheduling problems with idle time permitted.Naval Research Logistics.49,760-780.

Davis, J. S.,Kanet, J. J.(1993).Single-machine scheduling with early and tardy completion costs.Naval Research Logistics.40,85-101.

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