There are no files associated with this item.

##### Supplementary
• Appears in Collections:

#### Article: Competitive algorithms for due date scheduling

TitleCompetitive algorithms for due date scheduling
Authors
KeywordsCompetitive Analysis
Due Dates
Online Algorithms
Scheduling
Supply Chain
Issue Date2011
PublisherSpringer New York LLC. The Journal's web site is located at http://link.springer.de/link/service/journals/00453/index.htm
Citation
Algorithmica (New York), 2011, v. 59 n. 4, p. 569-582 How to Cite?
AbstractWe consider several online scheduling problems that arise when customers request make-to-order products from a company. At the time of the order, the company must quote a due date to the customer. To satisfy the customer, the company must produce the good by the due date. The company must have an online algorithm with two components: The first component sets the due dates, and the second component schedules the resulting jobs with the goal of meeting the due dates. The most basic quality of service measure for a job is the quoted lead time, which is the difference between the due date and the release time. We first consider the basic problem of minimizing the average quoted lead time. We show that there is a (1+ε)-speed O(log k/ε)-competitive algorithm for this problem (here k is the ratio of the maximum work of a job to the minimum work of a job), and that this algorithm is essentially optimally competitive. This result extends to the case that each job has a weight and the objective is weighted quoted lead time. We then introduce the following general setting: there is a non-increasing profit function p i (t) associated with each job J i . If the customer for job J i is quoted a due date of d i, then the profit obtained from completing this job by its due date is p i (d i ). We consider the objective of maximizing profits. We show that if the company must finish each job by its due date, then there is no O(1)-speed poly-log-competitive algorithm. However, if the company can miss the due date of a job, at the cost of forgoing the profits from that job, then we show that there is a (1+ε)-speed O(1+1/ε)-competitive algorithm, and that this algorithm is essentially optimally competitive. © 2009 Springer Science+Business Media, LLC.
Persistent Identifierhttp://hdl.handle.net/10722/152480
ISSN
2015 Impact Factor: 0.795
2015 SCImago Journal Rankings: 0.898
ISI Accession Number ID
Funding AgencyGrant Number
NSFCNS-0325353
CCF-0448196
CCF-0514058
IIS-0534531
Funding Information:

The research of K. Pruhs was supported in part by NSF grants CNS-0325353, CCF-0448196, CCF-0514058 and IIS-0534531.

References

DC FieldValueLanguage
dc.contributor.authorBansal, Nen_US
dc.contributor.authorChan, HLen_US
dc.contributor.authorPruhs, Ken_US
dc.date.accessioned2012-06-26T06:39:31Z-
dc.date.available2012-06-26T06:39:31Z-
dc.date.issued2011en_US
dc.identifier.citationAlgorithmica (New York), 2011, v. 59 n. 4, p. 569-582en_US
dc.identifier.issn0178-4617en_US
dc.identifier.urihttp://hdl.handle.net/10722/152480-
dc.description.abstractWe consider several online scheduling problems that arise when customers request make-to-order products from a company. At the time of the order, the company must quote a due date to the customer. To satisfy the customer, the company must produce the good by the due date. The company must have an online algorithm with two components: The first component sets the due dates, and the second component schedules the resulting jobs with the goal of meeting the due dates. The most basic quality of service measure for a job is the quoted lead time, which is the difference between the due date and the release time. We first consider the basic problem of minimizing the average quoted lead time. We show that there is a (1+ε)-speed O(log k/ε)-competitive algorithm for this problem (here k is the ratio of the maximum work of a job to the minimum work of a job), and that this algorithm is essentially optimally competitive. This result extends to the case that each job has a weight and the objective is weighted quoted lead time. We then introduce the following general setting: there is a non-increasing profit function p i (t) associated with each job J i . If the customer for job J i is quoted a due date of d i, then the profit obtained from completing this job by its due date is p i (d i ). We consider the objective of maximizing profits. We show that if the company must finish each job by its due date, then there is no O(1)-speed poly-log-competitive algorithm. However, if the company can miss the due date of a job, at the cost of forgoing the profits from that job, then we show that there is a (1+ε)-speed O(1+1/ε)-competitive algorithm, and that this algorithm is essentially optimally competitive. © 2009 Springer Science+Business Media, LLC.en_US
dc.languageengen_US
dc.publisherSpringer New York LLC. The Journal's web site is located at http://link.springer.de/link/service/journals/00453/index.htmen_US
dc.relation.ispartofAlgorithmica (New York)en_US
dc.subjectCompetitive Analysisen_US
dc.subjectDue Datesen_US
dc.subjectOnline Algorithmsen_US
dc.subjectSchedulingen_US
dc.subjectSupply Chainen_US
dc.titleCompetitive algorithms for due date schedulingen_US
dc.typeArticleen_US
dc.identifier.emailChan, HL:hlchan@cs.hku.hken_US
dc.identifier.authorityChan, HL=rp01310en_US
dc.identifier.doi10.1007/s00453-009-9321-4en_US
dc.identifier.scopuseid_2-s2.0-81955163122en_US
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-81955163122&selection=ref&src=s&origin=recordpageen_US
dc.identifier.volume59en_US
dc.identifier.issue4en_US
dc.identifier.spage569en_US
dc.identifier.epage582en_US
dc.identifier.isiWOS:000287319100006-
dc.publisher.placeUnited Statesen_US
dc.identifier.scopusauthoridBansal, N=7102714084en_US
dc.identifier.scopusauthoridChan, HL=7403402384en_US
dc.identifier.scopusauthoridPruhs, K=6603866438en_US
dc.identifier.citeulike4519951-