Server Cloud Scheduling - Maack, Marten; Meyer auf der Heide, Friedhelm; Pukrop, Simon (Algorithmica)
Abstract Consider 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.
Keywords: Applied Mathematics; Computer Science Applications; General Computer Science

Scheduling with Many Shared Resources - Deppert, Max A.; Jansen, Klaus; Maack, Marten; Pukrop, Simon; Rau, Malin (2023 IEEE International Parallel and Distributed Processing Symposium (IPDPS))

On-The-Fly Compute Centers II: Execution of Composed Services in Configurable Compute Centers - Karl, Holger; Maack, Marten; Meyer auf der Heide, Friedhelm; Pukrop, Simon; Redder, Adrian (On-The-Fly Computing -- Individualized IT-services in dynamic markets)

Cardinality Constrained Scheduling in Online Models - Epstein, Leah; Lassota, Alexandra; Levin, Asaf; Maack, Marten; Rohwedder, Lars (39th International Symposium on Theoretical Aspects of Computer Science, STACS 2022, March 15-18, 2022, Marseille, France (Virtual Conference))

(In-)Approximability Results for Interval, Resource Restricted, and Low Rank Scheduling - Maack, Marten; Pukrop, Simon; Rasmussen, Anna Rodriguez (30th Annual European Symposium on Algorithms, ESA 2022, September 5-9, 2022, Berlin/Potsdam, Germany)

Server Cloud Scheduling - Maack, Marten; Meyer auf der Heide, Friedhelm; Pukrop, Simon (Approximation and Online Algorithms)

Full Version -- Server Cloud Scheduling - Maack, Marten; Meyer auf der Heide, Friedhelm; Pukrop, Simon (arXiv:2108.02109)
Consider 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 many cloud machines. Both the source and the sink have to be scheduled on the local machine. 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, the other in the cloud. The server can process 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 with respect for the makespan objective for a fairly general case and strong hardness for the case with unit processing times and delays.