Premium
A machine‐order search space for job‐shop scheduling problems
Author(s) -
Choi S. H.,
Yang F. Y.
Publication year - 2003
Publication title -
international transactions in operational research
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.032
H-Index - 52
eISSN - 1475-3995
pISSN - 0969-6016
DOI - 10.1111/1475-3995.00430
Subject(s) - computer science , job shop scheduling , flow shop scheduling , scheduling (production processes) , mathematical optimization , dynamic priority scheduling , rate monotonic scheduling , beam search , two level scheduling , search algorithm , algorithm , mathematics , schedule , operating system
Abstract This paper proposes a methodology for real‐time job‐shop scheduling problems. It introduces a new classification of the scheduling methods for JSSPs with emphasis on the search methods and the significance of the search space. Subsequently, a machine‐order search space is proposed as a new framework in which different single‐machine scheduling algorithms and search methods can be incorporated to solve JSSPs. An optimization model relating makespan minimization and the proposed machine‐order search space is also described. The proposed methodology finds an optimal solution by searching a proper machine order in the machine‐order search space and scheduling the machines one by one in this order. Such an approach significantly reduces the size of the search space, and hence the computing efforts. As a result, scheduling of large JSSPs in real‐time becomes practicable.