On the representation of the One Machine Sequencing Problem in the Shifting Bottleneck Heuristic

Saral Mukherjee and Chalterjee A K

No WP2004-11-01, IIMA Working Papers from Indian Institute of Management Ahmedabad, Research and Publication Department

Abstract: The Shilling 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 constraint 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 constraints 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.

Date: 2004-11-01
References: Add references at CitEc
Citations:

Downloads: (external link)
https://www.iima.ac.in/sites/default/files/rnpfiles/2004-11-01saralm.pdf English Version (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:iim:iimawp:wp01855

Access Statistics for this paper

More papers in IIMA Working Papers from Indian Institute of Management Ahmedabad, Research and Publication Department Contact information at EDIRC.
Bibliographic data for series maintained by ().