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 |
Show full item record
SCOPUSTM
Citations
11
Last Week
0
0
Last month
0
0
Citations as of Feb 9, 2019
WEB OF SCIENCETM
Citations
7
Last Week
0
0
Last month
0
0
Citations as of Feb 16, 2019
Page view(s)
77
Last Week
1
1
Last month
Citations as of Feb 18, 2019

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