Solving Composite MultiobjectiveSingle Machine Scheduling ProblemUsingBranch and Bound and Local SearchAlgorithms

Hafed Mohammed Motair


This paper present algorithms for solving a single machine scheduling  problem to minimize the sum of total completion times, total tardiness,maxim-um tardiness,and maximum earliness.The single machine total tardiness problem is already NP-hard, so the consider problem is strongly NP-hard, and several algorithms are used to solve it. Branch and bound algorithmwith dominance ruleand local search algorit- hms are proposed for the problem. For the Branch and bound algorithm results- show that using dominance rule improve the performance of the algorithm in both computation times and optimal values,but it need longer times.Thus we tackle the problem

of large sizes with local search algorit- hms descent method, simulated annealing and tabusearch. The perfomance of these algorithms is evaluated on a large set of test problems and the results are compared.The computational results show that simulated annealing algorithm and Tabu search algorithm are better than Descent method with preference to simulated annealing algorithm,and show that the three algorithms find optimal or near optimal solutions inreasonable times.


Multiciteria Scheduling, Branch and bound , Dominance rule, Local search algorithms.

Full Text:



Abdul-Razaq, T.S,Ibraheem.S.J (2014)" Single machine with maximum Earliness and maxim-um Tardiness" International Jorna of Mathematical Archive -5(9),2014,79-82.

Abdul-Razaq, T.S ,Mahrooz.Z. A, (2015) "Minimizing the total complition time ,the total tardiness and the maximum tardiness"ibn AL-Haitham J. for Pure & Applide Sci . Vol.28 (2).

Bo Chen , Chris N. Potts, Gerhard J. Woeginger (1998) " A Review of Machine SchedulingComplexity Algorithms and Approximability, Handbook of Combinatorial Optimization, pp. 21-169,1998 Kluwer Academic Publishers.

Brucker . P (2007) " Scheduling Algorithms " , SBN 978-3-540-69515-8 Springer Berlin Heidelberg New York

Crauwels H.A,Potts C.N,Wassen- hove LN,(1996)"Local Search Heuristics for Sin- gle Machine Total Weighted Tardiness Schedul- ing Problem " JOC volume 10,Issue 3,341-350

Du, J., Leung, J.Y.-T., 1990. Minimizing total tardiness on one machine is NP-hard. Mathe- matics of Operations Research 15,483-495.

Eren T (2007)"A multicriteria scheduling with sequence Depe- ndent setup times " Applied Mathematics Science Vol .1,2007 ,no 58,2883-2894.

Garey, M.R., Tarjan, R.E, Wilfong, G.T., 1988. One-processor schedul- ing with symmetric earliness and tardiness penalties. Mathematics of Operations Research 13, 330–348.

Joshua. D. Knowles (2002) "Local Search and Hybrid Evolutionary Algor-ithms for Pareto Optemiza- tion "submited in partial fulfilment of the requirements for the degree of Doctor of Philosophy in comput- er science . Department of comput- er science ,University of Reading, Reading RG6 6AY. UK,January 9.2002.

Jouglet A, Carlier J.(2011)” Dominance rules in combinatorial optimization problems”. European Journal of Operational Research, Elsevier, 212, pp.433-444.

Kindt, T’ V. and Billaut, J.C. , (2006), “Multicriteria Scheduling : Theory, Models and Algorithms” Springer-verlag Berlin Heidelberg ,2nd ed.Discrete Applied Mathema- tics 124, 117-126.

Lee CY, Choi JY (1995)”A genetic algorithm for job sequencing problems with distinct due dates and general early tardy penalty weights”. Computers & Operations Research 22:857–869

Michel G•Jean-Y.P,(2010)" Handbook of Metaheuristics " ISBN 978-1-4419-1663-1, Springer New York Dordrecht Heidelberg London.

Sen T & Gupta S K (1983)’ A BranchandBound Procedure to Solve a Bicriterion Scheduling Problem, IIE Transactions, 15:1, 84-88

Verma, S., Dessouky, M., 1998. Single-machine scheduling of unit-time jobs with earliness and tardiness penalties. Mathematics of Operations Research 23, 930–943.

Wan G, Benjamin P-CY (2002) Tabu search for single machine scheduling with distinct due windows and weighted earliness/tardiness penalties. European Journal of Operational Research 142:271–281



  • There are currently no refbacks.

Copyright (c) 2018 Al-Mustansiriyah Journal of Science

Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.

Copyright (c) 2018 by Al-Mustansiriyah Journal of Science
ISSN: 1814-635X (Print), ISSN: 2521-3520 (online)