An Effective Metaheuristic Algorithm for Uniform Parallel Machine Scheduling with Resource Consumption Restriction to Minimize The Maximum Lateness - Chen, Jianfu; Li, Kai; Xie, Fulong; Chu, Chengbin (International Journal of Industrial Engineering: Theory, Applications and Practice, 2024)
This paper addresses a uniform parallel machine scheduling problem with resource consumption restriction. The objective is to minimize the maximum lateness under the constraint that the total resource consumption cannot exceed the given budget. To solve this NP-hard problem, a mixed integer programming model is first developed to obtain the exact solution for small-sized instances. Afterward, an effective simulated annealing (SA) algorithm with a repairing procedure is designed to generate near-optimal solutions within reasonable CPU time. The performance of the designed algorithm is evaluated by comparing it with two metaheuristic algorithms adapted from the relevant literature that address similar scheduling problems. The experimental and statistical results show that for small-sized instances, the proposed SA can optimally solve 99.13% of these instances, significantly outperforming its competitors. For large-sized instances, it is shown that the proposed SA can provide the best solution for 97.88% of these instances, markedly surpassing its competitors.