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

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

1 Citaat (Scopus)


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.
Originele taal-2Engels
Pagina's (van-tot)640-660
Aantal pagina's21
TijdschriftEuropean Journal of Operational Research
Nummer van het tijdschrift2
StatusGepubliceerd - 1 jun 2021

Vingerafdruk Duik in de onderzoeksthema's van 'A Matheuristic for Parallel Machine Scheduling with Tool Replacements'. Samen vormen ze een unieke vingerafdruk.

Citeer dit