Parameterized Complexity of Scheduling Unit-TimeJobs with Generalized Precedence Constraints

arXiv (Cornell University)

Abstract

We study the parameterized complexity of scheduling unit-time jobs on parallel, identical machines under generalized precedence constraints for minimization of the makespan and the sum of completion times. In our setting, each job is equipped with a Boolean formula (precedence constraint) over the set of jobs. A schedule satisfies a job's precedence constraint if setting earlier jobs to true satisfies the formula. Our definition generalizes several common types of precedence constraints: classical and-constraints if every formula is a conjunction, or-constraints if every formula is a disjunction, and and/or-constraints if every formula is in conjunctive normal form. We prove fixed-parameter tractability when parameterizing by the number of predecessors. For parameterization by the number of successors, however, the complexity depends on the structure of the precedence constraints. If every constraint is a conjunction or a disjunction, we prove the problem to be fixed-parameter tractable. For constraints in disjunctive normal form, we prove W[1]-hardness. We show that the and/or-constrained problem is NP-hard, even for a single successor. Moreover, we prove NP-hardness on two machines if every constraint is a conjunction or a disjunction. This result not only proves para-NP-hardness for parameterization by the number of machines but also complements the polynomial-time solvability on two machines if every constraint is a conjunction (Coffman and Graham 1972) or if every constraint is a disjunction (Berit 2005).

Authors 3

1. Christina Büsing Aachen

   RWTH Aachen University

   Affiliation as printed

   RWTH Aachen

2. Maurice Draeger Aachen

   RWTH Aachen University

   Affiliation as printed

   RWTH Aachen

3. Corinna Mathwieser Aachen

   RWTH Aachen University

   Affiliation as printed

   RWTH Aachen