Name
Title | ||
|---|---|---|
Online scheduling of weighted equal-length jobs with hard deadlines on parallel machines |
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 p0. 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+@d"i. If the job is scheduled and completed before the deadline, a profit of w"i 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. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1016/j.cor.2010.10.012 | Computers & OR |
Keywords | DocType | Volume |
maximization problem,release time,Revenue management,weighted equal-length job,new job,Online scheduling,lower bound,total profit,maximum profit selection,equal length job,hard deadline,online algorithm,Scheduling,job j,scheduled job,parallel machine,On-line algorithms,Competitiveness | Journal | 38 |
Issue | ISSN | Citations |
8 | Computers and Operations Research | 3 |
PageRank | References | Authors |
0.42 | 5 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Sven O. Krumke | 1 | 308 | 36.62 |
| Alfred Taudes | 2 | 243 | 31.43 |
| Stephan Westphal | 3 | 97 | 13.41 |