A Biobjective Optimization for Integrated Parallel Machine Scheduling and Location Problem: Mathematical Model and Iterative Two-Stage Heuristic
研究了机器选址与作业调度的双目标优化问题，提出改进的混合整数线性规划和迭代两阶段启发式算法，在500个基准实例中求解率达78.4%，优于现有方法。
This study investigates a biobjective integrated parallel machine scheduling and location problem. It aims to place machines on a set of candidate locations, assign jobs dispersed in different locations to the placed machines, and sequence them while minimizing the maximum completion time, i.e., makespan, and the location cost. For the challenging NP-hard problem, we first develop an improved mixed-integer linear program. Then, several inequalities are proposed to further strengthen it. To more effectively and efficiently solve practical-size instances, a new iterative two-stage heuristic algorithm based on <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\varepsilon $ </tex-math></inline-formula> -constraint is proposed. Extensive experimental results demonstrate that 1) the improved model with valid inequalities can solve 78.4% of 500 benchmark instances, more than 29.8% for the state-of-the-art one and the Pareto solutions obtained by the former are much superior to that of the latter and 2) the proposed iterative two-stage heuristic algorithm can solve all benchmark instances and its performance is significantly superior to the widely adapted nondominated sorting genetic algorithm II in obtaining high-quality Pareto solutions.