Online scheduling of weighted equal-length jobs with hard deadlines on parallel machines

Sven O. Krumke, Alfred Taudes, Stephan Westphal

Publikation: Wissenschaftliche FachzeitschriftOriginalbeitrag in FachzeitschriftBegutachtung

Abstract

We consider the problem of scheduling a maximum profit selection of equal length jobs on m identical machines. Jobs arrive online over time and the goal is to determine a non-preemptive schedule which maximizes the total profit of the scheduled jobs. Let the common processing requirement of the jobs be p>0. For each job j_i, i=1...,n we are given a release time r_i (at which the job becomes known) and a deadline r_i+p+δ_i. If the job is scheduled and completed before the deadline, a profit of wi is earned.
Upon arrival of a new job, an online algorithm must decide whether to accept the job or not. In case of acceptance, the online algorithms must provide a feasible starting date for the job.

Competitive analysis has become a standard way of measuring the quality of online algorithms. For a maximization problem, an online algorithm is called c-competitive, if on every input instance it achieves at least a 1/c-fraction of the optimal (offline) profit.

We give lower bounds for the competitivity of online algorithms and propose algorithms which match this lower bound up to a constant factor.
OriginalspracheEnglisch
Seiten (von - bis)1103 - 1108
FachzeitschriftComputers and Operations Research
Jahrgang38
Ausgabenummer8
PublikationsstatusVeröffentlicht - 2011

Dieses zitieren