A bi-objective unrelated parallel machine scheduling problem with additional resources and soft precedence constraints

This paper investigates an unrelated parallel machine scheduling problem with practical production constraints, where the upper limit of additional resources varies across distinct time intervals, and the precedence relationships between jobs can be violated by paying specified penalty costs. We formulate a novel mixed integer linear programming model to minimize the makespan and total penalty cost simultaneously. To tackle this problem, we utilize the framework of the multi-objective evolutionary algorithm based on decomposition, which decomposes the original problem into multiple scalar subproblems. In solving each subproblem, we propose three decoding algorithms to explore different solution spaces in the Pareto front and design a cyclic decoding mechanism inspired by the greedy idea. Furthermore, a 2-swap local search strategy is applied in the evolutionary process to enhance the proposed algorithm. Computational experiments on extensive numerical instances indicate that the cyclic decoding mechanism performs better than the single decoding algorithm. The results of small-scale instances show that the evolutionary algorithms, regardless of using the 2-swap local search, outperform the MILP model in terms of computational efficiency when achieving the optimal Pareto front. For large-scale instances, applying the 2-swap local search strategy significantly enhances the quality of the Pareto front, albeit at the cost of a substantial increase in computational time. The results also demonstrate the superior effectiveness and efficiency of the proposed algorithm compared to NSGA-II.