Non-clairvoyant scheduling with conflicts for unit-size jobs

摘要

We consider the problem of scheduling unit-size jobs with conflicts in a non-clairvoyant setting. In this problem, all jobs are released at the same time but the conflict graph is unknown to the scheduling algorithm beforehand. Instead, the conflicts between the jobs are revealed online by an adversary during the job's execution. There is an unlimited number of processors so that all jobs could be executed simultaneously. However, two jobs with a conflict cannot be both completed in the same time step; when their conflict is revealed, one of them must be aborted and re-executed later. The objective is to minimize the total number of time steps required to complete all jobs, or the makespan. We present an online non-clairvoyant algorithm and analyze its performance for three types of conflict graphs. For bipartite graphs, we show that it is O (log n)-competitive, where n denotes the total number of jobs. For unit-interval graphs, we show that it is O (log chi)-competitive, where chi denotes the chromatic number of the graph. For bounded-degree graphs, we show that it is O (Delta)-competitive, where Delta denotes the maximum degree of any node in the graph. For bipartite and bounded-degree graphs, we also provide matching lower bounds and show that the obtained competitive ratios are asymptotically tight. (C) 2018 Elsevier B.V. All rights reserved.