A matheuristic for parallel machine scheduling with tool replacements

Quang-Vinh Dang, Thijs van Diessen, Tugce Martagan and Ivo Adan

European Journal of Operational Research, 2021, vol. 291, issue 2, 640-660

Abstract: 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.

Keywords: Flexible manufacturing systems; Scheduling; Tool switching; Genetic algorithm; Integer linear programming (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221720308547
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:291:y:2021:i:2:p:640-660

DOI: 10.1016/j.ejor.2020.09.050

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().