A Biobjective Optimization for Integrated Parallel Machine Scheduling and Location Problem: Mathematical Model and Iterative Two-Stage Heuristic

Abstract

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.