This article studies an unrelated parallel machine scheduling problem that considers job release times and setup times. The objective is to minimize the makespan subject to a given resource consumption constraint. For this problem, a mathematical model is established for small-sized problems, and a Modified Adaptive Large Neighbourhood Search (MALNS) algorithm is used to solve large-sized problems. To verify the effectiveness of the proposed algorithm, it is compared with three other advanced algorithms and a mathematical model. Each algorithm is run five times, and both the average and best results are recorded. The experimental results show that, for small-sized problems, the MALNS algorithm achieves the average result equal to the optimal result for 93.333% of the 480 instances, while the other three algorithms achieve 91.458%, 62.500% and 43.958%, respectively. For large-sized problems, MALNS provides the best result for all 960 cases, which is far superior to its competitors.
Li et al. (Tue,) studied this question.