caa a22 4500 445804947 CHVBK 20180317145153.0 cr unu---uuuuu 170323e20110401xx s 000 0 eng 10.1007/s00453-009-9321-4 doi (NATIONALLICENCE)springer-10.1007/s00453-009-9321-4 Competitive Algorithms for Due Date Scheduling [Elektronische Daten] [Nikhil Bansal, Ho-Leung Chan, Kirk Pruhs] 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(\frac{\log k}{\epsilon})$ -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 Science+Business Media, LLC, 2009 Online algorithms nationallicence Scheduling nationallicence Competitive analysis nationallicence Due dates nationallicence Supply chain nationallicence Bansal Nikhil IBM T.J. Watson Research, P.O. Box 218, Yorktown Heights, NY, USA aut Chan Ho-Leung Max-Planck-Institut für Informatik, Saarbrücken, Germany aut Pruhs Kirk Computer Science Department, University of Pittsburgh, Pittsburgh, PA, USA aut Algorithmica Springer-Verlag 59/4(2011-04-01), 569-582 0178-4617 59:4<569 2011 59 453 https://doi.org/10.1007/s00453-009-9321-4 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00453-009-9321-4 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Bansal Nikhil IBM T.J. Watson Research, P.O. Box 218, Yorktown Heights, NY, USA aut NATIONALLICENCE 700 1- Chan Ho-Leung Max-Planck-Institut für Informatik, Saarbrücken, Germany aut NATIONALLICENCE 700 1- Pruhs Kirk Computer Science Department, University of Pittsburgh, Pittsburgh, PA, USA aut NATIONALLICENCE 773 0- Algorithmica Springer-Verlag 59/4(2011-04-01), 569-582 0178-4617 59:4<569 2011 59 453 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer