# the_complexity_landscape_of_resourceconstrained_scheduling__dd129305.pdf

The Complexity Landscape of Resource-Constrained Scheduling

Robert Ganian1 , Thekla Hamm1 and Guillaume Mescoff2

1Vienna University of Technology 2Rennes University rganian@gmail.com, thamm@ac.tuwien.ac.at, guillaume.mescoff@ens-rennes.fr

The Resource-Constrained Project Scheduling Problem (RCPSP) and its extension via activity modes (MRCPSP) are well-established scheduling frameworks that have found numerous applications in a broad range of settings related to artificial intelligence. Unsurprisingly, the problem of finding a suitable schedule in these frameworks is known to be NP-complete however, aside from a few results for special cases, we have lacked an in-depth and comprehensive understanding of the complexity of the problems from the viewpoint of natural restrictions of the considered instances. In the first part of our paper, we develop new algorithms and give hardness-proofs in order to obtain a detailed complexity map of (M)RCPSP that settles the complexity of all 1024 considered variants of the problem defined in terms of explicit restrictions of natural parameters of instances. In the second part, we turn to implicit structural restrictions defined in terms of the complexity of interactions between individual activities. In particular, we show that if the treewidth of a graph which captures such interactions is bounded by a constant, then we can solve MRCPSP in polynomial time.

1 Introduction The RESOURCE-CONSTRAINED PROJECT SCHEDULING PROBLEM (RCPSP) provides a generic and well-established framework for the formal description of scheduling problems. RCPSP has been the subject of extensive theoretical as well as empirical research in the context of Artificial Intelligence [Smith and Pyle, 2004; Kuster et al., 2007; Varakantham et al., 2016; Song, 2017], Operations Research and Scheduling [van Bevern et al., 2016; Fu et al., 2010; Fu et al., 2016]; see also the survey [Kolisch and Padman, 2001] and book [Artigues et al., 2008] dedicated to the topic. RCPSP falls within the wider framework of so-called scheduling problems which are classical and have been at the focus of a vast and diverse amount of works [Schwindt and Zimmermann, 2015]. On a high level, in scheduling problems one is given a set of activities that have to be processed in a given time frame

while adhering to certain conditions. Solutions to scheduling problems are also called schedules. RCPSP represents the subclass of scheduling problems where the processing of activities requires the use of resources; these have certain capacities that limit how many activities can be processed concurrently, and activities have certain resource requirements and durations which describe what resources each activity needs to be assigned to and for how long. It is assumed that an activity cannot be interrupted (one also calls this nonpreemptiveness). Now for RCPSP, a schedule consists of an assignment of the activities to certain points in time (simply modeled by natural numbers) such that the time it takes to process all activities satisfies a given makespan bound. Often one requires that activities also adhere to a precedence order. A prominent generalisation of RCPSP that has received considerable attention [Bofill et al., 2017; Barrios et al., 2011; Poppenborg and Knust, 2016] is based on the addition of activity modes, capturing scenarios where it is possible to complete activities in multiple ways each possibly requiring different amounts of time and resources. This gives rise to the MULTI-MODE RESOURCE-CONSTRAINED PROJECT SCHEDULING PROBLEM (MRCPSP).

Contribution. It is known that RCPSP is NP-complete, and in fact remains NP-complete even when we consider only a single resource and when there are no precedence constraints [van Bevern et al., 2016; Garey and Johnson, 1975]. However, so far we have lacked a comprehensive understanding of the complexity of these fundamental scheduling problems under explicit and natural restrictions of considered instances; interestingly, already Blazewicz, Lenstra and Kan (1983) called for such a theoretical investigation in their seminal paper which formalized RCPSP: The obvious research program would be to determine the borderline between easy and hard resource constrained scheduling problems. For example, is (M)RCPSP restricted to instances of constant makespan and number of resources NP-hard, or does the problem become polynomial-time solvable? Our first contribution is a complete complexity map for (M)RCPSP which takes into account all combinations of variants arising from the following explicit restrictions/attributes which are immediately tied to numerical properties of the input or have been established in previous literature:

Fixed upper-bound on number of activities (n), number

Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence (IJCAI-20)

of resources (m), maximum duration of an activity (t), maximum capacity of a resource (c), makespan (Cmax), and/or on the number of activities that can use each resource (rdeg); No precedence constraints ( P); Simple instances, where each activity only uses a single resource (S) (see, e.g., the work of Damay et al. [2007]); Whether we consider modes (MRCPSP) or not (RCPSP); All numbers are encoded in unary1 (U).

