A Matheuristic Approach to the Open Shop Scheduling Problem with Sequence-Dependent Setup Times

This paper deals with an open shop scheduling problem in which sequence-dependent setup times are present. In open shops there are no restrictions on the processing route of each job, so the decision regards not only the sequencing of jobs on each machine, but also the sequencing of operations (machines) for each job. These type of problems typically arise in application contexts where the order in which the operations are executed is irrelevant. In this work a novel heuristic approach based on mathematical programming, i.e., a matheuristic, is developed and its performance is assessed through a computational study on open shop benchmark instances.