A branch-and-cut algorithm for a production scheduling problem with sequence-dependent and time-dependent setup times

• Published in: Computers & operations research 2008-08, Vol.35 (8), p.2635-2655
• Main Authors: Stecco, Gabriella, Cordeau, Jean-François, Moretti, Elena
• Format: Article
• Language: English
• Subjects: Algorithms; Applied sciences; Branch & bound algorithms; Exact sciences and technology; Job shops; Linear programming; Logistics; Operational research and scientific management; Operational research. Management science; Production scheduling; Scheduling, sequencing; Sequence-dependent; Setup times; Studies; Time-dependent; Traveling salesman problem
• ISSN: 0305-0548; 1873-765X; 0305-0548
• DOI: 10.1016/j.cor.2006.12.021

This paper introduces and compares three different formulations of a production scheduling problem with sequence-dependent and time-dependent setup times on a single machine. The setup is divided into two parts: one that can be performed at any time and another one that is restricted to be performed outside of a given time interval. As a result, the setup time between two jobs is a function of the completion time of the first job. The problem can be formulated as a time-dependent traveling salesman problem, where the travel time between two nodes is a function of the departure time from the first node. We show that the resulting formulation can be strengthened to provide better linear programming relaxation lower bounds. We also introduce several families of valid inequalities which are used within a branch-and-cut algorithm. Computational experiments show that this algorithm can solve some instances with up to 50 jobs within reasonable computing times.