Chen, Lin ORCID: 0000-0003-3909-4916, Eberle, Franziska ORCID: 0000-0001-8636-9711, Megow, Nicole ORCID: 0000-0002-3531-7644, Schewior, Kevin ORCID: 0000-0003-2236-0210 and Stein, Cliff (2020). A general framework for handling commitment in online throughput maximization. Math. Program., 183 (1-2). S. 215 - 248. HEIDELBERG: SPRINGER HEIDELBERG. ISSN 1436-4646

Full text not available from this repository.

Abstract

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+epsilon times its processing time, for some epsilon>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 O(1/epsilon) 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 O(epsilon/((epsilon-delta)delta(2))), for 0<delta<epsilon. When a provider must commit upon starting a job, our bound is O(1/epsilon(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.

Item Type: Journal Article
Creators:
CreatorsEmailORCIDORCID Put Code
Chen, LinUNSPECIFIEDorcid.org/0000-0003-3909-4916UNSPECIFIED
Eberle, FranziskaUNSPECIFIEDorcid.org/0000-0001-8636-9711UNSPECIFIED
Megow, NicoleUNSPECIFIEDorcid.org/0000-0002-3531-7644UNSPECIFIED
Schewior, KevinUNSPECIFIEDorcid.org/0000-0003-2236-0210UNSPECIFIED
Stein, CliffUNSPECIFIEDUNSPECIFIEDUNSPECIFIED
URN: urn:nbn:de:hbz:38-345576
DOI: 10.1007/s10107-020-01469-2
Journal or Publication Title: Math. Program.
Volume: 183
Number: 1-2
Page Range: S. 215 - 248
Date: 2020
Publisher: SPRINGER HEIDELBERG
Place of Publication: HEIDELBERG
ISSN: 1436-4646
Language: English
Faculty: Faculty of Mathematics and Natural Sciences
Divisions: Faculty of Mathematics and Natural Sciences > Department of Mathematics and Computer Science > Institute of Computer Science
Subjects: no entry
Uncontrolled Keywords:
KeywordsLanguage
ADMISSION CONTROL; ALGORITHM; DELAYMultiple languages
Computer Science, Software Engineering; Operations Research & Management Science; Mathematics, AppliedMultiple languages
Refereed: Yes
URI: http://kups.ub.uni-koeln.de/id/eprint/34557

Downloads

Downloads per month over past year

Altmetric

Export

Actions (login required)

View Item View Item