DC Field | Value | Language |
---|---|---|
dc.contributor.author | Choi, BC | - |
dc.contributor.author | Lee, K | - |
dc.contributor.author | Leung, JYT | - |
dc.contributor.author | Pinedo, ML | - |
dc.date.accessioned | 2017-07-19T12:45:20Z | - |
dc.date.available | 2017-07-19T12:45:20Z | - |
dc.date.created | 2016-07-12 | - |
dc.date.issued | 2010-11 | - |
dc.identifier.issn | 0377-2217 | - |
dc.identifier.uri | https://oasis.postech.ac.kr/handle/2014.oak/36385 | - |
dc.description.abstract | We consider the m-machine ordered flow shop scheduling problem with machines subject to maintenance and with the makespan as objective. It is assumed that the maintenances are scheduled in advance and that the jobs are resumable. We consider permutation schedules and show that the problem is strongly NP-hard; it remains NP-hard in the ordinary sense even in the case of a single maintenance. We show that if the first (last) machine is the slowest and if maintenances occur only on the first (last) machine, then sequencing the jobs in the LPT (SPT) order yields an optimal schedule for the m-machine problem. As a special case of the ordered flow shop, we focus on the proportionate flow shop where the processing times of any given job on all the machines are identical. We prove that the proportionate flow shop problem with two maintenance periods is NP-hard, while the problem with a single maintenance period can be solved in polynomial time. Furthermore, we show that the optimal algorithm for the single maintenance case is a 3/2-approximation algorithm for the two maintenance case. In our conclusion we discuss also the computational complexity of other objective functions. (C) 2010 Elsevier B.V. All rights reserved. | - |
dc.language | English | - |
dc.publisher | ELSEVIER SCIENCE BV | - |
dc.relation.isPartOf | EUROPEAN JOURNAL OF OPERATIONAL RESEARCH | - |
dc.title | Flow Shops with Machine Maintenance: Ordered and Proportionate Cases | - |
dc.type | Article | - |
dc.identifier.doi | 10.1016/J.EJOR.2010.04.018 | - |
dc.type.rims | ART | - |
dc.identifier.bibliographicCitation | EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, v.207, no.1, pp.97 - 104 | - |
dc.identifier.wosid | 000280220100013 | - |
dc.date.tcdate | 2019-02-01 | - |
dc.citation.endPage | 104 | - |
dc.citation.number | 1 | - |
dc.citation.startPage | 97 | - |
dc.citation.title | EUROPEAN JOURNAL OF OPERATIONAL RESEARCH | - |
dc.citation.volume | 207 | - |
dc.contributor.affiliatedAuthor | Lee, K | - |
dc.identifier.scopusid | 2-s2.0-77953870363 | - |
dc.description.journalClass | 1 | - |
dc.description.journalClass | 1 | - |
dc.description.wostc | 8 | - |
dc.description.scptc | 7 | * |
dc.date.scptcdate | 2018-05-121 | * |
dc.description.isOpenAccess | N | - |
dc.type.docType | Article | - |
dc.subject.keywordPlus | PROCESSING TIME MATRICES | - |
dc.subject.keywordPlus | 2-MACHINE FLOWSHOP | - |
dc.subject.keywordPlus | AVAILABILITY CONSTRAINT | - |
dc.subject.keywordPlus | SCHEDULING PROBLEM | - |
dc.subject.keywordPlus | COMPLETION-TIME | - |
dc.subject.keywordPlus | SEQUENCING PROBLEM | - |
dc.subject.keywordPlus | MAKESPAN | - |
dc.subject.keywordPlus | SPEEDS | - |
dc.subject.keywordAuthor | Ordered flow shop | - |
dc.subject.keywordAuthor | Proportionate flow shop | - |
dc.subject.keywordAuthor | Maintenance | - |
dc.subject.keywordAuthor | Computational complexity | - |
dc.subject.keywordAuthor | Approximation algorithm | - |
dc.relation.journalWebOfScienceCategory | Management | - |
dc.relation.journalWebOfScienceCategory | Operations Research & Management Science | - |
dc.description.journalRegisteredClass | scie | - |
dc.description.journalRegisteredClass | scopus | - |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.
library@postech.ac.kr Tel: 054-279-2548
Copyrights © by 2017 Pohang University of Science ad Technology All right reserved.