A fast taboo search algorithm for the job shop problem. (English) Zbl 0880.90079

Nowicki, Eugeniusz; Smutnicki, Czeslaw

Manage. Sci. 42, No. 6, 797-813 (1996).

Summary: A fast and easily implementable approximation algorithm for the problem of finding a minimum makespan in a job shop is presented. The algorithm is based on a taboo search technique with a specific neighborhood definition which employs a critical path and blocks of operations notions. Computational experiments (up to 2,000 operations) show that the algorithm not only finds shorter makespans than the best approximation approaches but also runs in shorter time. It solves the well-known \(10\times 10\) hard benchmark problem within 30 seconds on a personal computer.

MSC:

90B35

Deterministic scheduling theory in operations research

Keywords:

approximation algorithm; minimum makespan; job shop; taboo search

Software:

JOBSHOP