A new lower bound for the two-machine total tardiness flow shop scheduling problem

• Main Author: Billaut, Jean-Charles
• Other Authors: Laboratoire d'Informatique Fondamentale et Appliquée de Tours (LIFAT), Université de Tours (UT)-Institut National des Sciences Appliquées - Centre Val de Loire (INSA CVL), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)
• Format: Conference Object
• Language: English
• Published: HAL CCSD 2006
• Subjects: [INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC]; [INFO.INFO-RO]Computer Science [cs]/Operations Research [math.OC]; Iceland
• Online Access: https://hal.science/hal-01048625

We consider the classical two machine flow shop scheduling problem, with total tardiness criterion. This problem is strongly NP-hard and literature contains already some lower bounds and dominance conditions. The more recent lower bound of the literature is due to Pan Chen and Chao (COR 2002) and is an improvement of the lower bound proposed by Pan and Fan (IJSE, 1997), Kim (COR 1993) and Sen Dileepan and Gupta (COR 1989). We propose here a new lower bound. Computational experiments show that this bound allows to obtain better results, both in terms of generated nodes and computation time.