Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/65937
PIRA download icon_1.1View/Download Full Text
DC FieldValueLanguage
dc.contributorDepartment of Logistics and Maritime Studiesen_US
dc.creatorLeung, JYTen_US
dc.creatorNg, CTen_US
dc.date.accessioned2017-05-22T02:09:28Z-
dc.date.available2017-05-22T02:09:28Z-
dc.identifier.issn0377-2217en_US
dc.identifier.urihttp://hdl.handle.net/10397/65937-
dc.language.isoenen_US
dc.publisherElsevieren_US
dc.rights© 2017 Elsevier B.V. All rights reserved.en_US
dc.rights© 2017. This manuscript version is made available under the CC-BY-NC-ND 4.0 license https://creativecommons.org/licenses/by-nc-nd/4.0/en_US
dc.rightsThe following publication Leung, J. Y., & Ng, C. T. (2017). Fast approximation algorithms for uniform machine scheduling with processing set restrictions. European Journal of Operational Research, 260(2), 507-513 is available at https://doi.org/10.1016/j.ejor.2017.01.013en_US
dc.subjectInclusive processing seten_US
dc.subjectMakespanen_US
dc.subjectSchedulingen_US
dc.subjectTree-hierarchical processing seten_US
dc.subjectUniform machinesen_US
dc.subjectWorst-case bounden_US
dc.titleFast approximation algorithms for uniform machine scheduling with processing set restrictionsen_US
dc.typeJournal/Magazine Articleen_US
dc.identifier.spage507en_US
dc.identifier.epage513en_US
dc.identifier.volume260en_US
dc.identifier.issue2en_US
dc.identifier.doi10.1016/j.ejor.2017.01.013en_US
dcterms.abstractWe consider the problem of nonpreemptively scheduling a set of independent jobs on a set of uniform machines, where each job has a set of machines to which it can be assigned. This kind of restriction is called the processing set restriction. In the literature there are many kinds of processing set restrictions that have been studied. In this paper we consider two kinds: the “inclusive processing set” and the “tree-hierarchical processing set”. Epstein and Levin (2011) have given Polynomial Time Approximation Schemes (PTAS) to solve both classes. However, the running times of their PTAS are rather high. In this paper, we give fast approximation algorithms for both cases and show that they both have a worst-case performance bound of 4/3. Moreover, we show that the bounds are achievable.en_US
dcterms.accessRightsopen accessen_US
dcterms.bibliographicCitationEuropean journal of operational research, 16 July 2017, v. 260, no. 2, p. 507-513en_US
dcterms.isPartOfEuropean journal of operational researchen_US
dcterms.issued2017-07-16-
dc.identifier.scopus2-s2.0-85009736114-
dc.identifier.ros2016003169-
dc.identifier.eissn1872-6860en_US
dc.identifier.rosgroupid2016003104-
dc.description.ros2016-2017 > Academic research: refereed > Publication in refereed journalen_US
dc.description.validate201804_a bcmaen_US
dc.description.oaAccepted Manuscripten_US
dc.identifier.FolderNumberLMS-0394-
dc.description.fundingSourceRGCen_US
dc.description.pubStatusPublisheden_US
dc.identifier.OPUS25114661-
Appears in Collections:Journal/Magazine Article
Files in This Item:
File Description SizeFormat 
Ng_Fast_Approximation_Algorithms.pdfPre-Published version691.21 kBAdobe PDFView/Open
Open Access Information
Status open access
File Version Final Accepted Manuscript
Access
View full-text via PolyU eLinks SFX Query
Show simple item record

Page views

53
Last Week
4
Last month
Citations as of Oct 2, 2022

Downloads

4
Citations as of Oct 2, 2022

SCOPUSTM   
Citations

5
Last Week
0
Last month
Citations as of Oct 6, 2022

WEB OF SCIENCETM
Citations

4
Last Week
0
Last month
Citations as of Oct 6, 2022

Google ScholarTM

Check

Altmetric


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