Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/24516
Title: Scheduling of a two-stage differentiation flowshop to minimize weighted sum of machine completion times
Authors: Cheng, TCE 
Lin, BMT
Tian, Y
Keywords: Approximation algorithm
Flowshop
Machine completion time
Performance ratio
Issue Date: 2009
Publisher: Pergamon Press
Source: Computers and operations research, 2009, v. 36, no. 11, p. 3031-3040 How to cite?
Journal: Computers and operations research 
Abstract: This paper considers the problem of scheduling a two-stage flowshop that consists of a common critical machine in stage one and two independent dedicated machines in stage two. All the jobs require processing first on the common critical machine. Each job after completing its critical operation in stage one will proceed to the dedicated machine of its type for further processing in stage two. The objective is to minimize the weighted sum of stage-two machine completion times. We show that the problem is strongly NP-hard, and develop an O (n3) polynomial time algorithm to solve the special case where the sequences of both types of jobs are given. We also design an approximation algorithm with a tight performance ratio of frac(4, 3) for the general case.
URI: http://hdl.handle.net/10397/24516
ISSN: 0305-0548
EISSN: 1873-765X
DOI: 10.1016/j.cor.2009.02.001
Appears in Collections:Journal/Magazine Article

Access
View full-text via PolyU eLinks SFX Query
Show full item record

SCOPUSTM   
Citations

14
Last Week
0
Last month
0
Citations as of Aug 14, 2017

WEB OF SCIENCETM
Citations

9
Last Week
0
Last month
0
Citations as of Aug 13, 2017

Page view(s)

50
Last Week
2
Last month
Checked on Aug 13, 2017

Google ScholarTM

Check

Altmetric



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.