File Download
There are no files associated with this item.
Supplementary

Citations:
 Scopus: 0
 Appears in Collections:
Article: Competitive algorithms for due date scheduling
Title  Competitive algorithms for due date scheduling 

Authors  
Keywords  Online algorithms Scheduling Competitive analysis Due dates Supply chain 
Issue Date  2007 
Publisher  Springer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/ 
Citation  Lecture Notes In Computer Science (Including Subseries Lecture Notes In Artificial Intelligence And Lecture Notes In Bioinformatics), 2007, v. 4596 LNCS, p. 2839 How to Cite? 
Abstract  We consider several online scheduling problems that arise when customers request maketoorder 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 nonincreasing 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 polylogcompetitive 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. © SpringerVerlag Berlin Heidelberg 2007. 
Persistent Identifier  http://hdl.handle.net/10722/140803 
ISSN  2005 Impact Factor: 0.402 2015 SCImago Journal Rankings: 0.252 
References 
DC Field  Value  Language 

dc.contributor.author  Bansal, N  en_HK 
dc.contributor.author  Chan, HL  en_HK 
dc.contributor.author  Pruhs, K  en_HK 
dc.date.accessioned  20110923T06:19:31Z   
dc.date.available  20110923T06:19:31Z   
dc.date.issued  2007  en_HK 
dc.identifier.citation  Lecture Notes In Computer Science (Including Subseries Lecture Notes In Artificial Intelligence And Lecture Notes In Bioinformatics), 2007, v. 4596 LNCS, p. 2839  en_HK 
dc.identifier.issn  03029743  en_HK 
dc.identifier.uri  http://hdl.handle.net/10722/140803   
dc.description.abstract  We consider several online scheduling problems that arise when customers request maketoorder 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 nonincreasing 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 polylogcompetitive 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. © SpringerVerlag Berlin Heidelberg 2007.  en_HK 
dc.language  eng  en_US 
dc.publisher  Springer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/  en_HK 
dc.relation.ispartof  Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)  en_HK 
dc.rights  The original publication is available at www.springerlink.com   
dc.subject  Online algorithms   
dc.subject  Scheduling   
dc.subject  Competitive analysis   
dc.subject  Due dates   
dc.subject  Supply chain   
dc.title  Competitive algorithms for due date scheduling  en_HK 
dc.type  Article  en_HK 
dc.identifier.openurl  http://library.hku.hk:4550/resserv?sid=HKU:IR&issn=01784617&volume=59&issue=4&spage=569&epage=582&date=2009&atitle=Competitive+algorithms+for+due+date+scheduling   
dc.identifier.email  Chan, HL:hlchan@cs.hku.hk  en_HK 
dc.identifier.authority  Chan, HL=rp01310  en_HK 
dc.description.nature  link_to_subscribed_fulltext   
dc.identifier.scopus  eid_2s2.038149066605  en_HK 
dc.identifier.hkuros  194065  en_US 
dc.relation.references  http://www.scopus.com/mlt/select.url?eid=2s2.038149066605&selection=ref&src=s&origin=recordpage  en_HK 
dc.identifier.volume  4596 LNCS  en_HK 
dc.identifier.issue  4  en_US 
dc.identifier.spage  28  en_HK 
dc.identifier.epage  39  en_HK 
dc.publisher.place  Germany  en_HK 
dc.identifier.scopusauthorid  Bansal, N=7102714084  en_HK 
dc.identifier.scopusauthorid  Chan, HL=7403402384  en_HK 
dc.identifier.scopusauthorid  Pruhs, K=6603866438  en_HK 