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

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...

Full description

Bibliographic Details
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 [cs.RO]
Iceland
Online Access:https://hal.science/hal-01048625
Description
Summary: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.

Similar Items