Approximation algorithms for single machine scheduling with one unavailability period
dc.contributor.author | Kacem, I. | |
dc.contributor.author | Haouari, Mohamed | |
dc.date.accessioned | 2012-05-28T13:11:25Z | |
dc.date.available | 2012-05-28T13:11:25Z | |
dc.date.issued | 2009-03 | |
dc.identifier.issn | 1619-4500 | |
dc.identifier.uri | http://hdl.handle.net/10679/175 | |
dc.identifier.uri | http://www.springerlink.com/content/x118pg4055027649/ | |
dc.description | Due to copyright restrictions, the access to the full text of this article is only available via subscription. | |
dc.description.abstract | In this paper, we investigate the single machine scheduling problem with release dates and tails and a planned unavailability time period. We show that the problem admits a fully polynomial-time approximation scheme when the tails are equal. We derive an approximation algorithm for the general case and we show that the worst-case bound of the sequence yielded by Schrage’s algorithm is equal to 2 and that this bound is tight. Some consequences of this result are also presented. | en_US |
dc.description.sponsorship | Conseil Général Champagne-Ardenne | |
dc.language.iso | eng | en_US |
dc.publisher | Springer Nature | en_US |
dc.relation.ispartof | 4OR: A Quarterly Journal of Operations Research | |
dc.rights | restrictedAccess | |
dc.title | Approximation algorithms for single machine scheduling with one unavailability period | en_US |
dc.type | Article | en_US |
dc.peerreviewed | yes | en_US |
dc.publicationstatus | published | en_US |
dc.contributor.department | Özyeğin University | |
dc.contributor.authorID | (ORCID 0000-0003-0767-8220 & YÖK ID ) Haouari, Mohamed | |
dc.contributor.ozuauthor | Haouari, Mohamed | |
dc.identifier.volume | 7 | |
dc.identifier.issue | 1 | |
dc.identifier.startpage | 79 | |
dc.identifier.endpage | 92 | |
dc.identifier.wos | WOS:000264830600007 | |
dc.identifier.doi | 10.1007/s10288-008-0076-6 | |
dc.subject.keywords | Scheduling | en_US |
dc.subject.keywords | Single machine | en_US |
dc.subject.keywords | Approximation | en_US |
dc.subject.keywords | Unavailability constraint | en_US |
dc.identifier.scopus | SCOPUS:2-s2.0-63949087368 | |
dc.contributor.authorMale | 1 | |
dc.relation.publicationcategory | Article - International Refereed Journal - Institutional Academic Staff |
Files in this item
Files | Size | Format | View |
---|---|---|---|
There are no files associated with this item. |
This item appears in the following Collection(s)
Share this page