Novel efficient formulation and matheuristic for large-sized unrelated parallel machine scheduling with release dates
针对带释放时间的无关并行机调度问题，提出了一种整数变量更少的混合整数线性规划模型和三阶段数学启发式算法，在多达3000个作业和20台机器的大规模实例上快速获得高质量近优解。
This study investigates the unrelated parallel machine scheduling problem with release dates to minimise the makespan. The solution to this problem finds wide applications in manufacturing and logistics systems. Due to the strong NP-hardness of the problem, most researchers develop heuristics, and the largest instances they consider are limited to 400 jobs. To tackle this problem, we develop a novel mixed-integer linear program (MILP) with significantly fewer integer variables than the state-of-the-art ones. The proposed MILP does not rely on a binary sequence variable usually used in the existing models. To deal with large-sized instances, a new three-stage matheuristic algorithm (TSMA) is proposed to obtain scheduling decisions. It uses a dispatching rule to sequentially schedule jobs on machines. Then a reassignment procedure is performed to reduce the makespan. Finally, it employs a re-optimisation procedure based on the proposed MILP to perform job moves and exchanges between two selected machines. We conduct numerical experiments on 1440 instances with up to 3000 jobs and 20 machines. Our results first clearly indicate that the proposed model significantly outperforms existing ones. Moreover, the results on large-sized instances show that the proposed TSMA can obtain high-quality near-optimal solutions in a short computation time.