With the exception of the modes attribute, we will adopt the convention of listing the attributes considered in a given fragment in angular brackets for instance, MRCPSP c, rdeg refers to instances of MRCPSP where each resource has capacity bounded (by a constant), and each resource is only used by a (constant-)bounded number of activities. Each of the above attributes can be viewed as an independent binary switch ; altogether this amounts to 210 considered fragments of (M)RCPSP. Our first contribution is a complete classification of all of these problems in terms of classical complexity theory; we show that 736 fragments are polynomial-time solvable and 288 are NP-hard. This is achieved by a collection of 3 new hardness proofs (in addition to 4 known NP-hard cases) and 6 polynomial-time algorithms, utilizing a range of diverse algorithmic techniques. An illustration of our complexity map is provided in Figure 1. In the second part of our paper, we shift our focus from explicit restrictions on instances to implicit ones. More specifically, we ask whether one can exploit the structure of interactions between activities and/or resources to lift any of the obtained polynomial-time algorithms towards more general classes of instances. A natural way of capturing such structure is the concept of treewidth. As our second contribution, we show that treewidth allows us to push the frontiers of tractability for MRCPSP when applied to the activity graph a graph which represents activities as vertices and adds edges between activities which interact either by sharing a resource or a precedence constraint.

Related work. While the treewidth of instances has not been considered for RCPSP yet, the parameter has found numerous applications in prominent subfields and problems that are relevant for AI research, such as SAT [Gottlob et al., 2002], ILP [Ganian and Ordyniak, 2018] and CSP [Cohen et al., 2015]. It is worth noting that instances of low treewidth may arise naturally in a variety of problems and settings for example, the treewidth of control flow graphs arising from goto-free programs is known to be at most 6 [Thorup, 1998]. RCPSP is known to be polynomial-time solvable when the poset width of the precedence constraints is bounded [van Bevern et al., 2016].

2 Preliminaries

For an integer i, we use [i] as shorthand for {1, . . . , i}. The function argmin refers to an (arbitrary) argument of the min-

1This captures the distinction between weak and strong NPhardness. Unary instances arise when encoding certain problems.

imum. We assume that N is the set of non-negative integers. For a vector R, we use R[ℓ] to denote its ℓ-th coordinate.

Problem definition. An instance I of MRCPSP is a tuple A, R, C, M, T, Q, <P , Cmax , of

A = {a1, . . . , an} a set of activities; R = {r1, . . . , rm , rm +1, . . . , rm +m } a set of resources, where we distinguish between m renewable (r1, . . . , rm ) and m non-renewable (rm +1, . . . , rm +m ) resources, and let m = m + m ; C : R N a mapping from resources to capacities; M = {M1, . . . , Mn} a set of (pairwise disjoint) activity mode sets, and let B = S i [n] Mi be the set of all modes; T : B N \ {0} a mapping from modes to durations; Q : B Nm a mapping of modes to resource requirements; <P a strict partial order on A which represents precedence constraints; Cmax N is the allowed makespan; we also refer to numbers in [Cmax] {0} as time points or time steps.

A solution or schedule for I is a pair (ω, α), where ω is a mapping from each activity ai to a mode wi Mi and α is a mapping from each ai to a starting time in [Cmax] {0}, satisfying the following four types of constraints.

Makespan constraints: For each activity ai: α(ai) + T(wi) Cmax. Resource constraints: For each resource rℓ: if rℓis renewable, i.e., ℓ [m ], for each time point j [Cmax]: Rj[ℓ] R[ℓ], where Rj denotes the vector of resource capacities being used at time point j formally, Rj = P i:α(ai) j<α(ai)+T (wi) Q(wi); and if rℓis non-renewable, i.e., ℓ [m] \ [m ], P ai A Q(wi)[ℓ] R[ℓ]. Precedence constraints: For each ai, ai A such that ai <P ai : α(ai) + T(wi) α(ai ).

The task in MRCPSP is to decide whether the instance admits a solution (in which case we also wish to compute such a solution), or not. RCPSP is the restriction of MRCPSP to the case where each activity has a single mode and all resources are renewable. In this case, we can simplify the notation by omitting M and having T and Q directly refer to activities in A. The problem definition suggests a number of interesting and natural parameters which we want to consider as flags used to define the basic fragments of (M)RCPSP considered in this paper. A class D of MRCPSP instances has the flag n if there exists some integer z such that each instance in D has at most z activities. The flags m (total number of resources renewable as well as non-renewable), t (maximum value of T), c (maximum value of C), Cmax are defined analogously. D has the flag rdeg if there exists some integer z such that, for each instance I D and for each resource rℓin that instance, there are at most z activities which can use rℓ formally, |{ ai | b Mi, C(b)[ℓ] = 0 }| n z. Intuitively, rdeg represents a natural generalization of

Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence (IJCAI-20)

