Algorithms for single machine total tardiness scheduling with sequence dependent setups

doi:10.1016/j.ejor.2005.05.018

Algorithms for single machine total tardiness scheduling with sequence dependent setups

2006-12-01

77

PRE

AI

DOI：10.1016/j.ejor.2005.05.018

Original

Original request for help

Save

Abstract

En 中文

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 IF 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 66 from literature, showing that the algorithms perform very competitively. (c) 2005 Elsevier B.V. All rights reserved.

Keywords:

scheduling

total tardiness

heuristics

sequence dependent setups

Algorithms for single machine total tardiness scheduling with sequence dependent setups

Abstract

Journal

Organization