Paper Titles
Recombination Parameters Determination by Using Internal Quantum Efficiency (IQE) Data of Bifacial Silicon Solar Cells
p.313
Potential of Nightsky Nocturnal Radiative Cooling as a Fresh Produce Preservation Method
p.325
Potentials of Passive Solar Design in Energy Conservation in Buildings in the Warm Humid Climate
p.331
Solar Tracker Technologies: Market Trends and Field Applications
p.339
Heuristics for Minimizing Total Completion Time on Single Machine with Release Time
p.347
Computer Aided Construction, Evaluation and Improvement of a Workplace Assembly Layout Using CADWORK
p.353
Enterprise Modelling in Support of the Application of Lean Manufacturing in SMEs
p.359
Developing the Niger Delta Transport System Using Adequate Geo-Spatial Information
p.365
Intervention Analysis of Road Traffic Accidents in Nigeria
p.375

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

Article Preview

Abstract:

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.

You might also be interested in these eBooks
Advances in Materials and Systems Technologies View Preview

Info:

Periodical:

Advanced Materials Research (Volumes 18-19)

Pages:

347-352

DOI:

https://doi.org/10.4028/www.scientific.net/AMR.18-19.347

Citation:

Cite this paper

Online since:

June 2007

Authors:

Elkanah Oyetunji, Ayodeji Emmanuel Oluleye

Keywords:

Heuristic, Objective Measure, Release Dates, Scheduling, Total Completion Time

Export:

RIS, BibTeX

Price:

Permissions CCC:

Request Permissions

Permissions PLS:

Request Permissions

Сopyright:

© 2007 Trans Tech Publications Ltd. All Rights Reserved

Share:

Citation:

References

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

Google Scholar

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

Google Scholar

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

Google Scholar

[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: 10.1016/0167-6377(95)00023-d

Google Scholar

[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: 10.1016/s0305-0548(99)00005-2

Google Scholar

[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: 10.1016/s0927-0507(05)80189-6

Google Scholar

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

Google Scholar

[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: 10.1007/3-540-61440-0_166

Google Scholar

[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: 10.1137/s0097539797327180

Google Scholar

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

Google Scholar

[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: 10.1007/bf01585872

Google Scholar

[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: 10.1137/s089548019936223x

Google Scholar

[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: 10.1007/3-540-61310-2_30

Google Scholar

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

Google Scholar

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

Google Scholar

[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: 10.1016/s0167-5060(08)70356-x

Google Scholar