MRCPSP n MRCPSP rdeg, S, P MRCPSP m, c, Cmax MRCPSP m, c, t, P MRCPSP m, P, Cmax, U MRCPSP m, rdeg

RCPSP c, rdeg, t, P, Cmax, U

RCPSP m, c, t, S, U

RCPSP m, c, S, P, U

RCPSP m, t, S, Cmax, U

RCPSP c, rdeg, t, S, Cmax, U

RCPSP m, t, S, P, U

RCPSP m, t, S, P, Cmax

n S rdeg P Cmax m c m P t c m P Cmax U m rdeg

Figure 1: The obtained complexity map for MRCPSP showing polynomial-time solvable and NP-hard fragments of MRCPSP. Arrows indicate tightness of the polynomially tractable fragments w.r.t. the flags; removing any flag from a tractable fragment results in an NP-hard fragment.

the flag n , since it does not restrict the number of activities globally but only relatively to each resource. Three of the four remaining flags notably the ones signifying the lack of precedence constraints ( P ), an unary encoding of the numbers ( U ), and whether we have modes or not are self-explanatory. The last remaining flag is S (short for simple ), which signifies that for every activity ai in an instance in the class D, there is at most one resource used by ai in any mode formally, i [n] |{ℓ [m] | b Mi Q(b)[ℓ] > 0}| 1. Simple instances represent a middle ground between instances with a single resource and general instances [Damay et al., 2007] and have a natural correspondence to classical scheduling over m types of machines [Gehrke et al., 2018]. We will use |I| to denote the size of a (unary or binary, depending on the flag U ) encoding of the instance I. Treewidth and Graph Representations. A nice treedecomposition T of a graph G = (V, E) is a pair (T, X), where T is a tree rooted at a node r and X is a function that assigns each tree node t a set X(t) = Xt V of vertices such that the following conditions hold:

For every vertex u V , there is a tree node t such that u Xt. For every edge uv E(G) there is a tree node t such that u, v Xt. For every vertex v V (G), the set of tree nodes t with v Xt forms a subtree of T. |Xr| = |Xℓ| = 1 for every leaf ℓof T. There are only three kinds of non-leaf nodes in T: Introduce node: a node t with exactly one child t such that Xt = Xt {v} for some vertex v Xt . Forget node: a node t with exactly one child t such that Xt = Xt \{w} for some vertex w Xt . Join node: a node t with two children t1, t2 such that Xt = Xt1 = Xt2.

The sets Xt are called bags of the decomposition T and Xt is the bag associated with the tree node t. The width of a nice tree-decomposition (T, X) is the size of a largest bag minus 1. The treewidth of a graph G, denoted by tw(G), is the minimum possible width of a nice tree-decomposition of G. For every fixed k, a nice tree-decomposition of a graph G of treewidth k can be computed efficiently if one exists [Bodlaender et al., 2016; Kloks, 1994; Arnborg et al., 1987]. We use X (t) to denote the set of all vertices in bags of the sub-

a3 a4 n = 4, m = 4 Q(b1 1) = (1, 0, 0, 0), Q(b3 1) = (1, 1, 0, 0) Q(b1 2) = (0, 1, 0, 0), Q(b3 2) = (1, 0, 0, 1) Q(b2) = (0, 0, 1, 0), Q(b4) = (0, 0, 0, 1) a4 <P a1 <P a2

Figure 2: Graph representations of a MRCPSP-instance . (A mode is in Mi if i is its upper index, e.g., b1 2 M1.)

tree of T rooted at t. In our initial analysis of the potential applications of treewidth, we will restrict our attention to a natural graph representation of a MRCPSP instance I which captures how activities may interact with each other. Notably, the activity graph GI has vertex set A and edges represent precedences as well as the possibility of using the same resource in particular, its edge set is { aiaj | (aj <P ai) (ai <P aj) ( b Mi, b Mj, ℓ [m] Q(b)[ℓ] = 0 Q(b )[ℓ] = 0) }. An illustration is provided in Figure 2.

3 A Complexity Map for (M)RCPSP

In this section we give the polynomial-time algorithms and lower bounds (NP-hardness proofs) from which the complexity of all fragments obtained by considering any combination of considered flags follows (see Figure 1).

3.1 Polynomially Tractable Fragments We present our six tractability results in an order roughly corresponding to the technical difficulty of the algorithms. Our first result is a simple observation identifying a basic polynomial-time fragment of MRCPSP.

