Improved Scheduling with a Shared Resource via Structural Insights

Christoph Damerius; Peter Kling; Minming Li; Florian Schneider; Ruilong Zhang

doi:10.1007/978-3-030-64843-5_12

Improved Scheduling with a Shared Resource via Structural Insights

Christoph Damerius^*
, Peter Kling
, Minming Li
, Florian Schneider
, Ruilong Zhang

^*Corresponding author for this work

Department of Computer Science

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

1 Citation (Scopus)

Abstract

We consider a scheduling problem with resource-dependent processing speeds in which n jobs have to be scheduled on m machines that share a common resource. The resource may be distributed arbitrarily among the machines. This distribution is under the control of the scheduler and can be changed over time. Each job j has a processing volume p_j∈ N and a resource requirement r_j∈ (0, 1 ]. The latter indicates what fraction of the resource a job requires to run at full speed. Providing it with a larger share is not beneficial, but lowering its share results in a proportionally lowered processing speed. The goal is to schedule all jobs non-preemptively while minimizing the latest completion time.
This problem was introduced by Kling et al. [SPAA’17], who proved NP-hardness and gave an efficient algorithm with approximation ratio 2 + 1/(m - 2). The (asymptotic) tightness of that bound was left as an open question. We focus on the case of two machines and derive a strong, structural lower bound. This lower bound is based on a relaxed version and allows us to design an asymptotic 3/2-approximation that runs in time O (n· log n). As an immediate consequence we also get an improved 9/4-approximation for the case of three machines.

Original language	English
Title of host publication	Combinatorial Optimization and Applications
Subtitle of host publication	14th International Conference, COCOA 2020, Proceedings
Editors	Weili Wu, Zhongnan Zhang
Publisher	Springer Nature
Pages	168-182
ISBN (Electronic)	978-3-030-64843-5
ISBN (Print)	978-3-030-64842-8
DOIs	https://doi.org/10.1007/978-3-030-64843-5_12
Publication status	Published - Dec 2020
Event	14th International Conference on Combinatorial Optimization and Applications, COCOA 2020 - Virtual, Dallas, United States Duration: 11 Dec 2020 → 13 Dec 2020 https://theory.utdallas.edu/COCOA2020/index.html

Publication series

Name	Lecture Notes in Computer Science (including subseries Theoretical Computer Science and General Issues)
Volume	12577
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	14th International Conference on Combinatorial Optimization and Applications, COCOA 2020
Place	United States
City	Dallas
Period	11/12/20 → 13/12/20
Internet address	https://theory.utdallas.edu/COCOA2020/index.html

Bibliographical note

Full text of this publication does not contain sufficient affiliation information. With consent from the author(s) concerned, the Research Unit(s) information for this record is based on the existing academic department affiliation of the author(s).

Research Keywords

Approximation algorithm
Makespan
Multiprocessor scheduling
Relaxation
Resource constraints
Shared resource

Access Output

10.1007/978-3-030-64843-5_12

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

Damerius, C., Kling, P., Li, M., Schneider, F., & Zhang, R. (2020). Improved Scheduling with a Shared Resource via Structural Insights. In W. Wu, & Z. Zhang (Eds.), Combinatorial Optimization and Applications: 14th International Conference, COCOA 2020, Proceedings (pp. 168-182). (Lecture Notes in Computer Science (including subseries Theoretical Computer Science and General Issues); Vol. 12577). Springer Nature. https://doi.org/10.1007/978-3-030-64843-5_12

Damerius, Christoph ; Kling, Peter ; Li, Minming et al. / Improved Scheduling with a Shared Resource via Structural Insights. Combinatorial Optimization and Applications: 14th International Conference, COCOA 2020, Proceedings. editor / Weili Wu ; Zhongnan Zhang. Springer Nature, 2020. pp. 168-182 (Lecture Notes in Computer Science (including subseries Theoretical Computer Science and General Issues)).

@inproceedings{6bbfaa18ac3a463ab157d5d649896f72,

title = "Improved Scheduling with a Shared Resource via Structural Insights",

abstract = "We consider a scheduling problem with resource-dependent processing speeds in which n jobs have to be scheduled on m machines that share a common resource. The resource may be distributed arbitrarily among the machines. This distribution is under the control of the scheduler and can be changed over time. Each job j has a processing volume pj ∈ N and a resource requirement rj ∈ (0, 1 ]. The latter indicates what fraction of the resource a job requires to run at full speed. Providing it with a larger share is not beneficial, but lowering its share results in a proportionally lowered processing speed. The goal is to schedule all jobs non-preemptively while minimizing the latest completion time. This problem was introduced by Kling et al. [SPAA{\textquoteright}17], who proved NP-hardness and gave an efficient algorithm with approximation ratio 2 + 1/(m - 2). The (asymptotic) tightness of that bound was left as an open question. We focus on the case of two machines and derive a strong, structural lower bound. This lower bound is based on a relaxed version and allows us to design an asymptotic 3/2-approximation that runs in time O (n· log n). As an immediate consequence we also get an improved 9/4-approximation for the case of three machines.",

keywords = "Approximation algorithm, Makespan, Multiprocessor scheduling, Relaxation, Resource constraints, Shared resource",

author = "Christoph Damerius and Peter Kling and Minming Li and Florian Schneider and Ruilong Zhang",

note = "Full text of this publication does not contain sufficient affiliation information. With consent from the author(s) concerned, the Research Unit(s) information for this record is based on the existing academic department affiliation of the author(s).; 14th International Conference on Combinatorial Optimization and Applications, COCOA 2020 ; Conference date: 11-12-2020 Through 13-12-2020",

year = "2020",

month = dec,

doi = "10.1007/978-3-030-64843-5\_12",

language = "English",

isbn = "978-3-030-64842-8",

series = "Lecture Notes in Computer Science (including subseries Theoretical Computer Science and General Issues)",

publisher = "Springer Nature",

pages = "168--182",

editor = "Weili Wu and Zhongnan Zhang",

booktitle = "Combinatorial Optimization and Applications",

url = "https://theory.utdallas.edu/COCOA2020/index.html",

}

