A General Framework for Handling Commitment in Online Throughput Maximization
| Autor: | Franziska Eberle, Kevin Schewior, Cliff Stein, Lin Chen, Nicole Megow |
|---|---|
| Přispěvatelé: | University of Houston, Universität Bremen, Département d'informatique - ENS Paris (DI-ENS), École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Technische Universität München = Technical University of Munich (TUM), Columbia University [New York] |
| Jazyk: | angličtina |
| Rok vydání: | 2019 |
| Předmět: |
FOS: Computer and information sciences
Discrete mathematics 050101 languages & linguistics Competitive analysis General Mathematics 05 social sciences [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS] 0102 computer and information sciences 02 engineering and technology Commit Throughput maximization 01 natural sciences Scheduling (computing) 010201 computation theory & mathematics Time windows Computer Science - Data Structures and Algorithms 0202 electrical engineering electronic engineering information engineering Data Structures and Algorithms (cs.DS) 020201 artificial intelligence & image processing 0501 psychology and cognitive sciences Online algorithm Software Mathematics |
| Zdroj: | Conference on Integer Programming and Combinatorial Optimization (IPCO) 2019 Conference on Integer Programming and Combinatorial Optimization (IPCO) 2019, May 2019, Ann Arbor, United States. pp.141-154, ⟨10.1007/978-3-030-17953-3_11⟩ Integer Programming and Combinatorial Optimization ISBN: 9783030179526 IPCO |
| Popis: | We study a fundamental online job admission problem where jobs with deadlines arrive online over time at their release dates, and the task is to determine a preemptive single-server schedule which maximizes the number of jobs that complete on time. To circumvent known impossibility results, we make a standard slackness assumption by which the feasible time window for scheduling a job is at least $$1+\varepsilon $$ 1 + ε times its processing time, for some $$\varepsilon >0$$ ε > 0 . We quantify the impact that different provider commitment requirements have on the performance of online algorithms. Our main contribution is one universal algorithmic framework for online job admission both with and without commitments. Without commitment, our algorithm with a competitive ratio of $$\mathcal {O}(1/\varepsilon )$$ O ( 1 / ε ) is the best possible (deterministic) for this problem. For commitment models, we give the first non-trivial performance bounds. If the commitment decisions must be made before a job’s slack becomes less than a $$\delta $$ δ -fraction of its size, we prove a competitive ratio of $$\mathcal {O}(\varepsilon /((\varepsilon -\delta )\delta ^2))$$ O ( ε / ( ( ε - δ ) δ 2 ) ) , for $$0 0 < δ < ε . When a provider must commit upon starting a job, our bound is $$\mathcal {O}(1/\varepsilon ^2)$$ O ( 1 / ε 2 ) . Finally, we observe that for scheduling with commitment the restriction to the “unweighted” throughput model is essential; if jobs have individual weights, we rule out competitive deterministic algorithms. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|