Projekte pro Jahr
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 nonpreemptive 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 ccompetitive, if on every input instance it achieves at least a 1/cfraction 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.
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 ccompetitive, if on every input instance it achieves at least a 1/cfraction 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.
Originalsprache  Englisch 

Seiten (von  bis)  1103  1108 
Fachzeitschrift  Computers and Operations Research 
Jahrgang  38 
Ausgabenummer  8 
Publikationsstatus  Veröffentlicht  2011 
Projekte
 1 Abgeschlossen

Integriertes Nachfrage und Lieferkettenmanagement
Taudes, A., Arikan Fichtinger, E., Fichtinger, J., GimplHeersink, L., Jammernegg, W., Mild, A., Quante, R., Reiner, G., Swaton, N. & Wöckl, J.
1/06/05 → 1/06/08
Projekt: Forschungsförderung