Observation 1. MRCPSP n is in P. Proof Sketch. Branch over all permutations of the activities and all assignments of activities to their modes. In each branch, greedily build a solution which assigns activities to the selected modes and starts them in an order which does not violate the permutation, or decide that this is not possible, in quadratic time. The time complexity of this procedure lies in O(n! Qn i=1 |Mi| |I|2) O(|I|n+2).

The following fragment consisting of simple instances without precedence constraints and with a bound on the number of activities that use any particular resource can be solved via a reduction to the MRCPSP n fragment.

Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence (IJCAI-20)

Corollary 2. MRCPSP rdeg, S, P is in P. Proof Sketch. Since every activity uses at most a single resource (regardless of the mode it is set to), and since there are no precedence constraints between activities, an instance I of MRCPSP rdeg, S, P, can be split into a set of independent instances, each containing a single resource and at most rdeg activities. Using the previous observation this yields an algorithm in O(m rdeg!|I|rdeg+2) O(|I|rdeg+3).

We now proceed to fragments with non-trivial algorithms.

Theorem 3. MRCPSP m, c, Cmax is in P. Proof. Any solution (ω, α) to an instance I contains at most q = Cmax c m modes which use at least one resource i.e., the set B>0 = { b ω(A) | j N : Q(b)[j] > 0 } has cardinality at most q. Let A>0 = {a A | ω(a) B>0} be the set of activities using these modes in the solution. We can solve I using the algorithm A which begins by branching over all subsets of modes of cardinality at most q containing at most one mode from each of the pairwise disjoint Mi as options for B>0. From such a choice for a possible B>0 we infer a corresponding ω by setting ω(ai) = b for ai A>0 whenever B>0 Mi = {b}, and for all other activities ai A \ A>0 choosing ω(ai) as b Mi such that Q(b) = 0m (i.e., b requires no resources) and minimizes T(b) among these modes. It is easy to see that, whenever a solution with the chosen B>0 exists, a solution with the chosen B>0 and deduced ω exists. Now, we proceed similarly as in the proof of Observation 1 in which we branched on the order in which the activities are scheduled in a solution and then greedily constructed α which conforms to this ordering whenever such an α exists. The caveat here is that this exact approach would introduce a linear dependency on n! which is in general not in poly(|I|). Instead, A branches only on the order in which the activities in A>0 are scheduled by a solution, inserts the activities in A \ A>0 into this ordering, at the respective smallest positions respecting the precedence relation, and then a greedy starting time assignment is performed just as before. The overall running time of A can be shown to lie in O(|B|Cmax c m (Cmax c m)! |I|2) O(|I|Cmax c m+2).

The proof strategy for Theorem 3 can be combined with that of Observation 1 to obtain a polynomial-time algorithm when rdeg and m are bounded. The resulting algorithm runs in time O((rdeg m)! |I|rdeg m+2).

Corollary 4. MRCPSP m, rdeg is in P.

The final two (and arguably most difficult) fragments for which we show polynomial-time tractability both have no precedence constraints and have boundedly many resources.

Theorem 5. MRCPSP m, P, Cmax, U is in P. Proof Sketch. Let a resource snapshot be a Cmax m matrix over [c] {0} (i.e., the maximum capacity of a resource). Observe that the number of resource snapshots is upper-bounded by (c + 1)Cmax m. The resource snapshot J of a partial schedule (i.e., a solution restricted to a subset of activities) (ω, α) is the matrix where, for each x [Cmax] and y [m], the entry J[x, y] equals the amount of resource ry left at time step x.

Given an instance I, let Ji be the set of resource snapshots of all partial schedules for the activities { aj | j i }. Clearly, J0 contains a single resource snapshot, namely the one where J[x, y] = C(ry) for all x, y. On the other hand, if Jn = then I is clearly a YES-instance. To prove the theorem, we describe a dynamic programming algorithm A which computes Ji+1 from Ji. A begins by looping over all resource snapshots in Ji, branching over each mode b Mi+1 of activity ai+1 and branching over each starting time s [Cmax T(b)]. For each such choice of resource snapshot J, b and s, it creates a new possible resource snapshot J . If any entry of the constructed J is negative, it is not a resource snapshot and hence not added to Ji+1; otherwise J is added to Ji+1. If the algorithm A results in a set Jn+1 that is non-empty, we can reconstruct a solution from the run of the algorithm by standard means; otherwise we conclude that I is a NOinstance. Note that each combination of mode, starting time and resource snapshot is considered at most once when updating the resource snapshots. Hence time complexity lies in O(|B| Cmax (c + 1)Cmax m) O(|I|Cmax m+1).

