A PRODUCTION SCHEDULING PROBLEM AS A TIME-DEPENDENT TRAVELING SALESMAN PROBLEM: EXACT AND HEURISTIC APPROACHES

This paper studies a production scheduling problem with sequence-dependent and time-dependent setup times on a single machine. This Sequence- and Time-Dependent Scheduling Problem (STDSP) arises, for instance, when some setups cannot be performed during a certain part of the day. We consider the problem where the transition between two jobs involves two setups: one that can be performed at any time (an unrestricted setup) and another one that is required to take place outside of a given time interval (a restricted setup). It is possible to divide the restricted setup into two parts: one performed before the forbidden interval and the other performed after this interval. In addition, the unrestricted setup can be performed before or after the restricted setup. To schedule a job it is thus necessary to know the completion time of its predecessor, which determines whether both setups can be performed consecutively without interruption or if there is an idle time due to the restricted setup. Hence, the setup time between two jobs is clearly a function of the time at which the first of these jobs is completed. We consider a planning horizon of several periods (e.g., days) with a forbidden interval that repeats in the same position in each period. This problem is inspired from the actua