Parallel machines scheduling with dual criteria and sequence-dependent setups: Cooperative metaheuristics

摘要

This paper presents a min-max multi-objective procedure for a dual-objective, namely makespan, and sum of the earliness and tardiness of jobs in due window problems, simultaneously. This research extends the new hybrid metaheuristic for solving parallel machines scheduling problems with sequence-dependent setup times which comprises three components: an initial population generation method based on an ant colony optimization (ACO), a simulated annealing (SA) as an evolutionary stochastic searching algorithm, and a variable neighborhood search which involves three local search procedures to improve the population. In addition, two variable neighborhood search (VNS) based hybrid metaheuristics, which are a combination of two methods, SA/VNS and ACO/VNS, are also proposed for solving the addressed scheduling problems. The non-dominated sets obtained from each of algorithms are compared in terms of various indices, and the computational results show that the proposed algorithm is capable of producing a number of high-quality Pareto optimal scheduling plans.