Our last algorithm can be viewed as an extension of Theorem 5 to instances of larger makespan, by replacing the bound on the makespan by a weaker restriction, bounding t. This comes at a cost of requiring a bound on c. Theorem 6. MRCPSP m, c, t, P is in P. Proof Sketch. We may assume w.l.o.g. that the image of Q is a subset of [c]m (modes mapped by Q outside of this range are irrelevant because of resource constraints). Define the type of an activity ai A, denoted τ(ai), as { (Q(b), T(b)) | b Mi }. Observe that the property of having the same type describes an equivalence relation between activities, which has at most 2cm t many equivalence classes, each of which we refer to as an activity type. Let T be the set of non-empty activity types. If there is a solution, there is a solution (ω, α) such that maxi [n] α(ai) + T(ω(ai)) t n and any activity with a mode b with T(b) Cmax which requires no resources is scheduled to start at time 0 using mode b. In such a solution at any time point between 0 and t n at most c m of the remaining activities are being processed concurrently as they have to be assigned to modes using at least some resource. For the remaining activities we build up partial solutions ((ω , α ) where ω and α are defined on a subset of A instead of A satisfying all constraints on that subset) along the time steps. We do so by backtracking on the choice of a multiset of at most c m activity types and modes conforming to these activity types such that activities of these type may be scheduled using these modes in each time step. More formally, we iterate through i = 0 . . . min{t n, Cmax} 1. Within this iteration we iterate through the activity types (with multiplicities) that can be scheduled at time step i. To determine these activity types and their multiplicities we maintain, for each partial solution constructed in each iteration, the resource snapshot J ([c] {0})Cmax m (defined as in the proof of Theorem 5) induced by this partial solution and a vector s τ activity type([|τ|] {0}), describing how many activities of each activity type are not yet in the domain of the

Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence (IJCAI-20)

partial solution. A multiset {τ1, . . . , τz} of z c m activity types, can be scheduled at time step i if the multiplicity with which each activity type occurs in the multiset is bounded by the corresponding entry in s and there are (Qj, Tj) τj such that subtracting all Qj from the (i+1)-th through (i+1+Tj)- th rows of J does not result in negative entries in J. For each such choice of {(Qj, Tj) τj | j [z]}, we find an unscheduled activity a with τ(a) = τj and can set ω(a) = b such that (Q(b), T(b)) = (Qj, Tj) and α(a) = i. Appropriate modifications for J and s are straightforward. If we complete iteration min{t n, Cmax} 1 without having scheduled all activities in any encountered solution, we can conclude that no schedule for the instance exists. The described approach is an iterative branching procedure which is exhaustive modulo activity type equivalence. Hence correctness follows from the fact that activities of the same type can easily be interchanged in a schedule by an easy transformation. The complexity lies in O((min{t n, Cmax} 1) (2cm t |B|)c m |I|) O(|I|cm t+2).

3.2 Lower Bounds We now turn towards hardness results for fragments of MRCPSP. First, we state a few previously known lower bounds: Fact 7 (Uetz [2011], Lemma 5.1.1). RCPSP c, rdeg, t, P, Cmax, U is NP-hard. Fact 8 (Blazewicz, Lenstra and Kan [1983], Theorem 7). RCPSP m, c, t, S, U is NP-hard. The third and last known NP-hardness result that we need concerns the fragment RCPSP m, c, S, P, U . Du and Leung (1989, Theorem 2) proved that a scheduling problem equivalent to this fragment is NP-hard (one merely needs to represent the identical machines used in their reduction by capacity units of a single resource). Fact 9. RCPSP m, c, S, P, U is NP-hard. Moreover, it is easy to observe that a trivial reduction from BIN PACKING [Garey and Johnson, 1979] yields: Observation 10. RCPSP m, t, S, P, U is NP-hard. Our following three new reductions complete the complexity map for MRCPSP in terms of explicit restrictions. Theorem 11. RCPSP c, rdeg, t, S, Cmax, U is NP-hard. Proof Sketch. We give a reduction from 3-SAT by constructing an instance I from a 3-CNF formula F as follows. I has Cmax = 3 and all processing times of activities 1. For each variable x in F we create a resource rx with capacity one and two activities x T , x F , each requiring one of rx. Moreover, for each clause C we create a resource r C with capacity 3, and for each literal ℓin C we create one activity Cℓwhich requires one r C. If ℓ= x for some variable x (i.e., ℓis a positive literal), we create the precedence constraint requiring Cℓ to start after x T is completed; otherwise we create the precedence constraint requiring Cℓto start after x F is completed. For each clause C, we now create three new activities C0, C1 and C2, where C0 <P C1 <P C2 and which require 0, 2 and 1 resources of type r C, respectively. This completes our construction. To complete the proof, it suffices to verify that I is a YES-instance iff F is satisfiable.

