Minimization of Weighted Tardiness and Makespan in an Open shop Environment by a Novel Hybrid Multi-objective Meta-heuristic Method

This paper considers an open shop scheduling problem that minimizes bi-objectives, namely makespan and weighted tardiness. This problem, due to its complexity, is ranked in a 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 meta-heuristic method by hybridizing a multi-objective simulated annealing and ant colony optimization in order to solve the given problem. Two efficient local searches are also designed and applied to improve solution quality. Finally, we compare our computational results with a well-known multiobjective genetic algorithm, namely NSGA II. Comparisons are made in single objective case as well. The outputs show encouraging results in the form of solution quality.