Advanced Search

Query:

Fill in the form and click »Search«...

Format:

Display: entries per page entries

Zbl 1142.90399
Gupta, Skylab R.; Smith, Jeffrey S.
Algorithms for single machine total tardiness scheduling with sequence dependent setups. (English)
[J] Eur. J. Oper. Res. 175, No. 2, 722-739 (2006). ISSN 0377-2217

Summary: We consider the problem of scheduling a single machine to minimize total tardiness with sequence dependent setup times. We present two algorithms, a problem space-based local search heuristic and a Greedy Randomized Adaptive Search Procedure (GRASP) for this problem. With respect to GRASP, our main contributions are -- a new cost function in the construction phase, a new variation of Variable Neighborhood Search in the improvement phase, and Path Relinking using three different search neighborhoods. The problem space-based local search heuristic incorporates local search with respect to both the problem space and the solution space. We compare our algorithms with Simulated Annealing, Genetic Search, Pairwise Interchange, Branch and Bound and Ant Colony Search on a set of test problems from literature, showing that the algorithms perform very competitively.

MSC 2000:: *90B35 Scheduling theory
90C59 Approximation methods and heuristics

Keywords: scheduling; total tardiness; heuristics; sequence dependent setups

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering Article Journal

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Advanced Search

Zentralblatt MATH Berlin [Germany]