Please use this identifier to cite or link to this item:
http://hdl.handle.net/10397/1262
| Title: | Single-machine scheduling of multi-operation jobs without missing operations to minimize the total completion time | Authors: | Cheng, TCE Ng, CTD Yuan, JJ |
Issue Date: | 1-Dec-2008 | Source: | European journal of operational research, 1 Dec. 2008, v. 191, no. 2, p. 320-331 | Abstract: | We consider the problem of scheduling multi-operation jobs on a singe machine to minimize the total completion time. Each job consists of several operations that belong to different families. In a schedule each family of job operations may be processed as batches with each batch incurring a set-up time. A job is completed when all of its operations have been processed. We first show that the problem is strongly NP-hard even when the set-up times are common and each operation is not missing. When the operations have identical processing times and either the maximum set-up time is sufficiently small or the minimum set-up time is sufficiently large, the problem can be solved in polynomial time. We then consider the problem under the job-batch restriction in which the operations of each batch is partitioned into operation batches according to a partition of the jobs. We show that this case of the problem can be solved in polynomial time under a certain condition. | Keywords: | Scheduling Single machine Multi-operation jobs Job-batch restriction SPT-agreeability |
Publisher: | Elsevier | Journal: | European journal of operational research | ISSN: | 0377-2217 | EISSN: | 1872-6860 | DOI: | 10.1016/j.ejor.2007.08.019 | Rights: | European Journal of Operational Research © 2007 Elsevier B.V. The journal web site is located at http://www.sciencedirect.com. |
| Appears in Collections: | Journal/Magazine Article |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| Assembly_without(REVISED)_Final.pdf | Pre-published version | 178.31 kB | Adobe PDF | View/Open |
Access
View full-text via PolyU eLinks 
Page views
89
Last Week
0
0
Last month
Citations as of Jun 4, 2023
Downloads
154
Citations as of Jun 4, 2023
SCOPUSTM
Citations
4
Last Week
0
0
Last month
0
0
Citations as of Jun 1, 2023
WEB OF SCIENCETM
Citations
3
Last Week
0
0
Last month
0
0
Citations as of Jun 1, 2023
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.