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

Ayda M. Ramadan

College of Medicine, University of Sulaimani

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 ootimal 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 al gorithm is superior to other known algorithms .

Keywords: Single machine, weighted sum, Branch and bound.


[1] Anderson, E.J.; Glass, C. A. and Potts, C.N., Local search in combinatorial optimization, EHL.Aarts and 1K. Lenstra, Wilev 
[2] 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.
[3] French, S., Sequencing and scheduling, An introduction to the mathematics of the job-shop John Wiley and Sons 1982.
[4] 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 .
[5] Hakan, D. Utku, Department of industrial engineering, Bilkent University, Ankara April   672 spring 1999.
[6] 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.
[7] 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.
[8] Potts, C.N, ;PosnerM.E. and Belouadah Scheduling with release dates on a single machine to minimize total weighted completion time , Discrete applied mathematics
[9] Ramadhan, A. M. and Abdul- Razaq, Tas., A new algorithm for optimality,( RAJ), IA, 2001, 75-78,
[10] Ramadhan,A.M., New local search for multi objective functions, (KAJ), 2(l)A, 20035 6569,