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.
BibTeX
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.
Tags
Press 'enter' for creating the tagPublication'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 |
Associations
- Projects
- Integrated Demand and Supply Chain Management
- People
- Taudes, Alfred (Details)
- External
- Krumke, Sven O. (Universität Kaiserlautern, Germany)
- Westphal, Stephan (Universität Kaiserslautern, Germany)
- Organization
- Institute for Production Management (Taudes) (Details)
- Research Institute for Supply Chain Management FI (Details)