On Single-Machine Scheduling with Release Times to Minimize Total Weighted Completion Time

加權完工時間最小化之動態排程問題

張百棧(Pei-Chann Chang) ； 鍾雲恭(Yun-Kung Chung)

《工業工程學刊》 21卷6期 (2004/11) Pp. 567-575

https://doi.org/10.29977/JCIIE.200411.0006

摘要

在本研究中我們考虑動態的單機排程問題，目標是將加權完工時間最小化，在文章中提出了兩個應用決策指標決定排程順序的啓發式方法，第一個啓發式方法將目標函數重新安排，而第二個啓發式方法則利用分割的程序以産生較佳的下界。同時，也提出了一個淩越法則以增加演算的效率。實驗指出本研究所提出的兩個啓發式方法解可以在短時間內得到品質相當不錯的解。

關鍵字

單機排程 ； 釋放時間 ； 啓發解 ； 淩越性質 ； 分枝界限法

並列摘要

In this sstudy, we considered a single-machine scheduling problem with release times and the objective is to minimize the total weighted completion time. Two new heuristics were proposed with the use of decision indexes that assign the priorities to jobs in the sequence. The former decision index is based on the rearrangement of the objective function whereas the latter is based on a decomposition procedure to generate a better lower bound. A dominance rule was also developed to eliminate the node in which its partially scheduled sequence is dominated by a simple heuristic developed in this study. Experimental results showed that both heuristics yielded near-optimal solutions in a very short time.

並列關鍵字

Single machine scheduling ； Release times ； Heuristics ； Dominance property ； Branch and bound

參考文獻

Bianco, L.,S. Ricciardelli(1982).Scheduling of a single machine to minimize total weighted completion time subject to release dates.Naval Research Logistics Quarterly.29,151-167.

Bianco, L.,S. Ricciardelli,G. Rinaldi,A. Sassano(1988).Scheduling tasks with sequence-dependent processing times.Naval Research Logistics Quarterly.35,177-184.

Chand, S.,R. Traub,R. Uzsoy(1996).An iterative heuristic for the single machine dynamic total completion time scheduling problem.Computers and Operations Research.23,641-651.

Chand, S.,R. Traub,R. Uzsoy(1996).Single-machine scheduling with dynamic arrivals: Decomposition results and an improved algorithm.Naval Research Logistic Quarterly.43,709-719.

Chu, C.(1992).A branch-and-bound algorithm to minimize total flow time with unequal release dates.Naval Research Logistics Quarterly.39,859-875.