Title :
Lower Bounds for Tardiness Minimization on a Single Machine with Family Setup Times
Author_Institution :
Lab. d´´Optimisation des Systemes Industriels, Univ. de Technologie de Troyes
Abstract :
In this paper, we consider the scheduling of N jobs on a single machine with family setup times in order to minimize the total tardiness. The set of jobs is divided into F families. Between two jobs of the same family, we have not to stop the machine. However, when switching from family to another, a setup is required. Each family is characterized by a setup time independent of the sequence. We propose a set of approaches to compute lower bounds for the tardiness criterion. These approaches are analyzed and tested on a large set of numerical experiments in order to identify the dominant lower bounds
Keywords :
minimisation; single machine scheduling; family setup times; job scheduling; lower bound; single machine; tardiness criterion; tardiness minimization; Dynamic programming; Genetic algorithms; Job shop scheduling; Lagrangian functions; Polynomials; Processor scheduling; Single machine scheduling; Systems engineering and theory; Testing; family setup times; lower bounds; scheduling; single machine;
Conference_Titel :
Computational Engineering in Systems Applications, IMACS Multiconference on
Conference_Location :
Beijing
Print_ISBN :
7-302-13922-9
Electronic_ISBN :
7-900718-14-1
DOI :
10.1109/CESA.2006.4281799
