Skip navigation

An approximation algorithm for the three-machine scheduling problem with the routes given by the same partial order

An approximation algorithm for the three-machine scheduling problem with the routes given by the same partial order

Quibell, Richard and Strusevich, Vitaly A. (2014) An approximation algorithm for the three-machine scheduling problem with the routes given by the same partial order. Computers & Industrial Engineering, 76. pp. 347-359. ISSN 0360-8352 (doi:https://doi.org/10.1016/j.cie.2014.08.009)

[img]
Preview
PDF (Publisher's Unedited Manuscript)
12047_QUIBELL_STRUSEVICH_(AAM)_(2014).pdf - Accepted Version
Available under License Creative Commons Attribution Non-commercial No Derivatives.

Download (779kB)
[img]
Preview
PDF (Author's Accepted Manuscript)
12047 STRUSEVICH_An_Approximation_Algorithm_(AAM)_2014.pdf - Accepted Version
Available under License Creative Commons Attribution Non-commercial No Derivatives.

Download (318kB) | Preview
[img] PDF (Acceptance email)
12047_QUIBELL_STRUSEVICH_(Acceptance_email_13Aug2014)_(2014).pdf - Additional Metadata
Restricted to Repository staff only

Download (101kB)

Abstract

The paper considers a three-machine shop scheduling problem to minimize the makespan, in which the route of a job should be feasible with respect to a machine precedence digraph with three nodes and one arc. For this NP-hard problem that is related to the classical flow shop and open shop models, we present a simple 1.5-approximation algorithm and an improved 1.4-approximation algorithm.

Item Type: Article
Additional Information: [1] The Author's Accepted Manuscript version is attached. [2] Please cite this article as: Quibell, R., Strusevich, V.A., An Approximation Algorithm for the Three-Machine Scheduling Problem with the Routes Given by the Same Partial Order, Computers & Industrial Engineering (2014), doi: http://dx.doi.org/10.1016/j.cie.2014.08.009. [3] This is a PDF file of an unedited manuscript that has been accepted for publication. As a service to our customers we are providing this early version of the manuscript. The manuscript will undergo copyediting, typesetting, and review of the resulting proof before it is published in its final form. Please note that during the production process errors may be discovered which could affect the content, and all legal disclaimers that apply to the journal pertain.
Uncontrolled Keywords: shop scheduling, makespan minimization, partially ordered route, approximation
Subjects: Q Science > QA Mathematics
Faculty / School / Research Centre / Research Group: Faculty of Engineering & Science > School of Computing & Mathematical Sciences (CMS)
Faculty of Engineering & Science
Related URLs:
Last Modified: 04 Mar 2022 13:07
URI: http://gala.gre.ac.uk/id/eprint/12047

Actions (login required)

View Item View Item

Downloads

Downloads per month over past year

View more statistics