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

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

10.29977/JCIIE.200411.0006

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

單機排程 ； 釋放時間 ； 啓發解 ； 淩越性質 ； 分枝界限法 ； Single machine scheduling ； Release times ； Heuristics ； Dominance property ； Branch and bound

工業工程學刊

21卷6期（2004 / 11 / 01）

567 - 575

英文

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

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.

1. 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.
2. Bianco, L.,S. Ricciardelli,G. Rinaldi,A. Sassano(1988).Scheduling tasks with sequence-dependent processing times.Naval Research Logistics Quarterly,35,177-184.
3. 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.
4. 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.
5. Chu, C.(1992).A branch-and-bound algorithm to minimize total flow time with unequal release dates.Naval Research Logistics Quarterly,39,859-875.
6. Della Croce, F.,V. T`kindt(2002).A recovering beam search algorithm for the one-machine dynamic total completion time scheduling problem.Journal of the Operational Research Society,53,1275-1280.
7. Deogun, J. S.(1983).On scheduling with ready times to minimize mean flow time.The Computer Journal,26,320-328.
8. Dessouky, M. I.,J. S. Deogun(1981).Sequencing jobs with unequal ready times to minimize mean flow time.SIAM Journal of Computing,10,192-202.
9. Hariri, A. M. A.,C. N. Potts(1983).An algorithm for single machine sequencing with release times to minimize total weighted completion time.Discrete Applied Mathematics,5,99-109.
10. Lawler, E. L.,J. K. Lenstra,A. H. G. Rinnooy Kan,D. B. Shmoys(1993).Sequencing and scheduling: Algorithms and complexity.Handbooks in Operations Research and Management Science, 4: Logistics of Production and Inventory.
11. Liu, J.,B. L. MacCarthy(1991).Effective heuristics for the single machine sequencing problem with ready times.International Journal of Production Research,29,1521-1533.
12. Posner, M. E.(1985).Minimizing weighted completion times with deadlines.Operations Research,33,562-574.
13. Reeves, C.(1995).Heuristics for scheduling a single machine subject to unequal job release times.European Journal of Operational Research,80,397-403.
14. Smith, W. E.(1956).Various optimizers for single-stage production.Naval Research Logistics Quarterly,3,59-66.
15. Süer G. A.,R. Vazquez,J. Santos(1999).Evolutionary programming for minimizing the average flow time in the presence of non-zero ready times.Proceedings of the 25th International Conference on Computers and Industrial Engineering.

1. (2011).Solving a multi-criteria group scheduling problem for a cellular manufacturing system by scatter search.工業工程學刊,28(3),192-205.