Theorem 12. RCPSP m, t, S, Cmax, U is NP-hard. Proof Sketch. We give a polynomial-time reduction from the NP-hard CLIQUE problem, which asks whether a given graph contains a clique of a certain size. Given a graph G = (V, G) and a natural number k (i.e., the desired clique size), we construct an RCPSP-instance I as follows. We create an activity av for every vertex v of G and an activity avw for every edge vw of G, and we then set av <P avw and aw <P avw. All activities require one time step to process, and we fix Cmax = 3. The idea of the set-up we describe in the following is to restrict the activities that can be scheduled to start at the first time step to exactly k activities that correspond to vertices. These k vertices should correspond to the vertices of a clique in G. In the next time step, the k (k 1)

2 activities corresponding to the edges of that clique and the remaining vertex activities can be scheduled, allowing for the remaining edge activities to be scheduled in the last time step that Cmax = 3 allows for. For this to work, all we need to do is to restrict the number of vertex activities that can be scheduled to start in the first time point to be exactly k, the number of vertex activities which can start in the second time point to be exactly |V | k and the number of edge activities that can be scheduled to start in the third time point to be exactly |E| k (k 1)

2 . We do this by setting up the resources and resource requirements as follows and introducing filler activities. We consider two resources r1 and r2 with capacities |V | and |E|, respectively. Each av will require one of r1 and each avw will require one of r2. We introduce three further activities a1, a2, a3, each requiring one time step, and set a1 <P a2 <P a3; a1 requires |V | k of r1, a2 requires k of r1, a3 requires k (k 1)

2 of r2. It is easy to verify that I has a solution iff G has a clique of size k.

Theorem 13. RCPSP m, t, S, P, Cmax is NP-hard. Proof. This time, we start from the weakly NP-hard PARTITION problem [Garey and Johnson, 1979]: decide whether a given multiset S = {m1, m2, . . . , mn} of positive integers such that P mi S = 2b can be partitioned into two subsets S1, S2 such that P mi S1 = P mi S2 = b. Given an instance of PARTITION as described above, we create an instance I of RCPSP with a single resource of capacity b. For each number mi S, we now create an activitiy ai with duration 1 which requires mi-many units of our resource. It is now easy to see that the PARTITION instance has a solution iff I has a makespan of 2: indeed, there is a one-to-one correspondence between the activities scheduled at time 0 (in a schedule with makespan 2) and the numbers assigned to S1 (in a solution to PARTITION).

3.3 Summary and Discussion Note that the following modifications leave instances invariant with respect to polynomial-time solvability: (1) in simple instances without precedence constraints one can assume m to be bounded (see the argument used for Corollary 2), and (2) in instances with bounded Cmax one can assume t to be bounded. These two simple observations together with a complete enumeration of all combinations of flags yield that the 6 polynomial-time algorithms, give rise to a total of 736

Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence (IJCAI-20)

fragments of MRCPSP which are in P. Similarly, the 7 hardness results imply a total of 288 NP-hard fragments of MRCPSP. This completely settles the complexity of all fragments of the problem defined in terms of the 10 considered flags.

4 Solving (M)RCPSP via Structural Restriction

Here, we use the structure of interactions between activities to push beyond the frontiers of tractability delimited by the complexity map based on explicit restrictions of instance parameters. As mentioned in the introduction, this approach has been very successful for many other prominent problems, and we believe it is highly promising also for (M)RCPSP. However, due to the sheer volume of possible cases and fragments to consider, the result presented in this section should be viewed primarily as a proof of concept and, perhaps, the tip of a (potentially very large) iceberg. Indeed, a thorough investigation of how the structure of instances can be algorithmically exploited is beyond the scope of this work.

Theorem 14. MRCPSP U can be solved in time O(|I|5tw(GI)), where I is the input instance.

We note that Theorem 14 is a generalization of Observation 1 when dealing with unary instances, since the activity graphs of instances in the MRCPSP n, U fragment have boundedly-many vertices. Similarly, each connected component in the activity graph of an instance in MRCPSP rdeg, S, P, U has boundedly-many vertices, and so the result also generalizes Corollary 2 in the unary setting.

Proof Sketch of Theorem 14. We begin by computing a nice tree-decomposition T = (T, X) of width k = tw(GI) [Arnborg et al., 1987]. Let a configuration β(t) of a node t in T be a tuple (Mode, Time, Mkspan) where

Mode is a mapping from each activity ai Xt to a mode in Mi, Time is a mapping from Xt to [Cmax 1], and Mkspan is an integer from [Cmax].

