Solving a multi-objective open shop scheduling problem by a novel hybrid ant colony optimization

This paper considers an open shop scheduling problem that minimizes bi-objectives. namely makespan and total tardiness. This problem, due to its complexity, is ranked in the class of NP-hard problems. In this case, traditional approaches cannot reach to an optimal solution in a reasonable time. Thus, we propose an efficient method based on multi-objective simulated annealing and ant colony optimization, in order to solve the given problem. Furthermore a decoding operator is applied in order to improve the quality of generated schedules. Finally, we compare our computational results with a well-known multi-objective genetic algorithm, namely NSGA II. In addition, comparisons are made in single objective case. The outputs show encouraging results in the form of the solution quality. (C) 2010 Elsevier Ltd. All rights reserved.