Damerius, C, Kling, P, Li, M, Schneider, F & Zhang, R 2020, Improved Scheduling with a Shared Resource via Structural Insights. in W Wu & Z Zhang (eds), Combinatorial Optimization and Applications: 14th International Conference, COCOA 2020, Proceedings. Lecture Notes in Computer Science (including subseries Theoretical Computer Science and General Issues), vol. 12577, Springer Nature, pp. 168-182, 14th International Conference on Combinatorial Optimization and Applications, COCOA 2020, Dallas, Texas, United States, 11/12/20. https://doi.org/10.1007/978-3-030-64843-5_12

Improved Scheduling with a Shared Resource via Structural Insights. / Damerius, Christoph; Kling, Peter; Li, Minming et al.
Combinatorial Optimization and Applications: 14th International Conference, COCOA 2020, Proceedings. ed. / Weili Wu; Zhongnan Zhang. Springer Nature, 2020. p. 168-182 (Lecture Notes in Computer Science (including subseries Theoretical Computer Science and General Issues); Vol. 12577).

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

TY - GEN

T1 - Improved Scheduling with a Shared Resource via Structural Insights

AU - Damerius, Christoph

AU - Kling, Peter

AU - Li, Minming

AU - Schneider, Florian

AU - Zhang, Ruilong

N1 - Full text of this publication does not contain sufficient affiliation information. With consent from the author(s) concerned, the Research Unit(s) information for this record is based on the existing academic department affiliation of the author(s).

PY - 2020/12

Y1 - 2020/12

N2 - We consider a scheduling problem with resource-dependent processing speeds in which n jobs have to be scheduled on m machines that share a common resource. The resource may be distributed arbitrarily among the machines. This distribution is under the control of the scheduler and can be changed over time. Each job j has a processing volume pj ∈ N and a resource requirement rj ∈ (0, 1 ]. The latter indicates what fraction of the resource a job requires to run at full speed. Providing it with a larger share is not beneficial, but lowering its share results in a proportionally lowered processing speed. The goal is to schedule all jobs non-preemptively while minimizing the latest completion time. This problem was introduced by Kling et al. [SPAA’17], who proved NP-hardness and gave an efficient algorithm with approximation ratio 2 + 1/(m - 2). The (asymptotic) tightness of that bound was left as an open question. We focus on the case of two machines and derive a strong, structural lower bound. This lower bound is based on a relaxed version and allows us to design an asymptotic 3/2-approximation that runs in time O (n· log n). As an immediate consequence we also get an improved 9/4-approximation for the case of three machines.

AB - We consider a scheduling problem with resource-dependent processing speeds in which n jobs have to be scheduled on m machines that share a common resource. The resource may be distributed arbitrarily among the machines. This distribution is under the control of the scheduler and can be changed over time. Each job j has a processing volume pj ∈ N and a resource requirement rj ∈ (0, 1 ]. The latter indicates what fraction of the resource a job requires to run at full speed. Providing it with a larger share is not beneficial, but lowering its share results in a proportionally lowered processing speed. The goal is to schedule all jobs non-preemptively while minimizing the latest completion time. This problem was introduced by Kling et al. [SPAA’17], who proved NP-hardness and gave an efficient algorithm with approximation ratio 2 + 1/(m - 2). The (asymptotic) tightness of that bound was left as an open question. We focus on the case of two machines and derive a strong, structural lower bound. This lower bound is based on a relaxed version and allows us to design an asymptotic 3/2-approximation that runs in time O (n· log n). As an immediate consequence we also get an improved 9/4-approximation for the case of three machines.

KW - Approximation algorithm

KW - Makespan

KW - Multiprocessor scheduling

KW - Relaxation

KW - Resource constraints

KW - Shared resource

UR - https://www.scopus.com/pages/publications/85097807006

UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-85097807006&origin=recordpage

U2 - 10.1007/978-3-030-64843-5_12

DO - 10.1007/978-3-030-64843-5_12

M3 - RGC 32 - Refereed conference paper (with host publication)

SN - 978-3-030-64842-8

T3 - Lecture Notes in Computer Science (including subseries Theoretical Computer Science and General Issues)

SP - 168

EP - 182

BT - Combinatorial Optimization and Applications

A2 - Wu, Weili

A2 - Zhang, Zhongnan

PB - Springer Nature

T2 - 14th International Conference on Combinatorial Optimization and Applications, COCOA 2020

Y2 - 11 December 2020 through 13 December 2020

ER -

Damerius C, Kling P, Li M, Schneider F, Zhang R. Improved Scheduling with a Shared Resource via Structural Insights. In Wu W, Zhang Z, editors, Combinatorial Optimization and Applications: 14th International Conference, COCOA 2020, Proceedings. Springer Nature. 2020. p. 168-182. (Lecture Notes in Computer Science (including subseries Theoretical Computer Science and General Issues)). doi: 10.1007/978-3-030-64843-5_12

Improved Scheduling with a Shared Resource via Structural Insights

Abstract

Publication series

Conference

Bibliographical note

Research Keywords

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this