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.
翻译：考虑一组任务, 与固定源和汇的定向环绕任务图连接。 此图样样样的边框限制和任务必须为此排期。 我们引入了服务器云排程问题, 任务必须在单一的本地机器或多台云机中处理。 源和汇都必须在本地机器中排期。 对于每个任务, 在服务器和云中都给出了处理时间。 此外, 对于任务图的每个边角, 输入中都包含通信延迟, 如果两个任务中有一个被排在服务器上, 另一在云中, 则必须加以考虑 。 服务器可以按顺序处理工作, 而云可以按需要同时操作, 但也会引起成本。 我们考虑的是将源和汇放在本地机器上, 将成本最小化。 主要结果为 FPTAS, 尊重 manspan 目标, 以相当普通的立案和坚硬的难度, 以及单位处理时间和延迟的立案 。
相关内容
微信扫码咨询专知VIP会员