A Matheuristic for Parallel Machine Scheduling with Tool Replacements

Quang-Vinh Dang (Corresponding author), T.F.H. van Diessen, Tugce G. Martagan, Ivo J.B.F. Adan

Research output: Contribution to journalArticleAcademicpeer-review

21 Citations (Scopus)
13 Downloads (Pure)


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.
Original languageEnglish
Pages (from-to)640-660
Number of pages21
JournalEuropean Journal of Operational Research
Issue number2
Publication statusPublished - 1 Jun 2021


  • Flexible manufacturing systems
  • Genetic algorithm
  • Integer linear programming
  • Scheduling
  • Tool switching


Dive into the research topics of 'A Matheuristic for Parallel Machine Scheduling with Tool Replacements'. Together they form a unique fingerprint.

Cite this