Parallel machine scheduling with s-precedence constraints

Authors: Kim, Eun-Seok1; Posner, Marc2

Source: IIE Transactions, Volume 42, Number 7, July 2010 , pp. 525-537(13)

Publisher: Taylor and Francis Ltd

Buy & download fulltext article:


Price: $61.16 plus tax (Refund Policy)


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.

Keywords: Parallel machines scheduling; heuristic analysis; makespan; precedence constraints

Document Type: Research Article


Affiliations: 1: Cass Business School, City University London, London, United Kingdom 2: The Ohio State University, Integrated Systems Engineering, Columbus, OH, USA

Publication date: July 1, 2010

Related content


Free Content
Free content
New Content
New content
Open Access Content
Open access content
Subscribed Content
Subscribed content
Free Trial Content
Free trial content

Text size:

A | A | A | A
Share this item with others: These icons link to social bookmarking sites where readers can share and discover new web pages. print icon Print this page