The strategies and parameters of tabu search for job-shop scheduling
Journal of Intelligent ManufacturingPublished 8 July 2004
Faruk Geyik, İsmail Hakkı Cedi̇moğlu
Citations72
SJR quartileQ1
SJR score1.76
SNIP2.67
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
This paper focussed on the tabu search strategies and parameters such as initial solution, neighborhood structure, tabu list, aspiration criterion, elite solutions list, intensification, diversification and the number of iteration for the job-shop scheduling problem.
Abstract
This paper presents a tabu search approach for the job-shop scheduling problem. Although the problem is NP-hard, satisfactory solutions have been obtained recently by tabu search. However, tabu search has a problem-specific and parametric structure. Therefore, in the paper, we focussed on the tabu search strategies and parameters such as initial solution, neighborhood structure, tabu list, aspiration criterion, elite solutions list, intensification, diversification and the number of iteration. In order to compare some neighborhood strategies and tabu list length methods, a computational study is done on the benchmark problems.
Keywords
Computer ScienceEngineering
IIE TransactionsScheduling: Theory, Algorithms, and Systems
6,281 Citations1996Michael Pinedo
Scheduling will serve as an essential reference for professionals working on scheduling problems in manufacturing and computing environments and Graduate students in operations management, operations research, industrial engineering and computer science will find the book to be an accessible and invaluable resource.
Tabu Search
5,702 Citations1997Fred Glover, Manuel Laguna
INFORMS Journal on ComputingTabu Search—Part II
5,643 Citations1990Fred Glover
The elements of staged search and structured move sets are characterized, which bear on the issue of finiteness, and new dynamic strategies for managing tabu lists are introduced, allowing fuller exploitation of underlying evaluation functions.
INFORMS Journal on ComputingTabu Search—Part I
4,974 Citations1989Fred Glover
The fundamental principles underlying tabu search as a strategy for combinatorial optimization problems are presented and more advanced considerations are examined, applying the basic ideas to special settings and outlining a dynamic move structure to insure finiteness.
Computers & Operations ResearchFuture paths for integer programming and links to artificial intelligence
4,050 Citations1986Fred Glover
Four key areas of Integer programming are examined from a framework that links the perspectives of artificial intelligence and operations research, and each has characteristics that appear usefully relevant to developments on the horizon.
Tabu Search
2,936 Citations1997Fred Glover, Manuel Laguna
This book explores the meta-heuristics approach called tabu search, which is dramatically changing the authors' ability to solve a host of problems that stretch over the realms of resource planning, telecommunications, VLSI design, financial analysis, scheduling, spaceplanning, energy distribution, molecular engineering, logistics, pattern classification, flexible manufacturing, waste management,mineral exploration, biomedical analysis, environmental conservation and scores of other problems.
European Journal of Operational ResearchBenchmarks for basic scheduling problems
2,403 Citations1993Éric D. Taillard
This paper proposes 260 randomly generated scheduling problems whose size is greater than that of the rare examples published, and the objective is the minimization of the makespan.
Scheduling Algorithms
1,617 Citations2001Peter Brucker
Besides scheduling problems for single and parallel machines and shop scheduling problems, this book covers advanced models involving due-dates, sequence dependent changeover times and batching.
Management ScienceThe Shifting Bottleneck Procedure for Job Shop Scheduling
1,600 Citations1988Joseph Adams, Egon Balas +1 more
An approximation method for solving the minimum makespan problem of job shop scheduling by sequences the machines one by one, successively, taking each time the machine identified as a bottleneck among the machines not yet sequenced.
Operations ResearchA Survey of Scheduling Rules
1,295 Citations1977S. S. Panwalkar, Wafik H. Iskander
This paper presents a summary of over 100 priority dispatching rules, a list of many references that analyze them, and a classification scheme.
Operations ResearchJob Shop Scheduling by Simulated Annealing
1,124 Citations1992Peter J. M. van Laarhoven, Emile Aarts +1 more
An approximation algorithm based on simulated annealing, a generalization of the well known iterative improvement approach to combinatorial optimization problems, that can find shorter makespans than two recent approximation approaches that are more tailored to the job shop scheduling problem.
Management ScienceA Fast Taboo Search Algorithm for the Job Shop Problem
973 Citations1996Eugeniusz Nowicki, Czesław Smutnicki
A fast and easily implementable approximation algorithm for the problem of finding a minimum makespan in a job shop is presented, based on a taboo search technique with a specific neighborhood definition which employs a critical path and blocks of operations notions.
INFORMS Journal on ComputingA Computational Study of the Job-Shop Scheduling Problem
901 Citations1991David Applegate, William J. Cook
The optimization procedure, combining the heuristic method and the combinatorial branch and bound algorithm, solved the well-known 10×10 problem of J. F. Thomson in under 7 minutes of computation time on a Sun Sparcstation 1.
Management ScienceAn Algorithm for Solving the Job-Shop Problem
813 Citations1989Jacques Carlier, Éric Pinson
A branch and bound method based on one-machine scheduling problems and made more efficient by several propositions which limit the search tree by using immediate selections for the job-shop problem.
Operations ResearchAlgorithms for Solving Production-Scheduling Problems
788 Citations1960Bernard Giffler, Gerald L. Thompson
It is shown that it is practical, in problems of small size, to generate the complete set of all active schedules and to pick the optimal schedules directly from this set and, when this is not practical, to random sample from the bet of allactive schedules.
Annals of Operations ResearchApplying tabu search to the job-shop scheduling problem
595 Citations1993Mauro Dell’Amico, Marco Trubian
This paper applies the tabu-search technique to the job-shop scheduling problem, a notoriously difficult problem in combinatorial optimization and shows that the implementation of this method dominates both a previous approach with tabu search and the other heuristics based on iterative improvements.
Expert SystemsISIS—a knowledge‐based system for factory scheduling
551 Citations1984Mark S. Fox, Stephen F. Smith
This paper describes ISIS, a scheduling system capable of incorporating all relevant constraints in the construction of job shop schedules, and examines both the representation of constraints within ISIS, and the manner in which these constraints are used in conducting a constraint-directed search for an acceptable schedule.
Management ScienceNew Search Spaces for Sequencing Problems with Application to Job Shop Scheduling
546 Citations1992Robert H. Storer, S. David Wu +1 more
Applications of the proposed methodology are developed for job shop scheduling problems, and can be easily applied with any scheduling objective, and the applicability of local search to a wide range of problems is found.
Discrete Applied MathematicsA branch and bound algorithm for the job-shop scheduling problem
497 Citations1994Peter Brucker, Bernd Jurisch +1 more
A fast branch and bound algorithm for the job-shop scheduling problem has been developed and it solves the 10 × 10 benchmark problem which has been open for more than 20 years.
Management ScienceGuided Local Search with Shifting Bottleneck for Job Shop Scheduling
405 Citations1998Egon Balas, Alkis Vazacopoulos
A hybrid procedure that embeds GLS (Guided Local Search) into a Shifting Bottleneck framework and takes advantage of the differences between the two neighborhood structures proves to be particularly efficient.
Operations ResearchMachine Sequencing Via Disjunctive Graphs: An Implicit Enumeration Algorithm
399 Citations1969Egon Balas
This paper describes an implicit enumeration procedure that solves the problem by generating a sequence of circuit-free graphs and solving a slightly amended critical-path problem for each graph in the sequence.
INFORMS Journal on ComputingParallel Taboo Search Techniques for the Job Shop Scheduling Problem
355 Citations1994Éric D. Taillard
A fast parallel algorithm is given that provides good solutions to very large problems in a very short computation time and identifies a type of problem for which taboo search provides an optimal solution in a polynomial mean time in practice.
Computers & Operations ResearchEvolution based learning in a job shop scheduling environment
329 Citations1995Ulrich Dorndorf, Erwin Pesch
A class of approximation algorithms is described for solving the minimum makespan problem of job shop scheduling and can find shorter makespans than the shifting bottleneck heuristic or a simulated annealing approach with the same running time.
Data Archiving and Networked Services (DANS)Job shop scheduling by local search
232 Citations1992Aarts, E.H.L., Lenstra, J.K. +2 more
INFORMS Journal on ComputingA Computational Study of Local Search Algorithms for Job Shop Scheduling
183 Citations1994Emile Aarts, Peter J. M. van Laarhoven +2 more
This study shows that simulated annealing performs best in the sense that it finds better solutions than the other algorithms within the same amount of running time.
International Journal of Production ResearchA modified shifting bottleneck procedure for job-shop scheduling
128 Citations1993Stéphane Dauzère‐Pérès, Jean B. Lasserre
A modified version of the Adams et al. shifting bottleneck procedure for job-shop scheduling is proposed, by modifying Carlier's algorithm extensively used in the SB procedure, to eliminate some drawbacks.
IIE TransactionsSolving the job shop scheduling problem with tabu search
125 Citations1995J. Wesley Barnes, John B. Chambers
An effective tabu search approach to the job shop scheduling problem is presented that makes use of the classical disjunctive network representation of the problem and iteratively moves to another feasible solution by reversing the order of two adjacent critical path operations performed by the same machine.
Reactive Scheduling Systems
107 Citations1995Stephen F. Smith
OPIS is described, a scheduling system designed to incrementally revise schedules in response to changes to solution constraints, which implements a constraint-directed approach to reactive scheduling.
International Journal of Production ResearchLinguistic-based meta-heuristic optimization model for flexible job shop scheduling
74 Citations2002Adil Baykasoğlu
A linguistic based meta-heuristic modelling and solution approach for solving the Flexible Job Shop Scheduling Problem (FJSSP) and it is observed that the effect of dispatching rule selection on the jobshop performance diminishes by increasing the job shop flexibility.
Journal of HeuristicsNew and “Stronger” Job-Shop Neighbourhoods: A Focus on the Method of Nowicki and Smutnicki (1996)
52 Citations2000Anant Jain, Balasubramanian Rangaswamy +1 more
Findings show that the NS neighbourhood causes the method's choice of an initialisation procedure to have an important influence on the best solution the method is able to find, and implications for developing new and more effective job-shop algorithms are discussed.
Annals of Operations ResearchA tabu search experience in production scheduling
50 Citations1993J. Wesley Barnes, Manuel Laguna
A synthesis of the various tabu search mechanisms that have been employed, giving special attention to advances that have led to major improvements and suggesting directions for future research.
International Journal of Production ResearchA new dynamic programming formulation of (n x m) flowshop sequencing problems with due dates
45 Citations1998Alİ İhsan Sönmez, Adil Baykasoğlu
IEEE International Conference on Neural NetworksStochastic neural networks for solving job-shop scheduling. II. architecture and simulations
27 Citations1988Foo Yoon-Pin Simon, Yoshiyasu Takefuji
The authors introduce a neural computation architecture based on a stochastic Hopfield neural network model for solving job-shop scheduling by choosing an appropriate annealing schedule and results show near-optimal and optimal solutions to job- shop problems can be found.
International Journal of Computer Integrated ManufacturingA new integrated system for loading and scheduling in cellular manufacturing
20 Citations2002Sameh M. Saad, Adil Baykasoğlu +1 more
A multiple objective optimization technique, based on simulation, and a taboo search algorithm are proposed for loading and scheduling Cellular Manufacturing systems (CM).