Heuristics for Minimizing Total Completion Time on Single Machine with Release Time


Article Preview

This paper focuses on the problem of scheduling n jobs with release dates on a single machine in order to minimize the total completion time. Since the problem has been characterized as strongly NP-hard, two heuristics (HR1 and AEO) were proposed for solving the problem in polynomial time. The heuristics were compared with the best approximation algorithm for this problem to date (Best-alpha). Experimental results show that AEO performed better than the Bestalpha algorithm (selected from the literature) when the number of jobs (n) exceeds 5. This observation should prove useful in the operational dispatch of jobs in industrial production settings as well as the service sector.



Advanced Materials Research (Volumes 18-19)

Edited by:

Prof. A.O. Akii Ibhadode




E. Oyetunji and A. E. Oluleye, "Heuristics for Minimizing Total Completion Time on Single Machine with Release Time ", Advanced Materials Research, Vols. 18-19, pp. 347-352, 2007

Online since:

June 2007




[1] A.E. Oluleye and E.O. Oyetunji: Performance of some static flowshop scheduling heuristics, Directions in Mathematics, (1999) pp.315-327.

[2] S. French: Sequencing and Scheduling (Ellis Horwood Limited 1982).

[3] J.A. Hoogeveen: Single-Machine Bicriteria Scheduling, PhD thesis, Technische Universiteit Eindhoven, The Netherlands (1992).

[4] J.A. Hoogeveen and S.L. Van de Velde: Minimizing Total Completion time and Maximum cost simultaneously is solvable in polynomial time, Operations Research Letters Vol. 17 (1995) , pp.205-208.

DOI: https://doi.org/10.1016/0167-6377(95)00023-d

[5] G.J. Kyparisis and C. Koulamas: Open shop scheduling with makespan and total completion time criteria, Computers and Operations research Vol. 27 (2000), pp.15-27.

DOI: https://doi.org/10.1016/s0305-0548(99)00005-2

[6] E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan and D.B. Shmoys: Sequencing and Scheduling: Algorithms and Complexity, In S.C. Graves et al., editor, Handbook in Operations research and management science, Vol. 4 (1993) , pp.445-522.

DOI: https://doi.org/10.1016/s0927-0507(05)80189-6

[7] D.S. Hochbaum: The Scheduling Problem, RIOT Web Page, Web address: http: /riot. ieor. berkeley. edu/riot/Applications/Scheduling/index. html, (1999).

[8] S. Chakrabarti, C.A. Phillips, A.S. Schulz, D.B. Shmoys, C. Stein and J. Wein: Improved scheduling algorithms for minsum criteria, In F. Meyer auf der Heide and B. Monien, editors, Automata, Languages and Programming, Lecture Notes in Computer Science 1099, Springer Proceedings of the 23rd International Colloquium (ICALP'96), Berlin, (1996).

DOI: https://doi.org/10.1007/3-540-61440-0_166

[9] C. Chekuri, R. Motwani, B. Natarajan and C. Stein: Approximation techniques for Average Completion Time Scheduling, SIAM Journal on Computing Vol. 31 (2001), pp.146-166.

DOI: https://doi.org/10.1137/s0097539797327180

[10] D. Karger, C. Stein, and J. Wein: Scheduling Algorithms, A chapter written for the CRC Handbook on Algorithms (Boca Raton 1997).

[11] C. Philips, C. Stein and J. Wein: Minimising Average Completion Time in the Presence of Release Dates, Mathematical Programming Vol 82 (1998), pp.199-223.

DOI: https://doi.org/10.1007/bf01585872

[12] M.X. Goemans, M. Queyranne, A.S. Schulz, M. Skutella and Y. Wang: Single Machine Scheduling with Release Dates, SIAM Journal on Discrete Mathematics Vol. 15 (2002), pp.65-192.

DOI: https://doi.org/10.1137/s089548019936223x

[13] J.A. Hoogeveen and A.P.A. Vestjens: Optimal on-line algorithms for single-machine scheduling, In proceedings 5 th International Conference Integer Programming and combinatorial optimization, LNCS, Springer, (1996) pp.404-414.

DOI: https://doi.org/10.1007/3-540-61310-2_30

[14] E. Torng P. Uthaisombut, SODA: ACM-SIAM Symposium on Discrete Algorithms (A Conference on Theoretical and Experimental Analysis of Discrete Algorithms), (1999).

[15] P. Uthaisombut: New Directions in Machine Scheduling, PhD thesis, Michigan State University, (2000).

[16] R.L. Graham, E.L. Lawler, J.K. Lenstra and A.H.G. Rinnooy Kan: Optimization and approximation in deterministic sequencing and scheduling: a survey, Ann. Discrete Math. Vol. 5 (1979), pp.287-326.

DOI: https://doi.org/10.1007/978-94-009-7801-0_3