Projects per year
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.
Original language  English 

Pages (fromto)  1103  1108 
Journal  Computers and Operations Research 
Volume  38 
Issue number  8 
Publication status  Published  2011 
Projects
 1 Finished

Integrated Demand and Supply Chain Management
Taudes, A. (PI  Project head), Arikan Fichtinger, E. (Researcher), Fichtinger, J. (Researcher), GimplHeersink, L. (Researcher), Jammernegg, W. (Researcher), Mild, A. (Researcher), Quante, R. (Researcher), Reiner, G. (Researcher), Swaton, N. (Researcher) & Wöckl, J. (Researcher)
1/06/05 → 1/06/08
Project: Research funding