Name
Abstract | ||
|---|---|---|
We consider the problem of scheduling a maximum profit selection of jobs on m identical machines. Jobs arrive online one by one and each job is specified by its start and end time. The goal is to determine a non-preemptive schedule which maximizes the profit of the scheduled jobs, where the profit of a job is equal to its length. Upon arrival of a new job, an online algorithm must decide whether to accept the job ("admit the job") or not. If the job is accepted, the online algorithm must be able to reorganize its already existing schedule such that the new job can be processed together with all previously admitted jobs, however, the algorithm need not specify on which machine the job will eventually be run. Competitive analysis has become a standard way of measuring the quality of online algo- rithms. For a maximization problem, an online algorithm is called c-competitive, if on every input instance it achives at least a 1/c-fraction of the optimal ("offline") profit. We provide competitive algorithms and lower bounds on the competitive ratio for deterministic and ran- domized algorithms against an oblivious adversary. Our lower bound results essentially match (up to small constants factors) the competitive ratios achieved by our algorithms. |
Year | DOI | Keywords |
|---|---|---|
2013 | 10.1007/978-1-4020-9688-4_16 | preemptive scheduling,online algorithm,profitability |
Field | DocType | Citations |
Online algorithm,Job shop scheduling,Scheduling (computing),Computer science,Job stream,Operations research,Job scheduler,Deterministic algorithm,Job queue,Competitive analysis,Distributed computing | Conference | 0 |
PageRank | References | Authors |
0.34 | 18 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Sven O. Krumke | 1 | 308 | 36.62 |
| van stee | 2 | 490 | 39.87 |
| Stephan Westphal | 3 | 97 | 13.41 |