Open AccessSolving Composite MultiobjectiveSingle Machine Scheduling ProblemUsingBranch and Bound and Local SearchAlgorithms
Author(s) -
Hafed M. Motair
Publication year - 2018
Publication title -
maǧallaẗ ʻulūm al-mustanṣiriyyaẗ/mustansiriyah journal of science
Language(s) - English
Resource type - Journals
eISSN - 2521-3520
pISSN - 1814-635X
DOI - 10.23851/mjs.v28i3.122
Subject(s) - tardiness , simulated annealing , mathematical optimization , tabu search , branch and bound , single machine scheduling , hill climbing , computation , computer science , algorithm , scheduling (production processes) , search algorithm , mathematics , job shop scheduling , schedule , operating system
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 problemof 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.