Quotation Krumke, Sven O., Taudes, Alfred, Westphal, Stephan. 2011. Online scheduling of weighted equal-length jobs with hard deadlines on parallel machines. Computers and Operations Research 38 (8): 1103-1108.




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.


Press 'enter' for creating the tag

Publication's profile

Status of publication Published
Affiliation WU
Type of publication Journal article
Journal Computers and Operations Research
Citation Index SCI
WU Journalrating 2009 A
WU-Journal-Rating new FIN-A, INF-A, STRAT-B, WH-B
Language English
Title Online scheduling of weighted equal-length jobs with hard deadlines on parallel machines
Volume 38
Number 8
Year 2011
Page from 1103
Page to 1108
Reviewed? Y


Integrated Demand and Supply Chain Management
Taudes, Alfred (Details)
Krumke, Sven O. (Universit├Ąt Kaiserlautern, Germany)
Westphal, Stephan (Universit├Ąt Kaiserslautern, Germany)
Institute for Production Management (Taudes) (Details)
Research Institute for Supply Chain Management FI (Details)
Google Scholar: Search