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 by 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 for SWC in the online model, including lower and upper bounds for the competitive ratio of deterministic online algorithms.
展开▼
