There are no files associated with this item.

##### Supplementary
• Appears in Collections:

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

Title Competitive algorithms for due date scheduling Bansal, NChan, HLPruhs, K Online algorithmsSchedulingCompetitive analysisDue datesSupply chain 2007 Springer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/ Lecture Notes In Computer Science (Including Subseries Lecture Notes In Artificial Intelligence And Lecture Notes In Bioinformatics), 2007, v. 4596 LNCS, p. 28-39 How to Cite? We 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. © Springer-Verlag Berlin Heidelberg 2007. http://hdl.handle.net/10722/140803 0302-97432005 Impact Factor: 0.3022015 SCImago Journal Rankings: 0.252 References in Scopus

DC FieldValueLanguage
dc.contributor.authorBansal, Nen_HK
dc.contributor.authorChan, HLen_HK
dc.contributor.authorPruhs, Ken_HK
dc.date.accessioned2011-09-23T06:19:31Z-
dc.date.available2011-09-23T06:19:31Z-
dc.date.issued2007en_HK
dc.identifier.citationLecture Notes In Computer Science (Including Subseries Lecture Notes In Artificial Intelligence And Lecture Notes In Bioinformatics), 2007, v. 4596 LNCS, p. 28-39en_HK
dc.identifier.issn0302-9743en_HK
dc.identifier.urihttp://hdl.handle.net/10722/140803-
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. © Springer-Verlag Berlin Heidelberg 2007.en_HK
dc.languageengen_US
dc.publisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/en_HK
dc.relation.ispartofLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)en_HK
dc.rightsThe original publication is available at www.springerlink.com-
dc.subjectOnline algorithms-
dc.subjectScheduling-
dc.subjectCompetitive analysis-
dc.subjectDue dates-
dc.subjectSupply chain-
dc.titleCompetitive algorithms for due date schedulingen_HK
dc.typeArticleen_HK
dc.identifier.openurlhttp://library.hku.hk:4550/resserv?sid=HKU:IR&issn=0178-4617&volume=59&issue=4&spage=569&epage=582&date=2009&atitle=Competitive+algorithms+for+due+date+scheduling-
dc.identifier.emailChan, HL:hlchan@cs.hku.hken_HK
dc.identifier.authorityChan, HL=rp01310en_HK
dc.identifier.scopuseid_2-s2.0-38149066605en_HK
dc.identifier.hkuros194065en_US
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-38149066605&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume4596 LNCSen_HK
dc.identifier.issue4en_US
dc.identifier.spage28en_HK
dc.identifier.epage39en_HK
dc.publisher.placeGermanyen_HK
dc.identifier.scopusauthoridBansal, N=7102714084en_HK
dc.identifier.scopusauthoridChan, HL=7403402384en_HK
dc.identifier.scopusauthoridPruhs, K=6603866438en_HK