Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/21752
Title: Scheduling a single server in a two-machine flow shop
Authors: Cheng, TCE 
Kovalyov, MY
Keywords: Algorithms
Batching
Dynamic programming
Scheduling
Issue Date: 2003
Publisher: Springer
Source: Computing, 2003, v. 70, no. 2, p. 167-180 How to cite?
Journal: Computing 
Abstract: We study the problem of scheduling a single server that processes n jobs in a two-machine flow shop environment. A machine dependent setup time is needed whenever the server switches from one machine to the other. The problem with a given job sequence is shown to be reducible to a single machine batching problem. This result enables several cases of the server scheduling problem to be solved in O(n log n) by known algorithms, namely, finding a schedule feasible with respect to a given set of deadlines, minimizing the maximum lateness and, if the job processing times are agreeable, minimizing the total completion time. Minimizing the total weighted completion time is shown to be NP-hard in the strong sense. Two pseudopolynomial dynamic programming algorithms are presented for minimizing the weighted number of late jobs. Minimizing the number of late jobs is proved to be NP-hard even if setup times are equal and there are two distinct due dates. This problem is solved in O(n3) time when all job processing times on the first machine are equal, and it is solved in O(n4) time when all processing times on the second machine are equal.
URI: http://hdl.handle.net/10397/21752
ISSN: 0010-485X
EISSN: 1436-5057
DOI: 10.1007/s00607-002-1467-8
Appears in Collections:Journal/Magazine Article

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

SCOPUSTM   
Citations

11
Last Week
0
Last month
0
Citations as of Sep 15, 2017

WEB OF SCIENCETM
Citations

7
Last Week
0
Last month
0
Citations as of Sep 14, 2017

Page view(s)

52
Last Week
1
Last month
Checked on Sep 18, 2017

Google ScholarTM

Check

Altmetric



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