A multi-phase covering Pareto-optimal front method to multi-objective parallel machine scheduling

作者：Behnamian J; Zandieh M^*; Ghomi S M T Fatemi

来源：International Journal of Production Research, 2010, 48(17): 4949-4976.

DOI：10.1080/00207540902998349

• parallel machines scheduling
• multi-objective optimisation
• hybrid metaheuristic
• Pareto optimum solution
• Pareto covering
• due window scheduling
• sequence-dependent setup times

This paper considers the problem of parallel machine scheduling with sequence-dependent setup times to minimise both makespan and total earliness/tardiness in the due To tackle the problem considered, a multi-phase algorithm is proposed. The goal of the initial phase is to obtain a good approximation of the Pareto-front. In the second phase, to improve the Pareto-front, non-dominated solutions are unified to constitute a big population. In this phase, based on the local search in the Pareto space concept, three multi-objective hybrid metaheuristics are proposed. Covering the whole set of Pareto-optimal solutions is a desired task of multi-objective optimisation methods. So in the third phase, a new method using an e-constraint hybrid metaheuristic is proposed to cover the gaps between the non-dominated solutions and improve the Pareto-front. Appropriate combinations of multi-objective methods in various phases are considered to improve the total performance. The multi-phase algorithm iterates over a genetic algorithm in the first phase and three hybrid metaheuristics in the second and third phases. Experiments on the test problems with different structures show that the multi-phase method is a better tool to approximate the efficient set than the global archive sub-population genetic algorithm presented previously.

• 出版日期2010