3중기계 오픈샵 문제에서의 Makespan 최소화
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Inna Drobouchevitch | - |
dc.date.accessioned | 2021-09-04T06:56:49Z | - |
dc.date.available | 2021-09-04T06:56:49Z | - |
dc.date.created | 2021-06-17 | - |
dc.date.issued | 2016 | - |
dc.identifier.issn | 1229-831X | - |
dc.identifier.uri | https://scholar.korea.ac.kr/handle/2021.sw.korea/90847 | - |
dc.description.abstract | The paper considers the three-machine open shop scheduling problem to minimize the makespan, i.e., the maximum completion time (O3||Cmax). The open shop problem was introduced by Gonzalez and Sahni who gave a polynomial time algorithm for its solution in the case of two machines. They also proved that this problem is NP-hard in the case of three machines. In view of the problem complexity, it is an attractive research goal to search for the widest possible classes of problem instances which admit efficient solutions. Such problem classes can be formulated in terms of a certain relation between machine loads and maximum operation length. Let Li be the load (the total time of all operations) of the ith machine and let pmax be the maximum operation length. Suppose that the machines are numbered in the non-increasing order of their loads. The O3||Cmax problem is known to be polynomially solvable if L1-L3≥2pmax. In this paper, we show that the problem is ordinary NP-hard if 2L1-L2-L3< 2pmax. We then consider a special case of the O3||Cmax problem that lies outside the known NP-hardness bounds and show that it is solvable in linear time. | - |
dc.language | English | - |
dc.language.iso | en | - |
dc.publisher | 한국생산관리학회 | - |
dc.title | 3중기계 오픈샵 문제에서의 Makespan 최소화 | - |
dc.title.alternative | Three-machine Open Shop Problem with the Minimum Makespan Criterion | - |
dc.type | Article | - |
dc.contributor.affiliatedAuthor | Inna Drobouchevitch | - |
dc.identifier.doi | 10.21131/kopoms.27.1.201602.87 | - |
dc.identifier.bibliographicCitation | 한국생산관리학회지, v.27, no.1, pp.87 - 101 | - |
dc.relation.isPartOf | 한국생산관리학회지 | - |
dc.citation.title | 한국생산관리학회지 | - |
dc.citation.volume | 27 | - |
dc.citation.number | 1 | - |
dc.citation.startPage | 87 | - |
dc.citation.endPage | 101 | - |
dc.type.rims | ART | - |
dc.identifier.kciid | ART002083908 | - |
dc.description.journalClass | 2 | - |
dc.description.journalRegisteredClass | kci | - |
dc.subject.keywordAuthor | scheduling | - |
dc.subject.keywordAuthor | open shop | - |
dc.subject.keywordAuthor | machine load | - |
dc.subject.keywordAuthor | computational complexity | - |
dc.subject.keywordAuthor | 스케줄링 | - |
dc.subject.keywordAuthor | 오픈샵 | - |
dc.subject.keywordAuthor | 기계부하 | - |
dc.subject.keywordAuthor | 계산 복잡도 | - |
Items in ScholarWorks are protected by copyright, with all rights reserved, unless otherwise indicated.
(02841) 서울특별시 성북구 안암로 14502-3290-1114
COPYRIGHT © 2021 Korea University. All Rights Reserved.
Certain data included herein are derived from the © Web of Science of Clarivate Analytics. All rights reserved.
You may not copy or re-distribute this material in whole or in part without the prior written consent of Clarivate Analytics.