Scheduling with conflicts: approximation algorithms and online algorithms (コンピュテーション)

概要

論文の詳細を見る
We consider the following problem of scheduling with conflicts (SWC). Find a minimum makespan schedule on identical machines where conflicting jobs may not be scheduled concurrently. We present the first approximation algorithms for the case in which conflicts between jobs are modeled general graphs both for unit jobs and jobs with arbitrary processing times. We also consider an online model in which each job has a release time. We present the first results fo SWC in the online model, including lower and upper bounds for the competitive ratio of deterministic online algorithms.
一般社団法人電子情報通信学会の論文
2007-04-19