Minimizing total tardiness on a single machine with sequence-dependent setup times

Ahmed Souissi (1) , Imed Kacem (1, 2) , Chengbin Chu (1)

1 LOSI - Laboratoire d'Optimisation des Systèmes Industriels
2 LCOMS - Laboratoire de Conception, Optimisation et Modélisation des Systèmes

In this paper, we study the single machine scheduling problem with setup times for minimizing total tardiness. Such a problem is NP-hard and presents many difficulties to be solved. To reduce these difficulties, we propose a branch and bound algorithm. Our method is based on a new lower bound and is compared with Ragatz lower bound. New dominance rule and original exploration strategy are also proposed. Preliminary numerical simulations are encouraging and promising.

Keywords: Single machine scheduling; Job shop scheduling; Simulated annealing; Equations; Integer linear programming; Numerical simulation; Genetic algorithms; Mixed integer linear programming; Scheduling algorithm; Upper bound

Domains: Operations Research [cs.RO]

Ahmed Souissi, Imed Kacem, Chengbin Chu. Minimizing total tardiness on a single machine with sequence-dependent setup times. 2004 IEEE International Conference on Systems, Man and Cybernetics (IEEE Cat. No.04CH37583), Oct 2004, The Hague, Netherlands. pp.1481-1485, ⟨10.1109/ICSMC.2004.1399840⟩. ⟨hal-02497493⟩