Hybrid metaheuristics for a SDST parallel machines scheduling problem with bi-objectives: makespan and sum of the earliness and tardiness

摘要

In the literature of multi-objective problem there are different algorithms for solving different optimization problems, 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. In formulation of min-max method when this method is combined with the weighting method, the decision-maker can have the flexibility of mixed use of weights and distance parameter in yielding a set of Pareto-efficient solutions. This research extends the new hybrid metaheuristic (HMH) 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 algorithm employs certain probability to avoid becoming trapped in a local optimum, and a variable neighborhood search (VNS) which involves three local search procedures to improve the population. In addition, two 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. Aside, an extensive computational experience is carried out in order to analyze the different parameters of the algorithm.