Intuitively, we use configurations to store possible ways of assigning modes and starting times of activities in Xt that allow to schedule activities in X (t) with makespan Mkspan. For t V (T) we let the record R(t) consist of all admissible configurations of X (t), i.e., (Mode, Time, Mkspan) R(t) iff there is an assignment (satisfying all precedence and other constraints) (ω , α ) of the activities in X (t) with makespan Mkspan such that Mode and Time are the restrictions of ω to Xt and α to Xt respectively. As the total number of configurations is upper-bounded by Cmax k+1 |B|k and the instance is unary, |R(t)| is bounded by a polynomial in |I|. Moreover it is easy to compute R(t) for any leaf t of T by brute-forcing over all assignments and modes of the single activity in that leaf. I is a YES-instance iff the record R(r) for the root r is non-empty moreover, in this case it is easy to reconstruct a solution to I by backtracking from the root r to determine which entries in the records lead to a non-empty R(r). Hence, in order to complete the proof it suffices to show how to compute the records for forget, join and introduce nodes.

If t is a forget node with child t such that Xt \ Xt = {ai}, then for each configuration β(t ) R(t ) we compute a configuration β(t) by removing ai from the two mappings in β(t ). We add each such computed configuration to R(t).

If t is an introduce node with child t such that Xt \ Xt = {ai}, then we branch over all mappings ω (ai) Mi and α (ai) [Cmax 1]. In each branch and for each record (Mode, Time, Mkspan) R(t ), we check whether the instance contains sufficient resources for the activities in Xt to be scheduled at times α Time and in modes ω Mode. Moreover, we check that ai satisfies the precedence constraints w.r.t. the other activities in Xt. If both checks are successful, we check when ai ends based on the current choice of α and ω , and we update Mkspan accordingly (naturally, we discard records where ai ends after Cmax). We then add the configuration with the new Mkspan and with the mappings ω Mode, α Time to R(t).

If t is a join node with children t , t , then we check compatibility (i.e., equality) of every pair of elements of R(t ) and R(t ) and add compatible elements to R(t).

The running time of these steps is dominated by the running time of the join node, which requires time at most (Cmax k+1 |B|k)2 |I|. Hence, the total running time of the algorithm is upper-bounded by O(|I|5k).

5 Concluding Remarks

We introduced a series of new algorithmic upper and lower bounds that together paint a complete picture of the classical complexity of (M)RCPSP in terms of explicit restrictions on its instances. An extension of RCPSP which we did not directly address in this work is RCPSP/max, where instead of simple precedence constraints one can specify a desired maximum and minimum time gap between finishing one and starting another activity. Naturally, all our lower bounds also carry over to this more general problem. Moreover, the three positive results for fragments with precedence constraints (Observation 1, Theorem 3 and Corollary 4) extend to the RCPSP/max setting with minimal changes. It would be interesting to refine the obtained complexity map from the parameterized complexity viewpoint [Downey and Fellows, 2013; Cygan et al., 2015]. In particular, most of the tractability results presented in this paper do not readily translate to fixed-parameter tractability, and it would certainly be worthwhile to determine which parameterizations of (M)RCPSP give rise to fixed-parameter algorithms. Finally, we also indicated how one can algorithmically exploit the structural properties of activity interactions through the use of graph representations and structural parameters. We believe this is a promising direction for future research; for instance, a similar approach could also be used to consider graph representations of interactions between resources.

Acknowledgments

R. Ganian and T. Hamm acknowledge support by the Austrian Science Fund (FWF, project P31336). T. Hamm also acknowledges support by the FWF project W1255-N23.

Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence (IJCAI-20)

