Premium
Heuristic, optimal, static, and dynamic schedules when processing times are uncertain
Author(s) -
Lawrence Stephen R.,
Sewell Edward C.
Publication year - 1997
Publication title -
journal of operations management
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 3.649
H-Index - 191
eISSN - 1873-1317
pISSN - 0272-6963
DOI - 10.1016/s0272-6963(96)00090-3
Subject(s) - heuristics , computer science , mathematical optimization , job shop scheduling , heuristic , scheduling (production processes) , flow shop scheduling , dynamic priority scheduling , dynamic programming , algorithm , mathematics , artificial intelligence , schedule , operating system
In this paper we compare the static and dynamic application of heuristic and optimal solution methods to job‐shop scheduling problems when processing times are uncertain. Recently developed optimizing algorithms and several heuristics are used to evaluate 53 standard job‐shop scheduling problems with a makespan objective when job processing times are known with varying degrees of uncertainty. Results indicate that fixed optimal sequences derived from deterministic assumptions quickly deteriorate with the introduction of processing time uncertainty when compared with dynamically updated heuristic schedules. As processing time uncertainty grows, we demonstrate that simple dispatch heuristics provide performance comparable or superior to that of algorithmically more sophisticated scheduling policies.