Skip to main content

Parallel machine scheduling with s-precedence constraints

Buy Article:

$60.90 plus tax (Refund Policy)

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.

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

Document Type: Research Article

DOI: http://dx.doi.org/10.1080/07408171003670975

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

tandf/uiie/2010/00000042/00000007/art00005
dcterms_title,dcterms_description,pub_keyword
6
5
20
40
5

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
X
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