---
_id: '50458'
abstract:
- lang: eng
text: AbstractConsider a set of jobs connected
to a directed acyclic task graph with a fixed source and sink. The edges of this
graph model precedence constraints and the jobs have to be scheduled with respect
to those. We introduce the server cloud scheduling problem, in which the jobs
have to be processed either on a single local machine or on one of infinitely
many cloud machines. For each job, processing times both on the server and in
the cloud are given. Furthermore, for each edge in the task graph, a communication
delay is included in the input and has to be taken into account if one of the
two jobs is scheduled on the server and the other in the cloud. The server processes
jobs sequentially, whereas the cloud can serve as many as needed in parallel,
but induces costs. We consider both makespan and cost minimization. The main results
are an FPTAS for the makespan objective for graphs with a constant source and
sink dividing cut and strong hardness for the case with unit processing times
and delays.
author:
- first_name: Marten
full_name: Maack, Marten
id: '88252'
last_name: Maack
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
- first_name: Simon
full_name: Pukrop, Simon
id: '44428'
last_name: Pukrop
citation:
ama: Maack M, Meyer auf der Heide F, Pukrop S. Server Cloud Scheduling. Algorithmica.
Published online 2023. doi:10.1007/s00453-023-01189-x
apa: Maack, M., Meyer auf der Heide, F., & Pukrop, S. (2023). Server Cloud Scheduling.
Algorithmica. https://doi.org/10.1007/s00453-023-01189-x
bibtex: '@article{Maack_Meyer auf der Heide_Pukrop_2023, title={Server Cloud Scheduling},
DOI={10.1007/s00453-023-01189-x},
journal={Algorithmica}, publisher={Springer Science and Business Media LLC}, author={Maack,
Marten and Meyer auf der Heide, Friedhelm and Pukrop, Simon}, year={2023} }'
chicago: Maack, Marten, Friedhelm Meyer auf der Heide, and Simon Pukrop. “Server
Cloud Scheduling.” Algorithmica, 2023. https://doi.org/10.1007/s00453-023-01189-x.
ieee: 'M. Maack, F. Meyer auf der Heide, and S. Pukrop, “Server Cloud Scheduling,”
Algorithmica, 2023, doi: 10.1007/s00453-023-01189-x.'
mla: Maack, Marten, et al. “Server Cloud Scheduling.” Algorithmica, Springer
Science and Business Media LLC, 2023, doi:10.1007/s00453-023-01189-x.
short: M. Maack, F. Meyer auf der Heide, S. Pukrop, Algorithmica (2023).
date_created: 2024-01-11T11:10:53Z
date_updated: 2024-01-11T11:19:33Z
department:
- _id: '63'
doi: 10.1007/s00453-023-01189-x
extern: '1'
keyword:
- Applied Mathematics
- Computer Science Applications
- General Computer Science
language:
- iso: eng
project:
- _id: '1'
grant_number: '160364472'
name: 'SFB 901: SFB 901: On-The-Fly Computing - Individualisierte IT-Dienstleistungen
in dynamischen Märkten '
- _id: '4'
name: 'SFB 901 - C: SFB 901 - Project Area C'
- _id: '16'
grant_number: '160364472'
name: 'SFB 901 - C4: SFB 901 - On-The-Fly Compute Centers II: Ausführung komponierter
Dienste in konfigurierbaren Rechenzentren (Subproject C4)'
publication: Algorithmica
publication_identifier:
issn:
- 0178-4617
- 1432-0541
publication_status: published
publisher: Springer Science and Business Media LLC
status: public
title: Server Cloud Scheduling
type: journal_article
user_id: '44428'
year: '2023'
...
---
_id: '50460'
author:
- first_name: Max A.
full_name: Deppert, Max A.
last_name: Deppert
- first_name: Klaus
full_name: Jansen, Klaus
last_name: Jansen
- first_name: Marten
full_name: Maack, Marten
id: '88252'
last_name: Maack
- first_name: Simon
full_name: Pukrop, Simon
id: '44428'
last_name: Pukrop
- first_name: Malin
full_name: Rau, Malin
last_name: Rau
citation:
ama: 'Deppert MA, Jansen K, Maack M, Pukrop S, Rau M. Scheduling with Many Shared
Resources. In: 2023 IEEE International Parallel and Distributed Processing
Symposium (IPDPS). IEEE; 2023. doi:10.1109/ipdps54959.2023.00049'
apa: Deppert, M. A., Jansen, K., Maack, M., Pukrop, S., & Rau, M. (2023). Scheduling
with Many Shared Resources. 2023 IEEE International Parallel and Distributed
Processing Symposium (IPDPS). https://doi.org/10.1109/ipdps54959.2023.00049
bibtex: '@inproceedings{Deppert_Jansen_Maack_Pukrop_Rau_2023, title={Scheduling
with Many Shared Resources}, DOI={10.1109/ipdps54959.2023.00049},
booktitle={2023 IEEE International Parallel and Distributed Processing Symposium
(IPDPS)}, publisher={IEEE}, author={Deppert, Max A. and Jansen, Klaus and Maack,
Marten and Pukrop, Simon and Rau, Malin}, year={2023} }'
chicago: Deppert, Max A., Klaus Jansen, Marten Maack, Simon Pukrop, and Malin Rau.
“Scheduling with Many Shared Resources.” In 2023 IEEE International Parallel
and Distributed Processing Symposium (IPDPS). IEEE, 2023. https://doi.org/10.1109/ipdps54959.2023.00049.
ieee: 'M. A. Deppert, K. Jansen, M. Maack, S. Pukrop, and M. Rau, “Scheduling with
Many Shared Resources,” 2023, doi: 10.1109/ipdps54959.2023.00049.'
mla: Deppert, Max A., et al. “Scheduling with Many Shared Resources.” 2023 IEEE
International Parallel and Distributed Processing Symposium (IPDPS), IEEE,
2023, doi:10.1109/ipdps54959.2023.00049.
short: 'M.A. Deppert, K. Jansen, M. Maack, S. Pukrop, M. Rau, in: 2023 IEEE International
Parallel and Distributed Processing Symposium (IPDPS), IEEE, 2023.'
date_created: 2024-01-11T11:30:14Z
date_updated: 2024-01-11T11:31:11Z
department:
- _id: '63'
doi: 10.1109/ipdps54959.2023.00049
language:
- iso: eng
project:
- _id: '1'
grant_number: '160364472'
name: 'SFB 901: SFB 901: On-The-Fly Computing - Individualisierte IT-Dienstleistungen
in dynamischen Märkten '
- _id: '4'
name: 'SFB 901 - C: SFB 901 - Project Area C'
- _id: '16'
grant_number: '160364472'
name: 'SFB 901 - C4: SFB 901 - On-The-Fly Compute Centers II: Ausführung komponierter
Dienste in konfigurierbaren Rechenzentren (Subproject C4)'
publication: 2023 IEEE International Parallel and Distributed Processing Symposium
(IPDPS)
publication_status: published
publisher: IEEE
status: public
title: Scheduling with Many Shared Resources
type: conference
user_id: '44428'
year: '2023'
...
---
_id: '45895'
author:
- first_name: Holger
full_name: Karl, Holger
id: '126'
last_name: Karl
- first_name: Marten
full_name: Maack, Marten
id: '88252'
last_name: Maack
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
- first_name: Simon
full_name: Pukrop, Simon
id: '44428'
last_name: Pukrop
- first_name: Adrian
full_name: Redder, Adrian
id: '52265'
last_name: Redder
orcid: https://orcid.org/0000-0001-7391-4688
citation:
ama: 'Karl H, Maack M, Meyer auf der Heide F, Pukrop S, Redder A. On-The-Fly Compute
Centers II: Execution of Composed Services in Configurable Compute Centers. In:
Haake C-J, Meyer auf der Heide F, Platzner M, Wachsmuth H, Wehrheim H, eds. On-The-Fly
Computing -- Individualized IT-Services in Dynamic Markets. Vol 412. Verlagsschriftenreihe
des Heinz Nixdorf Instituts. Heinz Nixdorf Institut, Universität Paderborn; 2023:183-202.
doi:10.5281/zenodo.8068664'
apa: 'Karl, H., Maack, M., Meyer auf der Heide, F., Pukrop, S., & Redder, A.
(2023). On-The-Fly Compute Centers II: Execution of Composed Services in Configurable
Compute Centers. In C.-J. Haake, F. Meyer auf der Heide, M. Platzner, H. Wachsmuth,
& H. Wehrheim (Eds.), On-The-Fly Computing -- Individualized IT-services
in dynamic markets (Vol. 412, pp. 183–202). Heinz Nixdorf Institut, Universität
Paderborn. https://doi.org/10.5281/zenodo.8068664'
bibtex: '@inbook{Karl_Maack_Meyer auf der Heide_Pukrop_Redder_2023, place={Paderborn},
series={Verlagsschriftenreihe des Heinz Nixdorf Instituts}, title={On-The-Fly
Compute Centers II: Execution of Composed Services in Configurable Compute Centers},
volume={412}, DOI={10.5281/zenodo.8068664},
booktitle={On-The-Fly Computing -- Individualized IT-services in dynamic markets},
publisher={Heinz Nixdorf Institut, Universität Paderborn}, author={Karl, Holger
and Maack, Marten and Meyer auf der Heide, Friedhelm and Pukrop, Simon and Redder,
Adrian}, editor={Haake, Claus-Jochen and Meyer auf der Heide, Friedhelm and Platzner,
Marco and Wachsmuth, Henning and Wehrheim, Heike}, year={2023}, pages={183–202},
collection={Verlagsschriftenreihe des Heinz Nixdorf Instituts} }'
chicago: 'Karl, Holger, Marten Maack, Friedhelm Meyer auf der Heide, Simon Pukrop,
and Adrian Redder. “On-The-Fly Compute Centers II: Execution of Composed Services
in Configurable Compute Centers.” In On-The-Fly Computing -- Individualized
IT-Services in Dynamic Markets, edited by Claus-Jochen Haake, Friedhelm Meyer
auf der Heide, Marco Platzner, Henning Wachsmuth, and Heike Wehrheim, 412:183–202.
Verlagsschriftenreihe Des Heinz Nixdorf Instituts. Paderborn: Heinz Nixdorf Institut,
Universität Paderborn, 2023. https://doi.org/10.5281/zenodo.8068664.'
ieee: 'H. Karl, M. Maack, F. Meyer auf der Heide, S. Pukrop, and A. Redder, “On-The-Fly
Compute Centers II: Execution of Composed Services in Configurable Compute Centers,”
in On-The-Fly Computing -- Individualized IT-services in dynamic markets,
vol. 412, C.-J. Haake, F. Meyer auf der Heide, M. Platzner, H. Wachsmuth, and
H. Wehrheim, Eds. Paderborn: Heinz Nixdorf Institut, Universität Paderborn, 2023,
pp. 183–202.'
mla: 'Karl, Holger, et al. “On-The-Fly Compute Centers II: Execution of Composed
Services in Configurable Compute Centers.” On-The-Fly Computing -- Individualized
IT-Services in Dynamic Markets, edited by Claus-Jochen Haake et al., vol.
412, Heinz Nixdorf Institut, Universität Paderborn, 2023, pp. 183–202, doi:10.5281/zenodo.8068664.'
short: 'H. Karl, M. Maack, F. Meyer auf der Heide, S. Pukrop, A. Redder, in: C.-J.
Haake, F. Meyer auf der Heide, M. Platzner, H. Wachsmuth, H. Wehrheim (Eds.),
On-The-Fly Computing -- Individualized IT-Services in Dynamic Markets, Heinz Nixdorf
Institut, Universität Paderborn, Paderborn, 2023, pp. 183–202.'
date_created: 2023-07-07T08:24:28Z
date_updated: 2023-07-07T11:16:53Z
ddc:
- '004'
department:
- _id: '7'
doi: 10.5281/zenodo.8068664
editor:
- first_name: Claus-Jochen
full_name: Haake, Claus-Jochen
last_name: Haake
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
last_name: Meyer auf der Heide
- first_name: Marco
full_name: Platzner, Marco
last_name: Platzner
- first_name: Henning
full_name: Wachsmuth, Henning
last_name: Wachsmuth
- first_name: Heike
full_name: Wehrheim, Heike
last_name: Wehrheim
file:
- access_level: open_access
content_type: application/pdf
creator: florida
date_created: 2023-07-07T08:24:20Z
date_updated: 2023-07-07T11:16:52Z
file_id: '45896'
file_name: C4-Chapter-SFB-Buch-Final.pdf
file_size: 1803186
relation: main_file
file_date_updated: 2023-07-07T11:16:52Z
has_accepted_license: '1'
intvolume: ' 412'
language:
- iso: eng
oa: '1'
page: 183-202
place: Paderborn
project:
- _id: '1'
grant_number: '160364472'
name: 'SFB 901: SFB 901: On-The-Fly Computing - Individualisierte IT-Dienstleistungen
in dynamischen Märkten '
- _id: '4'
name: 'SFB 901 - C: SFB 901 - Project Area C'
- _id: '16'
grant_number: '160364472'
name: 'SFB 901 - C4: SFB 901 - On-The-Fly Compute Centers II: Ausführung komponierter
Dienste in konfigurierbaren Rechenzentren (Subproject C4)'
publication: On-The-Fly Computing -- Individualized IT-services in dynamic markets
publisher: Heinz Nixdorf Institut, Universität Paderborn
series_title: Verlagsschriftenreihe des Heinz Nixdorf Instituts
status: public
title: 'On-The-Fly Compute Centers II: Execution of Composed Services in Configurable
Compute Centers'
type: book_chapter
user_id: '477'
volume: 412
year: '2023'
...
---
_id: '45781'
author:
- first_name: Simon
full_name: Pukrop, Simon
id: '44428'
last_name: Pukrop
citation:
ama: Pukrop S. On Cloud Assisted, Restricted, and Reosurce Constrained Scheduling.;
2023. doi:10.17619/UNIPB/1-1768
apa: Pukrop, S. (2023). On Cloud Assisted, Restricted, and Reosurce Constrained
Scheduling. https://doi.org/10.17619/UNIPB/1-1768
bibtex: '@book{Pukrop_2023, title={On Cloud Assisted, Restricted, and Reosurce Constrained
Scheduling}, DOI={10.17619/UNIPB/1-1768
}, author={Pukrop, Simon}, year={2023} }'
chicago: Pukrop, Simon. On Cloud Assisted, Restricted, and Reosurce Constrained
Scheduling, 2023. https://doi.org/10.17619/UNIPB/1-1768
.
ieee: S. Pukrop, On Cloud Assisted, Restricted, and Reosurce Constrained Scheduling.
2023.
mla: Pukrop, Simon. On Cloud Assisted, Restricted, and Reosurce Constrained Scheduling.
2023, doi:10.17619/UNIPB/1-1768
.
short: S. Pukrop, On Cloud Assisted, Restricted, and Reosurce Constrained Scheduling,
2023.
date_created: 2023-06-27T05:24:19Z
date_updated: 2023-07-14T09:27:44Z
department:
- _id: '63'
doi: '10.17619/UNIPB/1-1768 '
language:
- iso: eng
project:
- _id: '1'
grant_number: '160364472'
name: 'SFB 901: SFB 901: On-The-Fly Computing - Individualisierte IT-Dienstleistungen
in dynamischen Märkten '
- _id: '4'
name: 'SFB 901 - C: SFB 901 - Project Area C'
- _id: '16'
grant_number: '160364472'
name: 'SFB 901 - C4: SFB 901 - On-The-Fly Compute Centers II: Ausführung komponierter
Dienste in konfigurierbaren Rechenzentren (Subproject C4)'
status: public
supervisor:
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
title: On Cloud Assisted, Restricted, and Reosurce Constrained Scheduling
type: dissertation
user_id: '15504'
year: '2023'
...
---
_id: '33491'
author:
- first_name: Marten
full_name: Maack, Marten
id: '88252'
last_name: Maack
- first_name: Simon
full_name: Pukrop, Simon
id: '44428'
last_name: Pukrop
- first_name: Anna Rodriguez
full_name: Rasmussen, Anna Rodriguez
last_name: Rasmussen
citation:
ama: 'Maack M, Pukrop S, Rasmussen AR. (In-)Approximability Results for Interval,
Resource Restricted, and Low Rank Scheduling. In: Chechik S, Navarro G, Rotenberg
E, Herman G, eds. 30th Annual European Symposium on Algorithms, ESA 2022, September
5-9, 2022, Berlin/Potsdam, Germany. Vol 244. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum
für Informatik; 2022:77:1–77:13. doi:10.4230/LIPIcs.ESA.2022.77'
apa: Maack, M., Pukrop, S., & Rasmussen, A. R. (2022). (In-)Approximability
Results for Interval, Resource Restricted, and Low Rank Scheduling. In S. Chechik,
G. Navarro, E. Rotenberg, & G. Herman (Eds.), 30th Annual European Symposium
on Algorithms, ESA 2022, September 5-9, 2022, Berlin/Potsdam, Germany (Vol.
244, p. 77:1–77:13). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ESA.2022.77
bibtex: '@inproceedings{Maack_Pukrop_Rasmussen_2022, series={LIPIcs}, title={(In-)Approximability
Results for Interval, Resource Restricted, and Low Rank Scheduling}, volume={244},
DOI={10.4230/LIPIcs.ESA.2022.77},
booktitle={30th Annual European Symposium on Algorithms, ESA 2022, September 5-9,
2022, Berlin/Potsdam, Germany}, publisher={Schloss Dagstuhl - Leibniz-Zentrum
für Informatik}, author={Maack, Marten and Pukrop, Simon and Rasmussen, Anna Rodriguez},
editor={Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
year={2022}, pages={77:1–77:13}, collection={LIPIcs} }'
chicago: Maack, Marten, Simon Pukrop, and Anna Rodriguez Rasmussen. “(In-)Approximability
Results for Interval, Resource Restricted, and Low Rank Scheduling.” In 30th
Annual European Symposium on Algorithms, ESA 2022, September 5-9, 2022, Berlin/Potsdam,
Germany, edited by Shiri Chechik, Gonzalo Navarro, Eva Rotenberg, and Grzegorz
Herman, 244:77:1–77:13. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2022. https://doi.org/10.4230/LIPIcs.ESA.2022.77.
ieee: 'M. Maack, S. Pukrop, and A. R. Rasmussen, “(In-)Approximability Results for
Interval, Resource Restricted, and Low Rank Scheduling,” in 30th Annual European
Symposium on Algorithms, ESA 2022, September 5-9, 2022, Berlin/Potsdam, Germany,
2022, vol. 244, p. 77:1–77:13, doi: 10.4230/LIPIcs.ESA.2022.77.'
mla: Maack, Marten, et al. “(In-)Approximability Results for Interval, Resource
Restricted, and Low Rank Scheduling.” 30th Annual European Symposium on Algorithms,
ESA 2022, September 5-9, 2022, Berlin/Potsdam, Germany, edited by Shiri Chechik
et al., vol. 244, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022, p.
77:1–77:13, doi:10.4230/LIPIcs.ESA.2022.77.
short: 'M. Maack, S. Pukrop, A.R. Rasmussen, in: S. Chechik, G. Navarro, E. Rotenberg,
G. Herman (Eds.), 30th Annual European Symposium on Algorithms, ESA 2022, September
5-9, 2022, Berlin/Potsdam, Germany, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2022, p. 77:1–77:13.'
date_created: 2022-09-27T13:06:05Z
date_updated: 2022-11-18T10:14:14Z
department:
- _id: '63'
doi: 10.4230/LIPIcs.ESA.2022.77
editor:
- first_name: Shiri
full_name: Chechik, Shiri
last_name: Chechik
- first_name: Gonzalo
full_name: Navarro, Gonzalo
last_name: Navarro
- first_name: Eva
full_name: Rotenberg, Eva
last_name: Rotenberg
- first_name: Grzegorz
full_name: Herman, Grzegorz
last_name: Herman
intvolume: ' 244'
language:
- iso: eng
page: 77:1–77:13
project:
- _id: '1'
name: 'SFB 901: SFB 901'
- _id: '16'
name: 'SFB 901 - C4: SFB 901 - Subproject C4'
- _id: '4'
name: 'SFB 901 - C: SFB 901 - Project Area C'
publication: 30th Annual European Symposium on Algorithms, ESA 2022, September 5-9,
2022, Berlin/Potsdam, Germany
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
series_title: LIPIcs
status: public
title: (In-)Approximability Results for Interval, Resource Restricted, and Low Rank
Scheduling
type: conference
user_id: '477'
volume: 244
year: '2022'
...
---
_id: '29872'
author:
- first_name: Marten
full_name: Maack, Marten
id: '88252'
last_name: Maack
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
- first_name: Simon
full_name: Pukrop, Simon
id: '44428'
last_name: Pukrop
citation:
ama: 'Maack M, Meyer auf der Heide F, Pukrop S. Server Cloud Scheduling. In: Approximation
and Online Algorithms. Springer International Publishing; 2022. doi:10.1007/978-3-030-92702-8_10'
apa: Maack, M., Meyer auf der Heide, F., & Pukrop, S. (2022). Server Cloud Scheduling.
In Approximation and Online Algorithms. Springer International Publishing.
https://doi.org/10.1007/978-3-030-92702-8_10
bibtex: '@inbook{Maack_Meyer auf der Heide_Pukrop_2022, place={Cham}, title={Server
Cloud Scheduling}, DOI={10.1007/978-3-030-92702-8_10},
booktitle={Approximation and Online Algorithms}, publisher={Springer International
Publishing}, author={Maack, Marten and Meyer auf der Heide, Friedhelm and Pukrop,
Simon}, year={2022} }'
chicago: 'Maack, Marten, Friedhelm Meyer auf der Heide, and Simon Pukrop. “Server
Cloud Scheduling.” In Approximation and Online Algorithms. Cham: Springer
International Publishing, 2022. https://doi.org/10.1007/978-3-030-92702-8_10.'
ieee: 'M. Maack, F. Meyer auf der Heide, and S. Pukrop, “Server Cloud Scheduling,”
in Approximation and Online Algorithms, Cham: Springer International Publishing,
2022.'
mla: Maack, Marten, et al. “Server Cloud Scheduling.” Approximation and Online
Algorithms, Springer International Publishing, 2022, doi:10.1007/978-3-030-92702-8_10.
short: 'M. Maack, F. Meyer auf der Heide, S. Pukrop, in: Approximation and Online
Algorithms, Springer International Publishing, Cham, 2022.'
date_created: 2022-02-18T09:31:54Z
date_updated: 2022-09-27T15:03:13Z
department:
- _id: '63'
doi: 10.1007/978-3-030-92702-8_10
language:
- iso: eng
place: Cham
project:
- _id: '1'
name: 'SFB 901: SFB 901'
- _id: '4'
name: 'SFB 901 - C: SFB 901 - Project Area C'
- _id: '16'
name: 'SFB 901 - C4: SFB 901 - Subproject C4'
publication: Approximation and Online Algorithms
publication_identifier:
isbn:
- '9783030927011'
- '9783030927028'
issn:
- 0302-9743
- 1611-3349
publication_status: published
publisher: Springer International Publishing
status: public
title: Server Cloud Scheduling
type: book_chapter
user_id: '44428'
year: '2022'
...
---
_id: '27778'
abstract:
- lang: eng
text: "Consider a set of jobs connected to a directed acyclic task graph with a\r\nfixed
source and sink. The edges of this graph model precedence constraints and\r\nthe
jobs have to be scheduled with respect to those. We introduce the Server\r\nCloud
Scheduling problem, in which the jobs have to be processed either on a\r\nsingle
local machine or on one of many cloud machines. Both the source and the\r\nsink
have to be scheduled on the local machine. For each job, processing times\r\nboth
on the server and in the cloud are given. Furthermore, for each edge in\r\nthe
task graph, a communication delay is included in the input and has to be\r\ntaken
into account if one of the two jobs is scheduled on the server, the other\r\nin
the cloud. The server can process jobs sequentially, whereas the cloud can\r\nserve
as many as needed in parallel, but induces costs. We consider both\r\nmakespan
and cost minimization. The main results are an FPTAS with respect for\r\nthe makespan
objective for a fairly general case and strong hardness for the\r\ncase with unit
processing times and delays."
author:
- first_name: Marten
full_name: Maack, Marten
id: '88252'
last_name: Maack
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
- first_name: Simon
full_name: Pukrop, Simon
id: '44428'
last_name: Pukrop
citation:
ama: Maack M, Meyer auf der Heide F, Pukrop S. Full Version -- Server Cloud Scheduling.
arXiv:210802109. Published online 2021.
apa: Maack, M., Meyer auf der Heide, F., & Pukrop, S. (2021). Full Version --
Server Cloud Scheduling. In arXiv:2108.02109.
bibtex: '@article{Maack_Meyer auf der Heide_Pukrop_2021, title={Full Version --
Server Cloud Scheduling}, journal={arXiv:2108.02109}, author={Maack, Marten and
Meyer auf der Heide, Friedhelm and Pukrop, Simon}, year={2021} }'
chicago: Maack, Marten, Friedhelm Meyer auf der Heide, and Simon Pukrop. “Full Version
-- Server Cloud Scheduling.” ArXiv:2108.02109, 2021.
ieee: M. Maack, F. Meyer auf der Heide, and S. Pukrop, “Full Version -- Server Cloud
Scheduling,” arXiv:2108.02109. 2021.
mla: Maack, Marten, et al. “Full Version -- Server Cloud Scheduling.” ArXiv:2108.02109,
2021.
short: M. Maack, F. Meyer auf der Heide, S. Pukrop, ArXiv:2108.02109 (2021).
date_created: 2021-11-24T13:23:58Z
date_updated: 2022-09-27T15:03:19Z
department:
- _id: '63'
- _id: '26'
language:
- iso: eng
publication: arXiv:2108.02109
status: public
title: Full Version -- Server Cloud Scheduling
type: preprint
user_id: '44428'
year: '2021'
...
---
_id: '13868'
author:
- first_name: Simon
full_name: Pukrop, Simon
id: '44428'
last_name: Pukrop
- first_name: Alexander
full_name: Mäcker, Alexander
id: '13536'
last_name: Mäcker
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
citation:
ama: 'Pukrop S, Mäcker A, Meyer auf der Heide F. Approximating Weighted Completion
Time for Order Scheduling with Setup Times. In: Proceedings of the 46th International
Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM).
; 2020.'
apa: Pukrop, S., Mäcker, A., & Meyer auf der Heide, F. (2020). Approximating
Weighted Completion Time for Order Scheduling with Setup Times. In Proceedings
of the 46th International Conference on Current Trends in Theory and Practice
of Computer Science (SOFSEM).
bibtex: '@inproceedings{Pukrop_Mäcker_Meyer auf der Heide_2020, title={Approximating
Weighted Completion Time for Order Scheduling with Setup Times}, booktitle={Proceedings
of the 46th International Conference on Current Trends in Theory and Practice
of Computer Science (SOFSEM)}, author={Pukrop, Simon and Mäcker, Alexander and
Meyer auf der Heide, Friedhelm}, year={2020} }'
chicago: Pukrop, Simon, Alexander Mäcker, and Friedhelm Meyer auf der Heide. “Approximating
Weighted Completion Time for Order Scheduling with Setup Times.” In Proceedings
of the 46th International Conference on Current Trends in Theory and Practice
of Computer Science (SOFSEM), 2020.
ieee: S. Pukrop, A. Mäcker, and F. Meyer auf der Heide, “Approximating Weighted
Completion Time for Order Scheduling with Setup Times,” in Proceedings of the
46th International Conference on Current Trends in Theory and Practice of Computer
Science (SOFSEM), 2020.
mla: Pukrop, Simon, et al. “Approximating Weighted Completion Time for Order Scheduling
with Setup Times.” Proceedings of the 46th International Conference on Current
Trends in Theory and Practice of Computer Science (SOFSEM), 2020.
short: 'S. Pukrop, A. Mäcker, F. Meyer auf der Heide, in: Proceedings of the 46th
International Conference on Current Trends in Theory and Practice of Computer
Science (SOFSEM), 2020.'
date_created: 2019-10-15T12:19:49Z
date_updated: 2022-01-06T06:51:45Z
department:
- _id: '63'
language:
- iso: eng
project:
- _id: '4'
name: SFB 901 - Project Area C
- _id: '1'
name: SFB 901
- _id: '16'
name: SFB 901 - Subproject C4
publication: Proceedings of the 46th International Conference on Current Trends in
Theory and Practice of Computer Science (SOFSEM)
status: public
title: Approximating Weighted Completion Time for Order Scheduling with Setup Times
type: conference
user_id: '44428'
year: '2020'
...