On the representation of the one machine sequencing problem in the shifting bottleneck heuristic
Abstract
The Shifting Bottleneck heuristic decomposes the Job Shop problem into a series of One Machine Sequencing Problems
(OMSPs) with release and due dates, precedence constraints and the minimization of maximum lateness objective. It is well
known that delayed precedence constraints may exist between two operations to be performed on the same machine. We
identify a new type of precedence relationship that may exist in an OMSP between the predecessor of an operation and the
successor of another. The premise that an OMSP captures the sequencing relationships on other machines in the release
and due date information is not valid when such precedence relationships exist. A modification of the OMSP representation
is proposed based on a generalized lateness objective defined on a due window. The implications of such a representation
for the OMSP solution procedure have been explored.
Collections
- Journal Articles [3690]