Solving Composite MultiobjectiveSingle Machine Scheduling ProblemUsingBranch and Bound and Local SearchAlgorithms

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.

Keywords

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