Skip to main content

Parallel machine scheduling with s-precedence constraints

Buy Article:

$60.90 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


Access Key

Free Content
Free content
New Content
New content
Open Access Content
Open access content
Subscribed Content
Subscribed content
Free Trial Content
Free trial content
Cookie Policy
Cookie Policy
Ingenta Connect website makes use of cookies so as to keep track of data that you have filled in. I am Happy with this Find out more