Parallel machine scheduling with s-precedence constraints

Eun-Seok Kim and Marc Posner

IISE Transactions, 2010, vol. 42, issue 7, 525-537

Abstract: For s-precedence constraints, job i cannot start processing until all jobs that precede i start. This is different from the standard definition of a precedence relation where i cannot start until all prior jobs complete. While not discussed in the scheduling literature, s-precedence constraints have wide applicability in real-world settings such as first-come, first-served processing systems. This article considers a deterministic scheduling problem where jobs with s-precedence relations are processed by multiple identical parallel machines. The objective is to minimize the makespan. The problem is shown to be intractable. A heuristic procedure is developed and tight worst-case bounds on the relative error are derived. Finally, computational experiments show that the proposed heuristic provides effective solutions.

Date: 2010
References: Add references at CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://hdl.handle.net/10.1080/07408171003670975 (text/html)
Access to full text is restricted to subscribers.

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:taf:uiiexx:v:42:y:2010:i:7:p:525-537

Ordering information: This journal article can be ordered from
http://www.tandfonline.com/pricing/journal/uiie20

DOI: 10.1080/07408171003670975

Access Statistics for this article

IISE Transactions is currently edited by Jianjun Shi

More articles in IISE Transactions from Taylor & Francis Journals
Bibliographic data for series maintained by Chris Longhurst ().