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)

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)
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
	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:	Publisher
Last Modified:	04 Mar 2022 13:07
URI:	http://gala.gre.ac.uk/id/eprint/12047

Actions (login required)

View Item

Downloads