Home
Scholarly Works
Time-sharing scheduling with tolerance capacities
Journal article

Time-sharing scheduling with tolerance capacities

Abstract

Motivated by time-sharing systems with deadlines, we introduce the study of the following problem. We are given m machines and n jobs, as well as a set of tolerance capacities u i j ≥ 0 for every job j and machine i. Can we assign the jobs so that, if job j ends up on machine i, the total size of jobs that are processed on i is at most u i j ? We define two natural optimization versions: (i) Maximize the total weight of jobs that can be assigned without violating the tolerance capacities. (ii) Minimize the amount ρ ≥ 1 by which capacities have to be scaled so that all jobs can be assigned. For (i), we provide constant-factor approximations even in the presence of additional side-constraints. For (ii), we provide a strong inapproximability result and integrality gap lower bounds for two key relaxations.

Authors

Karakostas G; Kolliopoulos SG

Journal

Journal of Computer and System Sciences, Vol. 148, ,

Publisher

Elsevier

Publication Date

March 1, 2025

DOI

10.1016/j.jcss.2024.103605

ISSN

0022-0000

Contact the Experts team