Job shop scheduling with beam search
European Journal of Operational ResearchPublished 1 October 1999
İhsan Sabuncuoğlu, M Bayız
Citations183
SJR quartileQ1
SJR score2.24
SNIP2.62
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
A beam search based scheduling algorithm for the job shop problem using the makespan and mean tardiness as performance measures and is compared with other well known search methods and dispatching rules for a wide variety of problems.
Abstract
Beam Search is a heuristic method for solving optimization problems. It is an adaptation of the branch and bound method in which only some nodes are evaluated in the search tree. At any level, only the promising nodes are kept for further branching and remaining nodes are pruned off permanently. In this paper, we develop a beam search based scheduling algorithm for the job shop problem. Both the makespan and mean tardiness are used as the performance measures. The proposed algorithm is also compared with other well known search methods and dispatching rules for a wide variety of problems. The results indicate that the beam search technique is a very competitive and promising tool which deserves further research in the scheduling literature.
Keywords
Computer ScienceEngineering
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.
Operational Research Quarterly (1970-1977)Introduction to Sequencing and Scheduling
2,619 Citations1977A. J. Clewett, Kenneth R. Baker
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.
Research Showcase @ Carnegie Mellon University (Carnegie Mellon University)Constraint-directed search : a case study of job-shop scheduling
530 Citations1983Mark S. Fox
In this thesis, a system called ISIS is presented, which uses a constraint-directed search paradigm to solve the scheduling problem and provides a knowledge representation language for modeling organizations and their constraints.
Management ScienceSequencing Rules and Due-Date Assignments in a Job Shop
497 Citations1984Kenneth R. Baker
This paper surveys the tactical aspects of this interaction between sequencing priorities and the method of assigning due-dates, focusing primarily on average tardiness as a measure of scheduling effectiveness.
Journal of the Operational Research SocietyHeuristic Scheduling Systems
486 Citations1995Upendra Dave
The HARPY speech recognition system
467 Citations1976B. Lowerre
The HARPY system is the result of an attempt to understand the relative importance of various design choices of two earlier speech recognition systems developed at Carnegie-Mellon University, in which knowledge is represented as a finite state transition network but without the a-priori transition probabilities.
International Journal of Production ResearchFiltered beam search in scheduling†
386 Citations1988Peng Si Ow, Thomas E. Morton
This paper systematically study the performance behaviour of beam search with other heuristic methods for scheduling, and the effects of using different evaluation functions to guide the search, and develops a new variation ofbeam search, called filtered beam search which is computationally simple yet produces high quality solutions.
Large-step Markov chains for the Traveling Salesman Problem
322 Citations2018Olivier Martin
A new class of Markov chain Monte Carlo search procedures are introduced, leading to more powerful optimizat~on methods than simulated annealing, and a new best heuristic is introduced.
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.
European Journal of Operational ResearchA neural network model for scheduling problems
95 Citations1996İhsan Sabuncuoğlu, Burckaan Gurgun
A new neural network approach is proposed to solve the single machine mean tardiness scheduling problem and the minimum makespan job shop scheduling problem that combines the characteristics of neural networks and algorithmic approaches.
International Journal of Production ResearchA bottleneck-based beam search for job scheduling in a flexible manufacturing system
79 Citations1989Yih‐Long Chang, Hirofumi Matsuo +1 more
Journal of Intelligent ManufacturingFlexible manufacturing system (FMS) scheduling using filtered beam search
76 Citations1990Suranjan De, Anita Lee
An important feature of this system, in this view, is the explicit manner in which environmental, procedural and structural knowledge can be used to improve the quality of the generated schedule.
Computers & Industrial EngineeringSimulation studies in job shop scheduling—II
61 Citations1984Ali S. Kiran, Milton L. Smith
Major simulation studies of dynamic job shop scheduling problem and approaches taken to model dynamic job shops have been considered and basic results on relative effectiveness of priority rules in job shop simulation literature are focused.
Computers & Industrial EngineeringSimulation studies in job shop sheduling—I a survey
51 Citations1984Ali S. Kiran, Milton L. Smith
IIE TransactionsA beam search-based algorithm and evaluation of scheduling approaches for flexible manufacturing systems
28 Citations1998İhsan Sabuncuoğlu, Süleyman Karabük
The International Journal of Advanced Manufacturing TechnologyJob-shop scheduling using certain heuristic search algorithms
8 Citations1992L. Hatzikonstantis, C.B. Besant
This paper presents a family of sub-optimal algorithms based on the A* heuristic search algorithm, aimed at solving the general job-shop scheduling problem, and the techniques investigated generally compare favourably with similar work in this field.