On the Complexity of Global Scheduling Constraints under Structural Restrictions

1 Introduction

There are many varieties of scheduling problems: production, workforce, and resource scheduling, to name just three. Whilst such scheduling problems are intractable in general, the actual instances met in practice may contain restrictions that mean we can solve them efficiently. For example, many scheduling problems can be encoded into Allen's interval algebra. If the interval relations used in this encoding are limited to one of the 18 maximal tractable sub-algebras [Krokhin et al., 2001] then the problem can be efficiently solved. This is an example of tractability via a language restriction. An orthogonal way to obtain tractability is via structural restrictions. We impose restrictions on the structure of the problem like the number of processors, or the number of different start times which ensure tractability. We illustrate such a study of scheduling problems with four case studies. The first three are positive: we identify structural restrictions under which the scheduling problem is fixed-parameter tractable or polynomial to solve. The fourth case study is negative: we show that even under strong structural restrictions, a simple scheduling problem with uniform task lengths remains NP-hard.

Since the consistency check for CUMULATIVE and INTERDISTANCE are equivalent to checking whether there ex- Univ. of Melbourne Melbourne, Australia andreas.schutt@nicta.com.au Toby Walsh NICTA and UNSW Sydney, Australia toby.walsh@nicta.com.au ists a schedule satisfying certain restrictions, our work can be seen as studying the tractability of scheduling problems. Marx (2011) recently noted noted that there is surprisingly little work on the fixed-parameter tractability of scheduling problems. The few existing examples [Bodlaender and Fellows, 1995; Fellows and McCartin, 2003] present mostly negative results. The only known fixed-parameter tractable results parameterize by the tree-width of the precedence graph and either the number of late tasks or the number of tasks that need to be on time. In contrast, we consider CUMULATIVE as a hard constraint, allowing no late tasks and do not restrict the precedence graph. Instead, we exploit parameters related to the number of distinct values defining characteristics of the tasks can take, and to how many tasks can potentially start at any given time point. Our results for the INTERDISTANCE constraint complement existing results on structural restrictions [Artiouchine et al., 2008]. Building on [Bessi`ere et al., 2004a; Bessi`ere et al., 2004b], the parameterized complexity of global constraints was first studied in [Bessi`ere et al., 2008]. Amongst other results, INTERDISTANCE was shown to be fixed-parameter tractable in the total number of holes in the domains of the variables. This line of research was continued in, e.g., [Fellows et al., 2011a; Gaspers and Szeider, 2011; Samer and Szeider, 2011].

2 Background

CSP. A Constraint Satisfaction Problem (CSP) consists of a set of variables X, a set of values D, and a set of constraints C. The question is whether there exists an assignment α : V → D satisfying all constraints. A constraint is a pair 〈t,R〉; its scope t = (x1, . . . , xr) is an r-tuple of variables and its constraint relation R is an r-ary relation on D. It is satisfied if (α(x1), . . . , α(xr)) ∈ R. When there is no confusion we also write xi instead of α(xi). In the classical CSP, these relations are described explicitly, by listing all allowed tuples. A global constraint is an implicitly specified constraint of arbitrary scope. Next, we describe the global constraints CUMULATIVE and INTERDISTANCE.

CUMULATIVE. This was introduced in CHIP for scheduling and related problems [Aggoun and Beldiceanu, 1993]. We consider a set T = {1, ..., n} of n tasks and P processors. Each task i has a tuple (ri, li, di, pi) of four natural numbers:

• ri is the release time of the task, i.e., the time point at

which it becomes available,

• li is the length of the task, i.e., the amount of time it needs to be processed,
• di is the deadline of the task, i.e., the time point at which it needs to have been processed, and
• pi is the number of processors it uses.

The scope of the constraint contains a variable si for each i ∈ T , and it is satisfied by an assignment α if

• si ≥ ri for each task i ∈ T,
• si + li ≤ di for each task i ∈ T , and
• ∑i∈T:si≤j<si+li pi ≤ P at each time point j ∈ N.

We also consider precedence constraints between tasks, expressed by a directed acyclic precedence graph G = (T, A). For each arc (u, v) ∈ A, we constrain that su + lu ≤ sv.

Due to its expressivity, CUMULATIVE is widely used in constraint programming and is implemented in most constraint solvers. Therefore, a lot of research has been carried out on improving filtering algorithms for this constraint. Enforcing domain consistency on the constraint is NP-hard. However, a number of efficient filtering algorithms have been proposed, e.g. [Caseau and Laburthe, 1996; Mercier and Hentenryck, 2008; Schutt and Wolf, 2010; Vil´ım, 2011].

INTERDISTANCE. R´egin (1997) introduced the INTERDISTANCE constraint, which is useful in modeling scheduling problems on a single processor where all tasks have the same length. We are given a set T = {1, ..., n} of n tasks, a task length l, and each task i has a set Si ⊆ N of possible start times. The question is whether each task can be assigned a start time si ∈ Si such that no two tasks overlap, i.e., for every two distinct tasks i, j ∈ T, we have that |si - sj| ≥ l. Enforcing bounds consistency on the INTERDISTANCE constraint is polynomial [Artiouchine and Baptiste, 2007; Quimper et al., 2008]. However, enforcing domain consistency is NP-hard [Artiouchine et al., 2008].

Parameterized Complexity. Parameterized complexity is a 2-dimensional analogue of the theory of NP-completeness [Downey and Fellows, 1999; Fellows et al., 2011b; Flum and Grohe, 2006; Niedermeier, 2006], where instances are equipped with a parameter k. A parameterized problem Π is fixed-parameter tractable (FPT) if there is a computable function f such that every instance (I, k) of Π can be solved in time f(k) · nO(1) , where n is the instance size. The theory has a fundamental hierarchy of intractability classes W[1] ⊆ W[2] ⊆ . . . and a problem that is hard for any of these classes (under parameterized reductions) is not believed to be FPT.

3 Task Types

We first consider the CUMULATIVE constraint when the number of distinct release times and deadlines is bounded and there is a single processor. W.l.o.g. we assume that the smallest release time is zero and the latest deadline is d∗ . This problem is already NP-hard.

Theorem 1 ([Garey and Johnson, 1979]). Checking consistency of the CUMULATIVE constraint is weakly NP-complete even if the number of distinct releases is two, the number of distinct deadlines is also two, and there is a single processor.

Theorem 1 suggests that we need to restrict further the problem to identify tractable cases. In the spirit of parameterizing by the number of numbers [Fellows et al., 2012], we consider the CUMULATIVE constraint parameterized by the number of distinct characteristics. Observe that with this parameterization, the number of distinct quadruples consisting of a release time, a task length, a deadline, and a number of processors, is also bounded by the parameter. Therefore, we introduce a notion of a task type. A task i with characteristics (ri, li, di, pi) belongs to the (r, l, d, p)-type iff (ri, li, di, pi) = (r, l, d, p).

Given a sequence of tasks, a run of the (r, l, d, p)-type is a maximal consecutive subsequence of (r, l, d, p)-type tasks. An empty run contains no tasks. A block is a maximal time interval that does not contain release times nor deadlines. Given the CUMULATIVE constraint, we can always partition the time-line, [0, d∗ ], into a set of blocks B.

Example 1. Consider the CUMULATIVE constraint in Fig. 1. The task types are (0, 2, 10, 1), (6, 2, 25, 1), and (15, 2, 30, 1). Each type consists of three tasks of length 2. Release times and deadlines partition the time line into five blocks.

The results in this section assume precedences are defined over task types rather than individual tasks.

Lemma 1. Consider the CUMULATIVE constraint on a single processor. Let B be the partitioning of the time-line into blocks and s be a solution of the constraint. Consider bj ∈ B and the set of tasks T ′ such that [si, si +li] ⊆ bj for all tasks i in T ′ . Then any permutation of tasks in T ′ satisfying the precedence constraints gives a solution.

We write that the ith task is in a block bj iff [si, si + li] ⊆ bj . Schedule 2 in Fig. 1 is a permutation of Schedule 1.

The parameter considered in this section is q, the number of types. Denote by b the number of blocks in B, |B| = b. First, note that b ≤ 2q - 1.

Lemma 2. Consider the CUMULATIVE constraint on a single processor. If there exists a solution of the constraint then there exists a solution where for each block bi, there is at most one run of each type among the tasks starting in block bi.

Proof. Consider any block bi. By Lemma 1, any permutation of tasks in a block that satisfies the precedence constraints gives a solution. Let π be a topological order of task types in the precedence graph G that start in bi. Let j be the type of the last task that starts in bi. Note that this task could end after di and, w.l.o.g., assume that this task is the last task in

π. Reorder the tasks starting in bi according to π. This makes sure that there exists at most one run of each type among the tasks completely contained in bi and the last run has the same type as the task that crosses the border between this block and the following block. Since bi was chosen arbitrarily and only tasks that lie completely within bi were reordered, we can perform the same operation in each other block bi′ .

Given Lemma 2, we can write an integer linear program (ILP) to check consistency of the CUMULATIVE constraint, whose number of variables is bounded by a function of q. This shows that consistency checking for CUMULATIVE is FPT. In the INTEGER LINEAR PROGRAMMING FEASIBILITY problem (ILPF), the input is an m× n matrix A and m-vector b of integers, the parameter is n, and we ask if there is an n-vector x of integers satisfying the m inequalities Ax ≤ b. ILPF is FPT in the number of variables [Lenstra, 1983]. The current fastest algorithm solves ILPF in time O(n2.5n+o(n) · L), where L is the input size [Lokshtanov, 2009].

Theorem 2. Checking the consistency of the CUMULATIVE constraint on a single processor is fixed-parameter tractable parameterized by the number of task types.

Proof. We encode the problem of checking the consistency of the CUMULATIVE constraint into a set of ILPs, each with a number of variables bounded by a function of q. The size of this set is bounded by a function of q as well, and the CUMULATIVE constraint is satisfiable iff at least one ILP is feasible. By Lemma 2 we know that if a solution exists then there exists a solution with at most one run of each type starting in each block. The last run in each block might cross the border between this block and the next block. To simplify notations, we assume that there exists exactly one run of each type starting in each block, so that some runs are empty. We use a pair (i, j) to denote the ith run of type j. Then the total number of runs is bq ≤ (2q - 1)q. Any solution of the constraint with at most one run of each type among the tasks starting in the same block constitutes a permutation of such runs (i, j), i = 1, . . . , b, j = 1, . . . , q that satisfies precedence constraints. Moreover, the number of permutations O((bq)!) is also bounded by a function of q. For each valid permutation of runs, we will solve an ILP to check if this permutation can be extended to a feasible solution.

Given a permutation of runs π, we write (i, j) ≺ (k, l) ∈ π iff the ith run of type j precedes the kth run of type l in π. We emphasize that we only consider permutations that satisfy precedence constraints. To build the ILP, we need to identify the start time of each run and the number of tasks in each run. We introduce two sets of integer variables. The first set of variables is si,j, i = 1, . . . , b, j = 1, . . . , q. Variable si,j equals the starting time for the ith run of the jth type, si,j ∈ [0, d∗ ]. The second set of variables is xi,j, i = 1, . . . , b, j = 1, . . . , q. Variable xi,j equals the number of tasks in the ith run of type j, xi,j ∈ [0, nj], where nj is the number of tasks of type j. Note that xi,j = 0 means that the ith run of type j is empty. We obtain the following ILP for i, k ∈ {1, . . . , b} and j, l ∈ {1, . . . , q}:

Equations 1-2 make sure that each run of type j is performed within the interval [rj, dj]. Equation 3 ensures that runs are performed in the order specified by the permutation π and that they do not overlap. Finally, Equation 4 guarantees that all tasks are performed. Since the number of variables is bounded by a function of q, checking the consistency of CUMULATIVE on a single processor is fixed-parameter tractable parameterized by the number of task types.

Corollary 1. Checking the consistency of the CUMULATIVE constraint on multiple processors is FPT parameterized by the number of task types and the number of processors if each task requires one processor, pi = 1, i = 1, . . . , n.

Proof. As in the proof of Theorem 2, we need to consider all possible permutations of runs that satisfy precedence constraints. However, each run is characterized by an additional parameter which is a machine where this run is scheduled. The tuple (i, j, k) describes the ith run of jth type that runs on the kth machine. The total number of runs is O(qbP) which is bounded by the parameter. We solve an ILP for each permutation in a similar way. However, we need to add extra constraints to the ILP to make sure that for each pair of tasks of types j and j ′ , such that j ≺ j ′ in G, that run on different processors, respect precedence. Hence, if we have (i, j, k) ≺ (i′ , j ′ , k′ ), k ̸= k′ , in a permutation π and j ≺ j ′ in G, then we add the constraint: si,j,k + xi,j · lj ≤ si′ ,j ′ ,k′ The obtained ILP has O(qbP) variables. Hence, the problem is FPT in the number of task types and processors.

3.1 Nested Task Types

Here, we consider a special case of the CUMULATIVE constraint where the task types have a nested structure. The considered parameter is still the number of task types, q.

Definition 1. Task types are nested if ri ≤ ri+1, di+1 ≤ di and there is a common point c with c ∈ [ri, di], i = 1, . . . , n.

Example 2. The CUMULATIVE constraint in Fig. 2 has three nested types: (0, 2, 30, 1), (5, 2, 25, 1) and (10, 2, 20, 1).

Theorem 1 holds for nested types. The reduction is from partition and forces (via release-times and deadlines) one unitlength task to start at the exact middle of the schedule. The other tasks have lengths equal to the numbers that need to be partitioned and release-time 0 and deadline the sum of all numbers plus one. Note that the claimed polynomial time algorithm for this problem in [Briand et al., 2006] is actually incomplete. We now show some useful properties of this restriction of the CUMULATIVE constraint. Recall that nj denotes the number of tasks of type j. We say that a solution has no gaps if there exist time points t1 and t2 such that ∑qj=1 njlj = t2 - t1 + 1 and the processor is idle within [0, t1) ∪ [t2, d∗ ].

Lemma 3. Consider the CUMULATIVE constraint for a single processor with nested types. If there exists a solution of the constraint then there exists a solution with no gaps.

Proof. Let s be a solution of the constraint. Consider the first two consecutive tasks i and k in the schedule such that si + li < sk, where si and sk are starting times of tasks i and k, respectively. Let c be any time point between the release time and the deadline of the innermost type. If sk ≤ c then we can shift all tasks scheduled before the ith task and the ith task to the right by sk - (si + li) time units. This preserves the solution due to the nested structure of the types. Similarly, if si + li ≥ c then we can shift all tasks scheduled after the kth task and the kth task to the left by sk - (si + li) time units. Finally, if c ∈ [si+li, sk] then we shift tasks scheduled before the ith task and the ith task to the right by c - si + li and tasks scheduled after the kth task and the kth task to the left by sk -c time units. Again, this transformation preserves the solution due to the nested structure of the types.

Example 3. Consider the CUMULATIVE constraint fromExample 2. Schedule 1 is a valid solution of the constraint. Schedule 2 is a solution with no gaps.

Lemma 4. Consider the CUMULATIVE constraint for a single processor with nested types. If there exists a solution to the constraint then there exists a solution where there are at most two runs of each type and runs obey the following order: (1, 1) ≺ . . . ≺ (1, q-1) ≺ (1, q) ≺ (2, q-1) ≺ . . . ≺ (2, 1).

Proof. (Sketch) Consider the first and the second scheduled tasks of type q (q1 and q2) and the task j of type j that obey the order q1 ≺ j ≺ . . . ≺ q2 in a solution. Then, we can swap tasks j and q2 in the schedule and obtain another valid solution. Similarly, we reorder the remaining tasks.

Corollary 2. Consider the CUMULATIVE constraint with a single processor with nested types. If there exists a solution of the constraint then there exists a solution that satisfies the conditions of Lemmas 3-4.

Schedule 3 in Fig. 2 is a solution that satisfies the conditions of Lemmas 3-4.

Theorem 3. Checking the consistency of the CUMULATIVE constraint on a single processor with nested types is fixed-parameter tractable parameterized by the number of task types.

Proof. First, we encode the problem of checking the consistency without the precedence graph G into an ILP with a number of variables bounded by a function of q. Then we show how to take into account G. By Lemmas 3-4, if a solution exists then we know that there exists a solution with no gaps and runs obey the order (1, 1) ≺ (1, 2) ≺ . . . ≺ (1, q - 1) ≺ (1, q) ≺ (2, q - 1) ≺ . . . ≺ (2, 1). We exploit these properties to build the ILP. We know that tasks of type j are split into at most two runs. The first run completes before one of the common points c ∈ [rq, dq] and the second run starts after this point. However, we do not know c and how many tasks of each type are scheduled before c. First, we need to select c. Second we need to determine the number of tasks in these two runs. For convenience, we assume that the single run of type q is partitioned into two runs at c. The time point c ∈ [rq, dq] is encoded as a variable in the ILP. Variable xj, j = 1, . . . , q equals the number of tasks of type j that are scheduled before c. We obtain the following ILP.

Equations 5-6 makes sure that each run of the jth type is performed within the interval [rj, dj] by exploiting the fact that there are no gaps between tasks (Lemma 3) and runs occur in a specific order (Lemma 4).

Next, we show how to extend this ILP to take into account the precedence constraints. Consider two types i and j such that i ≺ j. We distinguish two cases. Suppose that the ith type is nested inside the jth type. In this case, xj must be equal zero, otherwise one of the tasks of type j is scheduled before a task of type i (we assume that there exists at least one task of each type.) Suppose that the jth type is nested inside the ith type. In this case, xi = ni. Hence, depending on the nesting we add one of these equality constraints to ILP. We perform this extension for each precedence constraint.

Note that Theorem 3 follows from Theorem 2. However, the ILP in the proof of Theorem 3 has only O(q) variables, while each of the O((bq)!) ILPs in the proof of Theorem 2 contains O(bq) variables. These considerations lead to much faster running times for a nested structure of task types.

4 Pairwise Overlapping Start Intervals

In this section, we consider a parameter that is related to the well-known disjunctive ratio [Baptiste and Pape, 2000] and the number of overlapping release-deadline windows. The start interval of a task i ∈ T is the interval S[i] = [ri; di-li], which we assume to be non-empty for all tasks. Clearly, in any valid instantiation each task starts at a time point that is within its start interval. For a time point t ∈ N, we denote by T[t] the set of tasks whose start interval contains t. We consider the parameterization by S := maxt∈N |T[t]|. We note that this parameter is more general than the number of overlapping release-deadline windows since for each job, its start interval is strictly contained in its release-deadline window. As usual, we also assume that there is a precedence graph G that defines precedence relations between individual tasks.

Theorem 4. Checking the consistency of the CUMULATIVE constraint on a single processor is fixed-parameter tractable parameterized by S.

Proof. We can check the consistency using dynamic programming. Let min(∅) = ∞. Let ≺ include explicit precedences from G and precedences implied by the start intervals.

Given a subset of the tasks S, let ms(S) be the the minimum value of max({si : i ∈ S}) over all valid instantiations where all tasks in S are scheduled before those not in S. The following dynamic program computes ms(S).

The cumulative constraint with precedences is consistent iff ms(T) ̸= ∞. Naively, it looks like the dynamic program has complexity O(n2n ). However, there are many S for which ms(S) = ∞ due to the constraints. Such S do not have to be stored or expanded. Given a subset S, let lr(S) = argmaxi∈S ri. We claim that for each task k, there are at most O(2|T[rk]| ) subsets with lr(S) = k which need to be evaluated in the dynamic program. Suppose S is one such subset. Every task i for which ri > rk is not in S by the definition of lr(S). Every task i for which di < rk + lk + li must be in S by the implied precedence constraint. Hence the only tasks which may be in S are those for which ri ≤ rk and di - li ≥ rk + lk, which means their start interval contains time rk. Thus there are at most O(2|T[rk]| ) relevant subsets with lr(S) = k as claimed. The task k can be any of the n tasks, so there are O(n2S) relevant subsets. Each subset is processed in the dynamic program by extending it with any of the O(n) remaining tasks. Hence the overall complexity is O(n2 2S), so the consistency check is FPT in S.

5 Decomposable Planning Horizon

Consider the CUMULATIVE constraint where each task i ∈ T has a set Si ∈ N of possible start times. Let the overlap graph L be defined as follows. For each task i and each v ∈ Si, we add the pair (i, v) to L as a vertex. We add an edge between two vertices (i, v) and (j, w) if [v, v + li] ∩ [w, w + lj ] ̸= ∅. This overlap graph might contain valuable structural information that can be exploited algorithmically. A clique is a graph with an edge between every pair of distinct vertices. The following theorem could, for instance, correspond to a scenario where tasks are only executed during the daytime, but no processor can execute two tasks during one day.

Theorem 5. Checking the consistency of the CUMULATIVE constraint on multiple processors is polynomial if pi = 1 for each task i ∈ T and L is a disjoint union of cliques.

Proof. Suppose L is a disjoint union of the k cliques L1, . . . ,Lk. Consider the vertices in Li. The set {[v, v + lj] : (j, v) ∈ Li} is pairwise intersecting since Li is a clique. This implies there is some value vi which is contained in all those intervals. Thus at most P of the assignments in Li can be taken without violating the resource constraint at time vi. We reduce this to a global cardinality constraint [R´egin, 1996] as follows. For each task i, we have a variable xi with domain {j ∈ {1, . . . , k} : ∃v ∈ Si, (i, v) ∈ Lj}. The cumulative constraint is satisfiable iff gcc([x1, . . . , xn], [1, . . . , k], [0, . . . , 0], [P, . . . , P]) is satisfiable, i.e., every task is associated to a clique, and each clique has at most P associated tasks. The reduction is polynomial time, as is solving the global cardinality constraint.

6 UniformTask Lengths

An important variant of the CUMULATIVE constraint is the INTERDISTANCE constraint, which is related to Runway sequencing problems for air-traffic control [Artiouchine and Baptiste, 2007; Artiouchine et al., 2008].

6.1 Start times consist of few intervals

The consistency check for INTERDISTANCE is polynomial if all Si are intervals, i.e., each Si contains only consecutive integer values [Artiouchine and Baptiste, 2007]. When l = 1, INTERDISTANCE is equal to the ALLDIFFERENT constraint, whose consistency check is polynomial [R´egin, 1994]. Based on a result by Spieksma and Crama (1992), Artiouchine et al. (2008), we observe that consistency checking is NP-hard when l = 2 and each Si consists of at most three intervals. We close this gap by proving that the problem remains NP-hard when l = 2 and each Si consists of at most two intervals.

Theorem 6. Checking the consistency of the INTERDISTANCE constraint is NP-complete when l = 2 and each Si consists of at most two intervals.

Proof (sketch). We give a polynomial time reduction from (≤ 3, ≤ 3)-SAT, the variant of the atisfiability problem where each clause has at most three literals and each variable occurs at most three times [Tovey, 1984]. Given a (≤ 3,≤ 3)-SAT formula F , denote by X = {x0, x1, . . . , xn-1} its set of variables and C = {C0,C1, . . . ,Cm-1} its set of clauses. A clause Ci ∈ C is a set of at most three literals. We set the task length l = 2. For each variable xi ∈ X, we introduce the following variable tasks (see Fig. 3):

• task number 10 · i with S10i = {40i + 1, 40i + 5} is the main task for variable xi,
• tasks number 10 · i + 1, . . . , 10 · i + 8 with

For each clause Ci ∈ C, we introduce four new tasks. Suppose Ci = {li1 , li2 , li3 }, each lij = xij or lij = ¬xij , j = 0, 1, 2, and lij is the kij th occurrence of variable xij in F , 1 ≤ kij ≤ 3. Then the new tasks are

• literal tasks numbered 10n + 4i + j, with j = 0, 1, 2, with possible starting times S10n+4i+j =

• a clause task numbered 10n+4i+3 with possible starting times in the interval [40n + 8i; 40n + 8i + 4].

This finishes the description of the reduction.

The (≤ 3, ≤ 3)-SAT instance is satisfiable if and only if the constructed INTERDISTANCE constraint has a valid instantiation. We set α(xi) = true if the main task for variable xi is scheduled at time point 40i + 1 and α(xi) = false otherwise. In the first case, each task 10 · i + j with j ∈ {3, 5, 7} is scheduled at time point 40i + 4j + 5. Therefore, for a clause containing ¬xi, the corresponding literal task is scheduled after the time point 40n. The argument for positive literals is similar. Since the clause task occupies two of the six units of time where literal clauses can be scheduled after 40n, one of the literal tasks must be scheduled before 40n and the corresponding literal therefore satisfies the clause.

6.2 Start times at equal distances

Artiouchine et al. (2008) also studied restrictions of the problemwhere Si = {ri, ri+h, . . . , ri+ki·h}. In this case, which we call REGULAR INTERDISTANCE, airplane i approaching a terminal at time ri can either land immediately or fly some number of at most ki loops in a holding pattern, each taking some fixed amount of time h, before it lands.

A proper interval graph is a graph whose vertices can be bijectively mapped to intervals of the real line, all with integer coordinates and equal lengths, such that two vertices are adjacent iff their intervals intersect. The set of these intervals is the interval model of the graph. We give a reduction from a graph coloring problem for proper interval graphs, called (γ, µ)-coloring [Bonomo et al., 2009]. Given a proper interval graph G = (V, E) and functions γ, µ : V → N, we ask if there exists a coloring f : V → N assigning distinct colors to adjacent vertices such that γ(v) ≤ f(v) ≤ µ(v).

We construct a REGULAR INTERDISTANCE constraint as follows. The task length l is the length of an interval in the interval model. The integer h is the position of the rightmost right endpoint of an interval in the interval model. For each vertex ui with interval [ai; ai + l), create a task i with Si = {ai +γ(ui) · h, ai +(γ(ui)+1) · h, . . . , ai +µ(ui) · h}. Now G has a (γ, µ)-coloring iff there is a solution for the constructed REGULAR INTERDISTANCE constraint. Precoloring Extension, a special case of (γ, µ)-coloring, is NP-complete on proper interval graphs [Marx, 2006]. Hence, we conclude:

Theorem7. Checking consistency of REGULAR INTERDISTANCE is NP-complete, even if ki ∈ {1, k} for integer k.

Consider now the special case where k1 = · · · = kn = k and maxi∈T ri + l ≤ maxi∈T ri + T, i.e., each task has k time slots where it can be scheduled and the time line can be partitioned into disjoint intervals I0, . . . , Ik where Ii contains all time points where a task may be scheduled if it occupies its ith time slot. This is linear-time solvable via a MIP formulation [Artiouchine et al., 2008]. But note that for this special case the above reduction can be reversed, giving a k-coloring problem for proper interval graphs, which is linear-time solvable [Golumbic, 1980]. Thus, we obtain the same theorem as [Artiouchine et al., 2008] by simpler means.

Theorem 8. The consistency of the REGULAR INTERDISTANCE constraint with k1 = · · · = kn and maxi∈T ri + l ≤ maxi∈T ri + T can be checked in linear time.

The requirement that k1 = · · · = kn is essential. Without it, we obtain the NP-complete µ-coloring problem on unit interval graphs [Bonomo et al., 2012], which is equivalent to (γ, µ)-coloring with γ(v) = 0 for all v ∈ V . It would be interesting to know in this context if (γ, µ)-coloring is FPT for proper interval graphs with parameter maxv∈V µ(v) - γ(v).

7 Conclusions

Scheduling is an important and well studied domain of combinatorial optimization. Due to their combinatorial nature, scheduling problems are computationally hard even for very restricted cases. Identifying those scheduling problemswhich become tractable when certain parameters are fixed has received little attention. In this paper, we take some steps forward in this direction. We show that we can exploit structural restrictions to obtain new tractable classes of scheduling problems. For example, we proved that scheduling problems with a large number of identical tasks are tractable. On the other hand, we demonstrated that scheduling problems with uniform task lengths remain intractable even under very strong structural restrictions. This also reveals an interesting connection between this class of problems and the list coloring problem on proper interval graphs. Our work raises a number of open questions. For example, what other interesting structural restrictions make scheduling tractable?

Acknowledgments

Supported by the Department of Broadband, Communications and the Digital Economy, the ARC and the Asian Office of Aerospace Research and Development (AOARD-124056).