TY - GEN

T1 - Competitive algorithms for due date scheduling

AU - Bansal, N.

AU - Chan, H.L.

AU - Pruhs, K.R.

PY - 2007

Y1 - 2007

N2 - 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 nonincreasing profit function pi(t) associated with each job Ji. If the customer for job Ji is quoted a due date of di, then the profit obtained from completing this job by its due date is pi(di). 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.

AB - 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 nonincreasing profit function pi(t) associated with each job Ji. If the customer for job Ji is quoted a due date of di, then the profit obtained from completing this job by its due date is pi(di). 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.

U2 - 10.1007/978-3-540-73420-8_5

DO - 10.1007/978-3-540-73420-8_5

M3 - Conference contribution

SN - 3-540-73419-8

T3 - Lecture Notes in Computer Science

SP - 28

EP - 39

BT - Automata, Languages and Programming (34th International Colloquium, ICALP 2007, Wroclaw, Poland, July 9-13, 2007. Proceedings)

A2 - Arge, L.

A2 - Cachin, C.

A2 - Jurdzinski, T.

A2 - Tarlecki, A.

PB - Springer

CY - Berlin

ER -