Single Machine Scheduling to Minimize Weighted Sum of Completion Times Added with the Maximum Tardiness - A Branch and Bound Approach

Authors

  • Ayda M. Ramadan College of Medicine, University of Sulaimani, Kurdistan Region, Iraq. Author

DOI:

https://doi.org/10.17656/jzs.10142

Keywords:

Single machine, Weighted sum, Branch and bound

Abstract

This paper considers the problem of scheduling n jobs on a single machine to minimize total weighted completion times and the maximum tardiness. A branch and bound algorithm is proposed to find optimal schedule. Our lower bound based on the late and early jobs. Computational experience on problems with to 60 jobs for a special case and 50 jobs for a general case, where {he previous works solve the problem up to 50 and 40 jobs for special and general case respectively. This indicates that the proposed algorithm is superior to other known algorithms.

References

Anderson, E.J.; Glass, C. A. and Potts, C.N., Local search in combinatorial optimization, EHL.Aarts and 1K. Lenstra, Wilev

Emilie Danna; Edward Rothberg and Claud Le Pape Integrating mixed integer programming and local search: A case study on job-shop scheduling problems. In proceeding of the genetic and evolutionary omputation conference CPAIOR03-2003.

French, S., Sequencing and scheduling, An introduction to the mathematics of the job-shop John Wiley and Sons 1982.

Gupta, IND., Werner, F. and Lauff v e, An enumerative algorithm for two — machine flow shop problems with earliness and tardiness penalties , Msc. classification 90 B35 , 90 (257 68 M 20 , June 30 2004 .

Hakan, D. Utku, Department of industrial engineering, Bilkent University, Ankara April 672 spring 1999.

Natalia, V. Shakhlevich; Yuri, N. Sotskov and Werner, F., Shop-scheduling problems with fixed and non- fixed machine orders of the jobs, Annals of operations research 92,199% 281-304. DOI: https://doi.org/10.1023/A:1018943016617

Potts, C.N. and Van Wassenhove, L. V. ,An algorithm for single machine sequencing with dead lines to minimize total weighted completion times, European journal of operational research 12 ,1983, 379-387. DOI: https://doi.org/10.1016/0377-2217(83)90159-5

Potts, C.N, ;PosnerM.E. and Belouadah Scheduling with release dates on a single machine to minimize total weighted completion time , Discrete applied mathematics

Ramadhan, A. M. and Abdul- Razaq, Tas., A new algorithm for optimality,( RAJ), IA, 2001, 75-78,

Ramadhan,A.M., New local search for multi objective functions, (KAJ), 2(l)A, 20035 6569,

Published

2005-02-21

How to Cite

Single Machine Scheduling to Minimize Weighted Sum of Completion Times Added with the Maximum Tardiness - A Branch and Bound Approach. (2005). Journal of Zankoy Sulaimani - Part A, 8(1), 141-145. https://doi.org/10.17656/jzs.10142

Most read articles by the same author(s)

1 2 3 4 5 6 7 8 9 10 > >>