A Matheuristic for Parallel Machine Scheduling with Tool Replacements

This paper addresses the problem of scheduling a set of jobs with tool requirements on identical parallel machines in a work center. This problem considers the following characteristics. First, each job may consist of an ordered set of operations due to reentrance to the work center. Moreover, operations have release times and due dates, and the processing of operations requires different tool sets of different sizes. Last, the objective is to minimize both tardiness of operations and tool setup times. Decisions concern the assignment of operations to machines, sequencing of operations, and replacement of tool sets on machines. We propose a mathematical model for the problem and a new matheuristic that combines a genetic algorithm and an integer linear programming formulation to solve industry-size instances. In the matheuristic, we propose two crossover operators which exploit the structure of the problem. We illustrate this approach through real-world case studies. Computational experiments show that our matheuristic outperforms the mathematical model and a practitioner heuristic. We also generate managerial insights by quantifying the potential room for improvement in current practice.