References [Arnborg et al., 1987] Stefan Arnborg, Derek G. Corneil, and Andrzej Proskurowski. Complexity of finding embeddings in a k-tree. SIAM J. Algebraic Discrete Methods, 8(2):277 284, 1987. [Artigues et al., 2008] Christian Artigues, Sophie Demassey, and Emmanuel Neron. Resource-Constrained Project Scheduling: Models, Algorithms, Extensions and Applications. ISTE/Wiley, 2008. [Barrios et al., 2011] Agust ın Barrios, Francisco Ballest ın, and Vicente Valls. A double genetic algorithm for the mrcpsp/max. Computers & OR, 38(1):33 43, 2011. [Blazewicz et al., 1983] Jacek Blazewicz, Jan Karel Lenstra, and A. H. G. Rinnooy Kan. Scheduling subject to resource constraints: classification and complexity. Discrete Applied Mathematics, 5(1):11 24, 1983. [Bodlaender et al., 2016] Hans L. Bodlaender, P al Grøn as Drange, Markus S. Dregi, Fedor V. Fomin, Daniel Lokshtanov, and Michal Pilipczuk. A ck n 5-approximation algorithm for treewidth. SIAM J. Comput., 45(2):317 378, 2016. [Bofill et al., 2017] Miquel Bofill, Jordi Coll, Josep Suy, and Mateu Villaret. An efficient SMT approach to solve mrcpsp/max instances with tight constraints on resources. In CP 2017, pages 71 79, 2017. [Cohen et al., 2015] David A. Cohen, Martin C. Cooper, Peter G. Jeavons, and Stanislav Zivny. Tractable classes of binary csps defined by excluded topological minors. In IJCAI 2015, pages 1945 1951, 2015. [Cygan et al., 2015] Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, D aniel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. [Damay et al., 2007] Jean Damay, Alain Quilliot, and Eric Sanlaville. Linear programming based algorithms for preemptive and non-preemptive RCPSP. European J. of Operational Research, 182(3):1012 1022, 2007. [Downey and Fellows, 2013] Rodney G. Downey and Michael R. Fellows. Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, 2013. [Du and Leung, 1989] Jianzhong Du and Joseph Y.-T. Leung. Complexity of scheduling parallel task systems. SIAM J. Discrete Math., 2(4):473 487, 1989. [Fu et al., 2010] Na Fu, Pradeep Varakantham, and Hoong Chuin Lau. Towards finding robust execution strategies for rcpsp/max with durational uncertainty. In ICAPS 2010, pages 73 80, 2010. [Fu et al., 2016] Na Fu, Pradeep Varakantham, and Hoong Chuin Lau. Robust partial order schedules for rcpsp/max with durational uncertainty. In ICAPS 2016, pages 124 130, 2016. [Ganian and Ordyniak, 2018] Robert Ganian and Sebastian Ordyniak. The complexity landscape of decompositional parameters for ILP. Artif. Intell., 257:61 71, 2018.

[Garey and Johnson, 1975] M. R. Garey and David S. Johnson. Complexity results for multiprocessor scheduling under resource constraints. SIAM J. Comput., 4(4):397 411, 1975. [Garey and Johnson, 1979] M. R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979. [Gehrke et al., 2018] Jan Clemens Gehrke, Klaus Jansen, Stefan E. J. Kraft, and Jakob Schikowski. A PTAS for scheduling unrelated machines of few different types. Int. J. Found. Comput. Sci., 29(4):591 621, 2018. [Gottlob et al., 2002] Georg Gottlob, Francesco Scarcello, and Martha Sideri. Fixed-parameter complexity in AI and nonmonotonic reasoning. Artif. Intell., 138(1-2):55 86, 2002. [Kloks, 1994] Ton Kloks. Treewidth, Computations and Approximations, volume 842 of LNCS. Springer, 1994. [Kolisch and Padman, 2001] R. Kolisch and R. Padman. An integrated survey of deterministic project scheduling. Omega, 29(3):249 272, 2001. [Kuster et al., 2007] J urgen Kuster, Dietmar Jannach, and Gerhard Friedrich. Handling alternative activities in resource-constrained project scheduling problems. In IJCAI 2007, pages 1960 1965, 2007. [Poppenborg and Knust, 2016] Jens Poppenborg and Sigrid Knust. Modeling and optimizing the evacuation of hospitals based on the MRCPSP with resource transfers. EURO J. Computational Optimization, 4(3-4):349 380, 2016. [Schwindt and Zimmermann, 2015] Christoph Schwindt and J urgen Zimmermann. Handbook on Project Management and Scheduling Vol.1. Springer, 2015. [Smith and Pyle, 2004] Tristan B. Smith and John M. Pyle. An effective algorithm for project scheduling with arbitrary temporal constraints. In AAAI 2004, pages 544 549, 2004. [Song, 2017] Wen Song. Project scheduling in complex business environments. In AAAI 2017, pages 5052 5053, 2017. [Thorup, 1998] Mikkel Thorup. All structured programs have small tree-width and good register allocation. Inf. Comput., 142(2):159 181, 1998. [Uetz, 2011] Marc Uetz. Algorithms for Deterministic and Stochastic Scheduling. Ph D thesis, 2011. [van Bevern et al., 2016] Ren e van Bevern, Robert Bredereck, Laurent Bulteau, Christian Komusiewicz, Nimrod Talmon, and Gerhard J. Woeginger. Precedenceconstrained scheduling problems parameterized by partial order width. In DOOR 2016, pages 105 120, 2016. [Varakantham et al., 2016] Pradeep Varakantham, Na Fu, and Hoong Chuin Lau. A proactive sampling approach to project scheduling under uncertainty. In AAAI 2016, pages 3195 3201, 2016.

Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence (IJCAI-20)