Solving Composite MultiobjectiveSingle Machine Scheduling ProblemUsingBranch and Bound and Local SearchAlgorithms
DOI:
https://doi.org/10.23851/mjs.v28i3.122Keywords:
Multiciteria Scheduling, Branch and bound, Dominance rule, Local search algorithms.Abstract
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.Downloads
References
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
Downloads
Key Dates
Published
Issue
Section
License
Articles accepted for publication in Al-Mustansiriyah Journal of Science (MJS) are protected under the Creative Commons Attribution 4.0 International License (CC BY-NC). Authors of accepted articles are requested to sign a copyright release form prior to their article being published. All authors must agree to the submission, sign copyright release forms, and agree to be included in any correspondence between MJS and the authors before submitting a work to MJS. For personal or educational use, permission is given without charge to print or create digital copies of all or portions of a MJS article. However, copies must not be produced or distributed for monetary gain. It is necessary to respect the copyright of any parts of this work that are not owned by MJS.
How to Cite
