Title: A comparison of different mathematical models for the job sequencing and tool switching problem with non-identical parallel machines

Authors: Dorothea Calmels

Addresses: University of Passau, Innstr. 27, 94032 Passau, Germany

Abstract: This paper addresses the generalisation of the NP-hard job sequencing and tool switching problem with non-identical parallel machines and sequence-dependent setup times where a set of jobs is to be scheduled on unrelated parallel machines with machine-dependent processing and tool switching times. Three different mathematical models for two different objectives are presented and applied to newly generated test instances. The instances are compared and analysed using a commercial solver and an iterated local search heuristic. Overall, it is shown that the solution quality obtained by the mathematical models depends on the size of the problem instance as well as the tool requirements. The precedence-based formulation is superior in general to the position-based and time-index-based formulation for dense problem instances while the position-based formulation works well for sparse problems. With an increasing problem size, the metaheuristic requires significantly less time to find near-optimal solutions than the mathematical models.

Keywords: mixed integer programming; job sequencing and tool switching; tooling constraints; parallel machines; sequence-dependent setup times.

DOI: 10.1504/IJOR.2022.128396

International Journal of Operational Research, 2022 Vol.45 No.4, pp.419 - 441

Received: 05 Nov 2019
Accepted: 10 Jan 2020
Published online: 20 Jan 2023 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article