Solving Composite Multi objective Single Machine Scheduling Problem Using Branch and Bound and Local Search Algorithms

S. Abdul, Tariq; Razaq,

	Solving Composite Multi objective Single Machine Scheduling Problem Using Branch and Bound and Local Search Algorithms
Al-Mustansiriyah Journal of Science
Article 1, Volume 28, Issue 3, 2017, Pages 200-208
Authors
Tariq S. Abdul;
Abstract
This paper present algorithm for solving a single machine scheduling problem to minimize the sum of total completion times, total tardiness, maximum tardiness, and maximum earliness. The single machine total tardiness problem is already NP-hard, so they consider problem is strongly NP-hard, and several algorithms are used to solve it. Branch and bound algorithm with dominance rule and local search algorithms 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 needs longer times. Thus we tackle the problem of large sizes with local search algorithms descent method, simulated annealing and tabu search. The performance 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 in reasonable times.
Keywords
Multicriteria Scheduling; Branch and bound; Dominance rule; Local search algorithms

Statistics Article View: 45 PDF Download: 7