An Efficient Filtering Algorithm for the Unary Resource Constraint with Transition Times and Optional Activities

Abstract

This paper describes a unified global constraint to model scheduling problems with unary resources, i.e., each resource can process only a single activity at a time. In addition, the constraint enforces sequence-dependent transition times between activities. It often happens that activities are grouped into families with zero transition times within a family. Moreover, some of the activities might be optional from the resource viewpoint (typically in the case of alternative resources). The global constraint unifies reasoning with both optional activities and families of activities. The scalable filtering algorithms we discuss keep a low time complexity of $\mathcal {O}(n \cdot \log (n) \cdot \log (f))$, where n is the number of tasks on the resource and f is the number of families. This results from the fact that we extend the $\varTheta$-tree data structure used for the Unary Resource constraint without transition times. Our experiments demonstrate that our global constraint strengthens the pruning of domains as compared with existing approaches, leading to important speedups. Moreover, our low time complexity allows maintaining a small overhead, even for large instances. These conclusions are particularly true when optional activities are present in the problem.

1 Introduction

Over the last decades, constraint programming has been successfully applied to solve scheduling problems (Baptiste et al. 2006; Baptiste et al. 2001), while substantial improvements are still ongoing (Laborie 2018; Laborie et al. 2018). One reason for this success is the incorporation of operation research techniques into global constraints. In addition to easing the modeling process, they improve solution times by capturing and efficiently solving subproblems of the main problem. This paper describes a unified global constraint to model unary resources with transition times and optional activities.

Unary resources with sequence-dependent transition times (also called set-up times) for non-preemptive activities are common in real-life scheduling problems. One example is quay crane scheduling in container terminals (Zampelli et al. 2013), where the crane is modeled as a unary resource and transition times represent the moves of the crane on the rail between positions where it loads or unloads containers. A second example is the continuous casting scheduling problem (Gay et al. 2014), where a set-up time is required between production programs. Figure 1 illustrates a minimalistic example of two activities running on a unary resource with transition times.

Fig. 1

Two possible schedules for two activities $A_1$ and $A_2$ running on the same unary resource with transition times. They can never overlap in time, so either activity $A_2$ starts after activity $A_1$ has completed, or $A_1$ starts after activity $A_2$ has completed. Moreover, a minimum transition time (represented by the arrows) must occur between the end of an activity and its successor. Notice that the value of the transition depends on the processing order of the activities

Although efficient propagators have been designed for the standard unary resource constraint (UR) (Vilım 2007), transition time constraints between activities generally make the problem harder to solve because the existing propagators do not take them into account. A propagator for the unary resource constraint with transition times (URTT) was recently introduced (Dejemeppe et al. 2015) as an extension to Vilím’s algorithms, in order to strengthen the filtering in the presence of transition times.

Unfortunately, the additional filtering quickly drops in the case of a sparse transition time matrix, which typically occurs when activities are grouped into families with zero transition times within a family. The reason for a weak filtering with sparse matrices is that it is based on a shortest path problem with free starting and ending nodes and a fixed number of edges. The length of this shortest path drops in the case of zero transition times. In addition, while Vilím algorithms allow us to cope with optional activities, the approach from Dejemeppe et al. (2015) does not support them.

The main contribution of the present paper is to introduce a generalized unary resource with transition times that unifies filtering rules and algorithms such that they consider family-based transition times and optional activities. The main asset of our approach is its scalability: we obtain strong filtering while keeping a low time complexity of $\mathcal {O}(n . \log (n) . \log (f))$, for n activities and f families. In general $f \ll n$, hence the theoretical complexity is very close to that of the propagators in Vilım (2007) and Dejemeppe et al. (2015). The filtering is experimentally tested on instances of the job-shop problem with sequence dependent transition times (JSPSDTT), although it can be used for any type of problems, e.g., with other kinds of objective function than the makespan minimization. We first consider the case where it is known prior to search on which machine the activities must be executed, and then the more general case where activities must be executed by exactly one of a set of alternative machines. The results show that our propagator improves the resolution time over existing approaches and is more scalable.

Related work As described in a recent survey (Allahverdi et al. 2008), scheduling problems with transition times can be classified in different categories. First, the activities can be grouped in batches (i.e., a machine allows several activities of the same batch to be processed simultaneously). Transition times may exist between successive batches. A constraint programming (CP) approach for batch problems with transition times is described in Vilım (2007). Secondly, the transition times may be sequence-dependent or sequence-independent. Transition times are said to be sequence-dependent if their durations depend on both activities between which they occur. Transition times are sequence-independent if their durations depend only on the activity after which they take place. The problem category we study in this paper is non-batch sequence-dependent transition time problems.

Over the years, many CP approaches have been developed to solve such problems (Focacci et al. 2000; Artigues et al. 2004; Wolf 2009; Grimes and Hebrard 2010; Dejemeppe et al. 2015). For instance, in Artigues et al. (2004), a traveling salesman problem with time window (TSPTW), relaxation is associated to each resource. The activities used by a resource are represented as vertices in a graph, and edges between vertices are weighted with the corresponding transition times. The TSPTW obtained by adding time windows to vertices from bounds of corresponding activities is then resolved. If one of the TSPTW routes is found unsatisfiable, then the corresponding node of the search tree is pruned. A similar technique is used in Artigues and Feillet (2008) with additional propagators, which are, to the best of our knowledge, the state of the art propagators when families of activities are present. Grimes and Hebrard proposed an efficient solution to job shop with transition times problems by using a simple lightweight CP model combined with restarts and weighted degree search heuristics (Grimes and Hebrard 2010). Recently, a bounded dynamic programming approach (Ozolins 2018) has improved the state of the art of standard benchmarks of the job shop with transition times problem.

Paper outline Section 2 provides the background required to read the paper. The content is then described in a top-down fashion: Sect. 3 describes the filtering rules for the unary resource with transition times and the different algorithms to apply those rules. Then, we explain in Sect. 4 the data structures required by the filtering algorithms. They rely on lower bounds for the minimum total transition time that must hold in a given set of activities. We discuss those lower bounds in Sect. 5. Finally, Sect. 6 compares the results of the different existing approaches for the unary resource with transition times on various applications.

2 Background

Non-preemptive scheduling problems are usually modeled in CP by associating three variables to each activity i: $s_{i}$, $c_{i}$, and $p_{i}$¹ representing, respectively, the starting time, completion time, and processing time of i. These variables are linked together by the following relation: $s_{i} + p_{i} = c_{i}$. Depending on the problem, the scheduling of the activities can be restricted by the availability of different kinds of resources required by the activities. In this paper, we are interested in the unary resource (sometimes referred to as machine or disjunctive resource) and the propagators associated to a single unary resource. Let $T$ be the set of activities requiring the unary resource. The unary resource constraint prevents any two activities in $T$ from overlapping in time:

$$\begin{aligned} \forall i, j \in T: i \ne j \implies (c_{i} \le s_{j}) \vee (c_{j} \le s_{i}) \end{aligned}$$

Transition times The unary resource can be generalized by requiring transition times between activities. They are described by a square transition matrix$tt$ in which $tt _{i,j}$, the entry at line i and column j, represents the minimum amount of time between the activities i and j when i directly precedes j. We assume that transition times respect the triangular inequality. That is, inserting any activity between two activities never decreases the transition time between these two activities: $\forall i, j, k \in T: tt _{i, j} \le tt _{i, k} + tt _{k, j}$.

The unary resource with transition times constraint imposes the following relation:

$$\begin{aligned} \forall i, j \in T: i \ne j \implies (c_{i} + tt _{i,j} \le s_{j}) \vee (c_{j} + tt _{j,i} \le s_{i}) \end{aligned}$$

(URTT)

An example of a transition matrix is given in Fig. 2, where we can notice that it is not symmetric (e.g., $tt _{1,2} = a \ne c = tt _{2,1}$ in Fig. 2). As exemplified, it induces a transition graph that will be used in the forthcoming sections.

Fig. 2

Example of a transition matrix $tt$ and its induced transition graph

Family-based transition times When transition times are present, it is often the case that activities are grouped into families on which the transition times are expressed. Formally, we denote by $F_{i}$ the family of activity i and by $\mathcal {F}$ the set of all families. Moreover, for a given set of activities $\varOmega$, we write $F_{\varOmega } = \left\{ F_{i} \mid i \in \varOmega \right\}$. In a family-based setting, the transition times are described as a square family transition matrix$tt ^\mathcal {F}$ of size $\left| \mathcal {F}\right|$. The transition time between two activities i and j is the transition time between their respective families $F_{i}$ and $F_{j}$, and it is zero if $F_{i} = F_{j}$:²

$$\begin{aligned} \forall i, j \in T: tt _{i, j} = tt _{F_{i}, F_{j}}^\mathcal {F} \wedge \left( F_{i}= F_{j} \implies tt _{F_{i}, F_{j}}^\mathcal {F} = 0 \right) \end{aligned}$$

(1)

Given a set of activities, their families and a transition matrix between families, $tt ^\mathcal {F}$ one can expand $tt ^\mathcal {F}$ into a transition matrix between activities $tt$. $tt$ is then larger and sparser than $tt ^\mathcal {F}$. An example of this expansion is given in Fig. 3, where the family transition graph induced by $tt ^\mathcal {F}$ is also illustrated. Notice that $tt = tt ^\mathcal {F}$ is the special case occurring when each activity is in its own family.

Fig. 3

Example of a family transition matrix $tt ^\mathcal {F}{}$, its induced family transition graph, and the expanded transition matrix $tt$ for five activities with $F_{1} = F_{2} = 1$ and $F_{3} = F_{4} = F_{5} = 2$

Optional activities Some activities can optionally be used by the resource, i.e., it is unknown a priori if a given optional activity must be processed by the resource in the final schedule. This case typically occurs when an activity must run on one of several alternative resources (Focacci et al. 2000), or when so-called conditional time-intervals (Laborie and Rogerie 2008) are available in the solver. Following Vilím’s notation, we call $R$ the set of regular activities (known to be running on the resource) and $O$ the set of optional activities, with $R\cup O= T$ and $R\cap O= \emptyset$.

To model optional activities, an additional boolean variable $v_{i}$ is used to represent the fact that the activity i is used by the machine. We define $R= \{ i \in T: v_{i}\}$. The unary resource with transition times constraint involving optional activities imposes the following relation:

Precedence graph The precedence graph $G= \langle T, E \rangle$ is a data structure (Brucker 1999; Focacci et al. 2000) used to maintain the precedences between activities of a given resource. In this graph, each vertex represents a given activity, and there is a directed edge from a vertex i to vertex j if and only if activity i precedes activity j, i.e., $c_{i} + tt _{i, j} \le s_{j}$. In Barták and Čepek (2010), the authors describe propagation rules for the precedence graph while taking optional activities into account.

One can use the precedence graph to make search decisions by adding edges in order to impose precedences between activities. A recent CP approach (Grimes and Hebrard 2010) demonstrated experimentally that branching on the precedences can be effective,³ using smart search techniques based on a domain/weighted-degree heuristic, rather than sophisticated propagators.

Finally, from a filtering perspective, additional precedences can be detected by computing the transitive closure of the graph.

Bounds of a set of activities$\varOmega$ The earliest starting time of an activity i is denoted $est _{i}$ and its latest starting time is denoted $lst _{i}$. The domain of $s_{i}$ is thus the interval $[ est _{i}.. lst _{i}]$. Similarly, the earliest completion time of i is denoted $ect _{i}$ and its latest completion time is denoted $lct _{i}$. The domain of $c_{i}$ is hence the interval $[ ect _{i}.. lct _{i}]$. These definitions can be extended to a set of activities $\varOmega$. For instance, $est _{\varOmega }$ is the earliest time when any activity in $\varOmega$ can start and $ect _{\varOmega }$ is the earliest time when all activities in $\varOmega$ can be completed. We also define $p_{\varOmega } = \sum _{j\in \varOmega } p_{j}$ to be the sum of the processing times of the activities in $\varOmega$. While one can directly compute $est _{\varOmega } = \min \left\{ est _{j} : j \in \varOmega \right\}$ and $lct _{\varOmega } = \max \left\{ lct _{j} | j \in \varOmega \right\}$, it is NP-hard (Vilım 2007) to compute the exact values of $ect _{\varOmega }$ and $lst _{\varOmega }$. Instead, one usually computes a lower bound for $ect _{\varOmega }$ and an upper bound for $lst _{\varOmega }$, as we will see in this paper.

3 Global filtering rules and propagation algorithms

This section first describes the inference rules of the unary resource without transition times. Those rules are then extended in order to handle transition times. We also describe the different algorithms in order to compute them efficiently. The data structures required by the algorithms are described in Sect. 4.

3.1 Filtering rules for the unary resource

The filtering rules presented in Vilım (2007) for the UR constraint fall into several categories known as Overload Checking (OC), Detectable Precedences (DP), Not-First/Not-Last (NF/NL), and Edge Finding (EF). They are valid for the general definition of $ect _{\varOmega }$ of the earliest completion time of a set of activities $\varOmega \subseteq T$. However, since the computation of its exact value is NP-hard, their implementation relies on an efficient computation of a lower bound $ect _{\varOmega }^{LB0}$, defined as:

$$\begin{aligned} ect _{\varOmega }^{LB0} = \max _{\varOmega ' \subseteq \varOmega } \left\{ est _{\varOmega '} + p_{\varOmega '} \right\} \end{aligned}$$

(2)

To define the different rules, we use the notation $ect _{\varOmega }$, although $ect _{\varOmega }^{LB0}$ is used in practice, as we will use a stronger lower bound under the presence of transition times later in this paper. Each rule has a symmetric counterpart for $lst _{\varOmega }$ that can easily be retrieved from the given definitions.⁴

Overload checking This rule tries to detect an inconsistency given the current domains. Intuitively, for a set of regular activities $\varOmega \subseteq R$, if the earliest completion time is found to be larger than the latest completion time, an infeasibility is detected. Additionally, if $\varOmega$ is extended with an optional activity i such that there would be an inconsistency, we know that the activity cannot be executed by the machine. Formally, we have:

$$\begin{aligned} \forall \varOmega \subseteq R{}, \forall i \in (T{\setminus } \varOmega ) : ect _{\varOmega \cup \{ i \}} > lct _{\varOmega \cup \{ i \}} \implies \lnot v_{i} \end{aligned}$$

(OC)

Notice that if $i \in R$ and $v_{i} = \mathbf {false}$, the constraint is infeasible.

Detectable precedences This rule detects new precedences between pairs of activities. The reasoning uses the set of activities $DPrec (R, i)$ that can be detected as preceding a given activity i based on the current domains. It is defined as:

$$\begin{aligned} DPrec (R, i) = \{ j \ne i \in R: ect _{i} > lst _{j}\} \end{aligned}$$

(DPrec)

The inference rule states that the earliest start time of an activity i must at least be the earliest completion time of the set of activities that are detected as preceding i, that is $DPrec (R, i)$. Formally:

$$\begin{aligned} \forall i \in T{} : v_{i} \implies est _{i} \leftarrow \max ( est _{i}, ect _{ DPrec (R, i)}) \end{aligned}$$

(DP)

Notice that only the activities known to be running on the resource can be used to update other activities, hence the use of $DPrec (R, i)$ and not $DPrec (T, i)$. In the contrary case, all activities (including optionals) can be updated.

Precedences that do not belong to $DPrec (R, i)$, but nevertheless must be respected, are called non-detectable precedences (Vilım 2007). They originate from the problem itself or branching decisions. Non-detectable precedences are not enforced by the DP rule but with binary propagators or a propagator based on a precedence graph.

Not-last When a given activity i has a latest starting time that is strictly smaller than the earliest completion time of a set of regular activities $\varOmega$, this activity cannot be scheduled as the last one of the set $\varOmega \cup \{i\}$. Its latest completion time can therefore be reduced to the maximum latest start time of the activities in $\varOmega$:

Edge finding This rule detects new edges in the precedence graph: if adding an activity i to a set of activities $\varOmega$ leads to an earliest completion larger than the latest completion of the set, then the activity i must succeed the activities in $\varOmega$:

Update of domains of optional activities Except in the case of the Overload Checking rule, the domain of an optional activity is updated only when it is known to be running on the resource (i.e., $v_{i} = \mathbf {true}$). However, the inference about the domain of this activity if it is running on the resource can be useful to other inference rules. Therefore, the domain is not updated until $v_{i} = \mathbf {true}$, but the inference on the domain if the activity runs on the resource is saved internally and used by all inference rules. Example 1 illustrates a case where this is beneficial.

Example 1

Let us consider four activities, as represented in Fig. 4. Green activities are regular activities, while $A_3$ is optional. If the DP rule is applied to the set $\{A_1, A_2, A_3\}$ and $A_3$ is a regular activity, $est _{3}$ will be updated to 9 (see the red bracket). $A_3$ is optional, so we only save this update internally. If the OC rule is applied to the set $\{A_3, A_4\}$ with $est _{3} = 9$ instead of $est _{3} = 6$, one can deduce that $v_{3} = \mathbf {false}$.

Fig. 4

The inference that can be made on optional activities must be communicated to other inference rules. Activity $A_3$ is optional and the others are regular. The DP rule applied to the set $\{A_1, A_2, A_3\}$ leads to $est _{3} = 9$. Applying the OC rule the set $\{A_3, A_4\}$ with that information allows inferring $v_{3} = \mathbf {false}$

Filtering limitation due to transition times Under the presence of transition times, the rules can be improved, as illustrated in Example 2. In the next section, we strengthen the lower bound of $ect _{\varOmega }$ so that it takes the transition times into account.

Example 2

Consider a set of three regular activities $\varOmega =\left\{ 1, 2, 3\right\}$ as shown in Fig. 5. Consider also, for simplicity, that all pairs of activities from $\varOmega$ have the same transition time $tt _{i, j} = 3 \, \forall i,j \in \{1, 2, 3\}$. The OC rule detects a failure when $ect _{\varOmega }^{LB0} > lct _{\varOmega }$. The lower bound is:

$$\begin{aligned} ect _{\varOmega }^{LB0} = est _{\varOmega } + \sum _{i \in \varOmega } p_{i} = 0 + 5 + 5 + 3 = 13 \end{aligned}$$

As we have $lct _{\varOmega } = \max _{i \in \varOmega } \; lct _{i} = lct _{2} = 17$, the OC rule from Vilım (2007), combined with the transition times binary decomposition (Eq. URTTO), does not detect a failure. However, as there are three activities in $\varOmega$, at least two transitions occur between these activities and it is actually not possible to find a feasible schedule. Indeed, taking these transition times into account, one could compute $ect _{\varOmega } = 13 + 2 \cdot tt _{i, j} = 13 + 2 \cdot 3 = 19> 17 = lct _{\varOmega }$, and thus detect the failure.

Fig. 5

Example illustrating the missed failure detection of OC when not considering transition times

3.2 Extending the filtering rules with transition times

Let $\varPi _{\varOmega }$ be the set of all possible permutations of activities in $\varOmega$. For a given permutation $\pi \in \varPi _{\varOmega }$, where $\pi (i)$ is the activity taking place at position i, we can define the total time spent by transition times, $tt _{\pi }$, as follows:

$$\begin{aligned} tt _{\pi } = \sum _{i = 1}^{|\varOmega | - 1} tt _{\pi (i), \pi (i + 1)} \end{aligned}$$

A lower bound for $ect _{\varOmega }$ that considers transition times can then be defined as:

$$\begin{aligned} ect _{\varOmega }^{LB1} = \max _{\varOmega ' \subseteq \varOmega } \left\{ est _{\varOmega '} + p_{\varOmega '} + \min _{\pi \in \varPi _{\varOmega '}} tt _{\pi } \right\} \end{aligned}$$

(3)

Unfortunately, computing this value is NP-hard, as computing the optimal permutation $\pi \in \varPi$ minimizing $tt _{\pi }$ amounts to solving a traveling salesman problem. Since embedding an exponential algorithm in a propagator is generally impractical, a looser lower bound should be used instead.

For each possible subset of cardinality $k \in [0..|T|]$, we compute the smallest transition time permutation on the set $T$ of all activities requiring the resource:

$$\begin{aligned} \underline{ tt }{\left( k \right) } = \min _{\{\varOmega ' \subseteq T: \ |\varOmega '|=k \} } \left\{ \min _{\pi \in \varPi _{\varOmega '}} tt _{\pi } \right\} \end{aligned}$$

(4)

For each k, the lower bound computation thus requires one to find the shortest node-distinct ($k-$1)-edge path between any two nodes of the transition graph (see Sect. 2), which is also NP-hard, as the traveling salesman problem can be reduced to this problem when $k = |T|$. Since one has to solve $|T|$ NP-hard problems in pre-computation (one for each cardinality k), we proposed in Dejemeppe et al. (2015) various lower bounds to achieve the computation in polynomial time. They are described in Sect. 5. Notice that we have $\underline{ tt }{\left( 0 \right) }=\underline{ tt }{\left( 1 \right) }=0$.

Our final lower bound formula for the earliest completion time of a set of activities, making use of pre-computed lower bounds on transition times, is:

$$\begin{aligned} ect _{\varOmega }^{LB2} = \max _{\varOmega ' \subseteq \varOmega } \left\{ est _{\varOmega '} + p_{\varOmega '} + \underline{ tt }{\left( |\varOmega '| \right) } \right\} \end{aligned}$$

(5)

The different lower bounds of $ect _{\varOmega }$ can be ordered as follows:

$$\begin{aligned} ect _{\varOmega }^{LB0} \le ect _{\varOmega }^{LB2} \le ect _{\varOmega }^{LB1} \le ect _{\varOmega } \end{aligned}$$

Limitation An important limitation of this approach arises in the context of sparse transition matrices, which typically occurs when activities are grouped in families (see Sect. 2). Indeed, when there exists a node-distinct path with K zero-transition edges, we have: $\underline{ tt }{\left( k \right) } = 0 \,\; \forall k \in [0\ldots K + 1]$. The pruning achieved by the propagator is then equivalent to one of the original algorithms from Vilım (2007), which has been shown to perform poorly when transition times are involved (see Dejemeppe et al. 2015). This is illustrated in the next example.

Example 3

Consider again the three activities $\varOmega = \left\{ 1, 2, 3\right\}$ shown in Fig. 5 with activity 1 belonging to family $F_{1}$, activity 2 to family $F_{2}$, and activity 3 to family $F_{3}$. The transition times are equal to 3 between activities from different families and equal to 0 between activities of the same family. Assume that 3 additional activities (not represented) also belong to family $F_{1}$. Since the transition times between any pair of activities from a same family is 0, we have that $\underline{ tt }{\left( 2 \right) } = \underline{ tt }{\left( 3 \right) } = 0$ and $ect _{\varOmega }^{LB2} = 13 = ect _{\varOmega }^{LB0}$, hence the OC of Dejemeppe et al. (2015) is unable to detect the failure.

To cope with this limitation, we will use a stronger lower bound by counting the number of different families present in a set $\varOmega$ of activities instead of the cardinality of $\varOmega$. This amounts to finding the shortest node-distinct ($k-$1)-edge path in the family transition graph (see Sect. 2) instead of the transition graph. Counting the number of families results in nonzero lower bounds even for small sets, assuming that there are no zero transition times between families. Formally, Eq. (5) is replaced by:

$$\begin{aligned} ect _{\varOmega }^{LB3} = \max _{\varOmega ' \subseteq \varOmega } \left\{ est _{\varOmega '} + p_{\varOmega '} + \underline{ tt }{\left( |F_{\varOmega '}| \right) } \right\} \end{aligned}$$

(6)

where $F_{\varOmega } = \left\{ F_{i} \mid i \in \varOmega \right\}$. The term $\underline{ tt }{\left( |F_{\varOmega '}| \right) }$ in Eq. (6) is pre-computed using the same lower bounds as before, but using $tt ^\mathcal {F}$ instead of $tt$. Notice that if $tt = tt ^\mathcal {F}$, we have $ect _{\varOmega }^{LB2} = ect _{\varOmega }^{LB3}$.

Lemma 1

In the presence of families, $ect _{\varOmega }^{LB2} \le ect _{\varOmega }^{LB3}$.

Proof

The family transition graph induced by $tt ^\mathcal {F}$ is isomorphic to a subgraph of the transition graph induced by $tt$, and any (shortest) path induced by $tt ^\mathcal {F}$ has a corresponding valid path induced by $tt$. Moreover, a shortest path of exactly k edges induced by $tt$ has a length that is at most equal to a shortest path of exactly k edges induced by $tt ^\mathcal {F}$.$\square$

3.3 Adapting the algorithms

We adapt the original algorithms of Vilım (2007) in order to consider transition times. Most of the modifications actually impact the underlying $\varTheta$-tree and $\varTheta$-$\varLambda$-tree data structures (described in Sect. 4), hence, the algorithms are similar to the original ones. In our opinion, this is a strength of our approach. The algorithms described in this section apply the rules given in Sect. 3.1. As mentioned in Sect. 3.1, counterparts of those rules can be applied using the same algorithms on mirror activities. Importantly, one must also transpose the transition matrix.

Notation We denote by $ect ^*_{\varTheta }$ a lower bound of $ect _{\varTheta }^{LB3}$ that will be used by the different algorithms. We describe in Sect. 4.1 the $\varTheta$-tree data structure that is used to compute this value. Moreover, following Vilím’s notation, we will use a specific set of gray activities$\varLambda \subseteq T$ such that $\varLambda \cap \varTheta = \emptyset$. For a given set $\varTheta$, this set is used to evaluate how $ect _{\varTheta }$ would evolve if one of the gray activities of $\varLambda$ were to be added to the set $\varTheta$. Formally, we are interested in computing

$$\begin{aligned} \overline{ect} _{\left( \varTheta , \varLambda \right) } = \max ( ect _{\varTheta }, ect _{\varTheta \cup \{i\}}, i \in \varLambda ) \end{aligned}$$

If $\exists i \in \varLambda : ect _{\varTheta \cup \{i\}} > ect _{\varTheta }$, we say the gray activity i is responsible for the value $ect _{\varTheta \cup \{i\}}$. Responsible activities are used in the Overload Checking and the Edge-Finding algorithms described in this section. We discuss how to find the responsible activity in Sect. 4.2. Once more, we actually compute a lower bound of $\overline{ect} _{\left( \varTheta , \varLambda \right) }$, written $\overline{ect} ^{*}_{\left( \varTheta , \varLambda \right) }$. Section 4.2 describes the $\varTheta$-$\varLambda$-tree data structure used to compute this value efficiently.

Overload checking The checker (see Algorithm 3.1) goes over each activity in non-decreasing order of $lct _{i}$. For each activity, if it is not yet known if it will be executed by the resource (verified by checking the size of the domain of the variable $v_{i}$ in line 3), it is added to the set $\varLambda$ (line 4) and the next activity is considered. If the activity must run on the resource, it is added to the set $\varTheta$. The OC rule is then applied: if the earliest completion time of the current set $\varTheta$ is larger than the latest completion time of the activity i we just added to $\varTheta$, the activity i cannot be executed on the machine. Since i is not optional, a feasible schedule cannot be found (see lines 7–9). The current optional activities in $\varLambda$ are then possibly updated in lines 10–14: as long as it is possible to find an optional activity o such that adding it to $\varTheta$ would lead to an overload, it is inferred that o cannot be executed by the machine, and o is removed from $\varLambda$.

Detectable precedences Algorithm 3.2 describes how the DP inference rule can be applied. It first sorts the regular activities by non-decreasing order of latest start time and inserts them into a queue Q (line 2).⁵ Then, it traverses all the activities (including optional ones as they can be updated): for each activity i, as long as its earliest completion time is strictly larger than the latest start time of the first activity j in Q, j is removed from the queue and added to the set $\varTheta$. Once this is done, $\varTheta$ is the set $DPrec (R, i)$ (see DPrec), and we can apply the DP rule (line 9). Moreover, as transition times are involved, the minimal transition from any family $F_{j} \in F_{\varTheta }$ to the family $F_{i}$ can also be added as it was not taken into account in the computation of $ect ^*_{\varTheta }$. This transition is the minimal one from any family $F_{j} \in F_{\varTheta }$ to $F_{i}$, because we do not know which activity will be just before i in the final schedule. The detectable precedence update rule becomes:

$$\begin{aligned} est _{i}' \leftarrow \max \left\{ est _{i}', ect ^*_{\varTheta } + \underset{f \in F_{\varTheta }}{\min }\; tt _{f, F_{i}}^\mathcal {F}\right\} \end{aligned}$$

(DPUR)

Notice that the value $\underset{f \in F_{\varTheta }}{\min }\; tt _{f, F_{i}}^\mathcal {F}$ can only be available in $\mathcal {O}(1)$ if it was pre-computed for any subset of families, which is exponential in $|\mathcal {F}|$ and therefore problematic if there are many families. It can also be computed in linear time, but it would increase the time complexity of the overall algorithm. In practice, the implementation can make use of the minimum transition from any family $f \in \mathcal {F}{} {\setminus } F_{i}$if$F_{i} \notin F_{\varTheta }$, and 0 otherwise.

When no transition times are involved, detected precedences are all eventually propagated, i.e., i precedes j if and only if $est _{j} \ge ect _{i}$ and $lct _{i} \le lst _{j}$ (see Vilım 2007). In our case, this is not guaranteed: if a precedence is detected for a given pair of activities i and j, it is not ensured that after propagation we will have $est _{j} \ge ect _{i} + tt _{i,j}$ and $lct _{i} \le est _{j} - tt _{i,j}$. The reason is that $ect ^*_{\varTheta }$ uses a lower bound on the transition times in $\varTheta$. One must therefore rely on branching (e.g., on the precedence graph) to ensure a given detected precedence is completely propagated.

Not-last The NL inference rule can be applied with Algorithm 3.3, similarly to Algorithm 3.2: a queue Q is filled with regular activities,⁶ and all activities (regular and optional) are then traversed in non-decreasing order of latest completion time. For each activity i, activities from Q having a larger latest starting time than the latest completion time of i are removed from the queue and added to the set $\varTheta$ (lines 5–8). $\varTheta$ is then the set of activities with a latest starting time strictly smaller than the latest completion time of i. The NL rule can then be applied (lines 9–11). An analogous reinforcement to the DP rule due to transition times can be applied when updating $lct _{i}$ (see line 10).

Edge finding Unlike the previous algorithms, Algorithm 3.4 starts with a set $\varTheta$ filled with all regular activities. We also directly fill the set $\varLambda$ with the optional activities⁷ so that their domain can be updated but they can never be used to update other activities (since they will not be in the set $\varOmega$ in the EF rule). A queue Q of regular activities sorted in non-increasing order of latest completion time is also initialized. The algorithm traverses this queue and the activities in $\varTheta$ are progressively removed from $\varTheta$ and added to the set $\varLambda$ of gray activities. For each activity j popped out of the queue Q, the algorithm first checks for an overload before j is removed from $\varTheta$ (lines 5–7). This is equivalent to what is done in Algorithm 3.1 for regular activities, so it is actually facultative. The activity j is then grayed: It is transferred from $\varTheta$ to $\varLambda$. This means it is no longer in the set $\varTheta$ we consider, but it will be part of the activities used to infer what would happen if one of them were added to $\varTheta$. Lines 10–14 apply the EF rule to the current gray activities such that $\overline{ect} ^{*}_{\left( \varTheta , \varLambda \right) } > lct _{j}$: as long as adding one of the gray activities would imply an overload (i.e., condition in line 10 is verified), we identify which gray activity i is responsible for this potential overload, we update its earliest start time, and remove it from $\varLambda$. The EF rule is strengthened using transition times similarly to the DP and NL rules.

Precedence graph propagator Algorithm 3.5 uses the precedence graph data structure (see Sect. 2). It relies on the topological order of all known precedences (i.e., edges in the digraph) since if i precedes j in the topological order of the precedence graph, the earliest start time of i cannot be influenced by the domain of $s_{j}$ and $c_{j}$. Algorithm 3.5 first builds a queue Q of activities in topological order of the precedence graph. It then traverses Q and, for each activity i, it applies the pairwise rule URTTO for all its successors in the precedence graph. In addition, if a successor j of an activity i is known to be running on the resource (i.e., $v_{j}$ is true), then one can use j to update the latest completion time of the activity i (see lines 6–8).

Important note Notice that when transition times are involved, this algorithm is mandatory in order to ensure the pruning is complete: because we use a lower bound of the earliest completion time of a set of activities $\varTheta$ in the other algorithms ($ect ^*_{\varTheta }$), they are not sufficient to ensure correctness of a given (partial) assignment of all $s_{i}, \, \forall i \in T$.

Complexities Sect. 4 describes data structures that allow us to retrieve $ect ^*_{\varTheta }$ in $\mathcal {O}(1)$ while addition/removal of an activity to/from $\varTheta$ is performed in $\mathcal {O}(\log (|T|) \cdot \log (|\mathcal {F}|))$. All algorithms but the Precedence Graph, therefore, have a time complexity of $\mathcal {O}(|T| \cdot \log (|T|) \cdot \log (|\mathcal {F}|))$. The precedence graph propagator runs in $\mathcal {O}(|T|^2)$.

4 Extending the $\varTheta$-tree and $\varTheta$-$\varLambda$-tree data structures

To efficiently use the sets $\varTheta$ and $\varLambda$, the algorithms described in Sect. 3.3 rely on the so-called $\varTheta$-tree and $\varTheta$-$\varLambda$-tree data structures, introduced by Vilím. Those structures are used to efficiently and incrementally compute $ect ^*_{\varTheta }$ and $\overline{ect} ^{*}_{\varTheta }$ for sets of activities $\varTheta$ and $\varLambda$. This section describes how those can be extended to handle (family-based) transition times.

4.1 Extended $\varTheta$-tree

A $\varTheta$-tree is a balanced complete binary tree in which each leaf represents an activity from a set $\varTheta$ and each internal node n gathers information about the set of activities represented by the leaves under this node, denoted $Leaves (n)$. We write $l (n)$ for the left child of n and $r (n)$ for the right one. Leaves are ordered in non-decreasing order of the earliest start time of the activities: for two activities i and j, if $est _{i} < est _{j}$, then the leaf representing i is at the left of the leaf representing j.

The main value stored in a node n is the lower bound of $ect _{ Leaves (n)}$, denoted $ect ^*_{n}$. To be able to compute this value incrementally upon insertion or deletion of an activity in the $\varTheta$-tree, one needs to maintain additional values.

Without any transition times involved, Vilím has shown (Vilım 2007) that by defining $ect ^*_{n} = ect _{ Leaves (n)}^{LB0}$, it suffices to store additionally $p_{n} = p_{ Leaves (n)}$. In a leaf n representing an activity i, one can compute $p_{n} = p_{i}$ and $ect ^*_{n} = ect _{i}$. In an internal node n, one can compute:

$$\begin{aligned} \begin{array}{lll} p_{n} &{} = &{} p_{ l (n)} + p_{ r (n)} \\ ect ^*_{n} &{} = &{} \max \left\{ ect ^*_{ r (n)}, ect ^*_{ l (n)} + p_{ r (n)} \right\} \end{array} \end{aligned}$$

Hence, the values depend only on the values stored in the two children.

In our case, we would like instead to define $ect ^*_{n} = ect _{ Leaves (n)}^{LB3}$ in order to take (family-based) transition times into account. However, this value cannot easily be computed incrementally, so we compute a lower bound, i.e., $ect ^*_{n} \le ect _{ Leaves (n)}^{LB3}$. In addition to $ect ^*_{n}$, one needs to store not only $p_{n}$, but also $F_{n} = F_{ Leaves (n)}$, the set of the families of the activities in $Leaves (n)$. In a leaf n representing an activity i, one can compute $p_{n} = p_{i}$, $ect ^*_{n} = ect _{i}$, and $F_{n} = \{ F_{i} \}$. In an internal node n, one can compute:

$$\begin{aligned} \begin{array}{lll} p_{n} &{} = &{}p_{ l (n)} + p_{ r (n)} \\ F_{n}&{} = &{}F_{ l (n)} \cup F_{ r (n)} \\ ect ^*_{n} &{}=&{} \max \left\{ \begin{array}{l} ect ^*_{ r (n)}\\ ect ^*_{ l (n)} + p_{ r (n)} + \underline{ tt }{\left( \left| F_{ r (n)}{\setminus }F_{ l (n)}\right| + 1 \right) } \end{array}\right. \\ \end{array} \end{aligned}$$

Intuitively, $ect ^*_{n}$ is maximized either by considering only activities in $r (n)$, or by adding to $ect ^*_{ l (n)}$ the processing times and (a lower bound of) the transition times due to activities in $r (n)$. In the latter case, only additional families are counted to compute the lower bound on transition times, that is, the families that are present in the right child but not in the left one. Hence, the cardinality of the set $F_{ r (n)}{\setminus }F_{ l (n)}$ is considered. Notice we always add one family to the count because of the definition of $\underline{ tt }{\left( k \right) }$ (remember $\underline{ tt }{\left( 0 \right) }=\underline{ tt }{\left( 1 \right) }=0$).

Before we prove this lower bound is correct, let us prove in Lemma 2 a property of the function $\underline{ tt }{\left( k \right) }$.

Lemma 2

$\forall i \in [0..|T|], k \in [0\ldots i] : \underline{ tt }{\left( i \right) } \ge \underline{ tt }{\left( k \right) } + \underline{ tt }{\left( i - k + 1 \right) }$

Proof

The optimal path $p^ opt$ in the transition graph leading to the value $\underline{ tt }{\left( i \right) }$ can be split into two subpaths:

• $p^ opt _{[1\ldots k]}$ with $k-1$ edges. Its total length is greater than or equal to $\underline{ tt }{\left( k \right) }$ (as $\underline{ tt }{\left( k \right) }$ is the minimum), the length of the optimal path with $k-1$ edges.

• $p^ opt _{[k\ldots i]}$ with $i-k$ edges. Its total length is greater than or equal to $\underline{ tt }{\left( i - k + 1 \right) }$, the length of the optimal path with $i-k$ edges.

Therefore $\underline{ tt }{\left( n \right) } = p^ opt _{[1\ldots k]} + p^ opt _{[k\ldots i]} \ge \underline{ tt }{\left( k \right) } + \underline{ tt }{\left( i - k + 1 \right) }$.$\square$

Lemma 3

$\forall$ node n in a $\varTheta$-tree$: ect ^*_{n} \le ect _{ Leaves (n)}^{LB3}$

Proof

By induction. If n is a leaf representing activity i, then $ect ^*_{n} = ect _{i} = ect _{\{i\}}^{LB3}$. Otherwise, our induction hypothesis is that $ect ^*_{ l (n)} \le ect _{ Leaves ( l (n))}^{LB3}$ and $ect ^*_{ r (n)} \le ect _{ Leaves ( r (n))}^{LB3}$. Let us call $\varOmega ^{LB3}\subseteq Leaves (n)$ the optimal set to compute $ect _{ Leaves (n)}^{LB3}$. For space reasons, we write $L(\varOmega )$ to denote $Leaves (\varOmega )$.

One can consider two cases:

• $ect ^*_{n} = ect ^*_{ r (n)}$. We have $ect ^*_{ r (n)} \le ect _{L( r (n))}^{LB3}$ (by induction) and $ect _{L( r (n))}^{LB3} \le ect _{L(n)}^{LB3}$ (by definition). Therefore, $ect ^*_{n} \le ect _{L(n)}^{LB3}$.

• $ect ^*_{n} = ect ^*_{ l (n)} + p_{ r (n)} + \underline{ tt }{\left( |F_{ r (n)}\,\backslash \, F_{ l (n)}|+ 1 \right) }$. Then, we have:

  $$\begin{aligned} ect ^*_{n}&\le ect _{L( l (n))}^{LB3} + p_{ r (n)} + \underline{ tt }{\left( |F_{ r (n)}\,\backslash \, F_{ l (n)}|+ 1 \right) } \\&\qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad {\hbox {(by induction)}} \\&= \max _{\varOmega _l \subseteq L( l (n))} \left\{ est _{\varOmega _l} + p_{\varOmega _l}\right. \\&\quad \left. + \underline{ tt }{\left( |F_{\varOmega _l}| \right) } \right\} + p_{ r (n)} + \underline{ tt }{\left( |F_{ r (n)}\,\backslash \, F_{ l (n)}|+ 1 \right) } \\&= \max _{\varOmega _l \subseteq L( l (n))} \{ est _{\varOmega _l} + p_{\varOmega _l \cup L( r (n))} \\&\quad + \underline{ tt }{\left( |F_{\varOmega _l}| \right) } + \underline{ tt }{\left( |F_{ r (n)}\,\backslash \, F_{ l (n)}|+ 1 \right) } \} \\&= \max _{\varOmega _l \subseteq L( l (n))} \{ est _{\varOmega _l \cup L( r (n))} + p_{\varOmega _l \cup L( r (n))} \\&\quad + \underline{ tt }{\left( |F_{\varOmega _l}| \right) } + \underline{ tt }{\left( |F_{ r (n)}\,\backslash \, F_{ l (n)}|+ 1 \right) } \} \\&\qquad \qquad \qquad \qquad \qquad {(\text {since } est _{\varOmega _l} = est _{\varOmega _l \cup L( r (n))})} \\&\le \max _{\varOmega _l \subseteq L( l (n))} \{ est _{\varOmega _l \cup L( r (n))} + p_{\varOmega _l \cup L( r (n))}\\&\quad + \underline{ tt }{\left( |F_{\varOmega _l \cup L( r (n))}| \right) } \} \\&\qquad \qquad \qquad {\hbox {(by Lemma~2)}} \\&\le ect _{L(n)}^{LB3} \\&\qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad {\hbox {(by definition)}} \end{aligned}$$

$\square$

Complexity We use bitsets to represent the set of families in each node. The space complexity of the $\varTheta$-tree is therefore $\mathcal {O}(|T| \cdot |\mathcal {F}|)$. The set operations we use are union, intersection, difference and cardinality. Using bitsets and assuming $|\mathcal {F}| \le 64$, the first three operations are $\mathcal {O}(1)$ and the last is $\mathcal {O}(\log (|\mathcal {F}|))$ with a binary population count⁸ (Warren 2013). The time complexity of insertion and deletion of an activity in the $\varTheta$-tree is therefore $\mathcal {O}(\log (|T|) \cdot \log (|\mathcal {F}|))$.

Example 4

Let us consider the activities presented in Fig. 6 (left). The family transition matrix $tt ^\mathcal {F}$ is given in Fig. 6 (center). The pre-computed values of $\underline{ tt }{\left( k \right) }$ are reported in Fig. 6 (right). Figure 7 illustrates the extended $\varTheta$-tree when all activities are inserted. Note that the value at the root of the tree is indeed a lower bound since we have $ect ^*_{\varTheta } = 75 \le ect _{\varTheta }^{LB3} = 80 \le ect _{\varTheta } = 85$.

Fig. 6

Four activities and their families (left), transition times for the families (center), and pre-computed lower bounds for the transition times (right)

Fig. 7

A $\varTheta$-tree when all activities of Fig. 6 are inserted

Fig. 8

A $\varTheta$-$\varLambda$-tree when all activities of Fig. 6 are inserted and activities 3 and 4 are gray

4.2 Extended $\varTheta$-$\varLambda$-tree

Algorithms 3.1 and 3.4 require an extension of the original $\varTheta$-tree, called $\varTheta$-$\varLambda$-tree (Vilım 2007). In this extension, leaves are marked as either white or gray. White leaves represent activities in the set $\varTheta$ and gray leaves represent activities that are in a second set, $\varLambda$, with $\varLambda \cap \varTheta = \emptyset$. In addition to $ect ^*_{n}$, a lower bound to the $ect _{}$ of $\varTheta$, a $\varTheta$-$\varLambda$-tree also aims at computing $\overline{ect} ^{*}_{n}$, which is a lower bound to $\overline{ect} _{(\varTheta , \varLambda )}$, the largest $ect _{}$ obtained by including one activity from $\varLambda$ into $\varTheta$:

$$\begin{aligned} \overline{ect} _{(\varTheta , \varLambda )} = \max _{i \in \varLambda } \ ect _{\varTheta \cup \{i\}} \end{aligned}$$

In addition to $p_{n}$, $ect ^*_{n}$, Vilím’s original $\varTheta$-$\varLambda$-tree also maintains $\overline{p}_{n}$ and $\overline{ect} ^{*}_{n}$, respectively, corresponding to $p_{n}$ and $ect ^*_{n}$, if a single gray activity $i \in \varLambda$ in the sub-tree rooted at n maximizing $ect _{\textit{Leaves}(v) \cup \left\{ i\right\} }$is included.

Our extension to the $\varTheta$-$\varLambda$-tree is similar to the one outlined in Sect. 4.1 for the $\varTheta$-tree: in addition to the previous values, each node also stores $\overline{p}_{n}$ and $\overline{F}_{n}$ in order to compute the lower bound $\overline{ect} ^{*}_{n}$.

Adapting the rules for the $\varTheta$-$\varLambda$-tree requires caution when families are involved. In Vilım (2007) and Dejemeppe et al. (2015), the rules only implicitly use the information about which gray activity is considered in the update. In our case, the rules must consider explicitly where the responsible gray activity (i.e., the gray activity maximizing $\overline{ect} ^{*}_{}$ at the root node) is located. Hence, when a node n is updated, one first updates $\overline{ect} ^{*}_{n}$ with the rule:

$$\begin{aligned} \begin{array}{lll} \overline{ect} ^{*}_{n} &{}=&{} \max \left\{ \begin{array}{lr} \overline{ect} ^{*}_{ l (n)} + p_{ r (n)} + \underline{ tt }{\left( |F_{ r (n)}\,\backslash \, \overline{F}_{ l (n)}| + 1 \right) } &{} \quad \text {(Case A)}\\ ect ^*_{ l (n)} + \overline{p}_{ r (n)} + \underline{ tt }{\left( |\overline{F}_{ r (n)}\,\backslash \, F_{ l (n)}| + 1 \right) } &{}\quad \text {(Case B)}\\ \overline{ect} ^{*}_{ r (n)} &{}\quad \text {(Case C)}\\ \end{array}\right. \end{array} \end{aligned}$$

Case A occurs when it is (locally) considered that the gray responsible activity that maximizes $\overline{ect} ^{*}_{n}$ is among $Leaves ( l (n))$. Cases B and C correspond to the opposite case (i.e., the responsible activity is among $Leaves ( r (n))$). Depending on which value gets assigned to $\overline{ect} ^{*}_{n}$, the values $\overline{F}_{n}$ and $\overline{p}_{n}$ of the node n are updated as follows:

$$\begin{aligned} \begin{array}{lll} \overline{F}_{n} &{}=&{} \left\{ \begin{array}{ll} \overline{F}_{ l (n)} \cup F_{ r (n)} &{}\quad \text {if (Case A)} \\ F_{ l (n)} \cup \overline{F}_{ r (n)} &{}\quad \text {otherwise} \end{array}\right. \\ \overline{p}_{n} &{}=&{} \left\{ \begin{array}{ll} \overline{p}_{ l (n)} + p_{ r (n)} &{}\quad \text {if (Case A)} \\ p_{ l (n)} + \overline{p}_{ r (n)} &{}\quad \text {otherwise} \end{array}\right. \end{array} \end{aligned}$$

If a leaf n represents an activity i, then we simply have $\overline{ect} ^{*}_{n}= ect _{i}$, $\overline{p}_{n} = p_{i}$, and $\overline{F}_{n} = \{ F_{i} \}$. The rules for $p_{n}$, $ect _{n}$, and $F_{n}$ are as presented in Sect. 4.1, but one must also define, for a gray leaf n, $ect ^*_{n}=-\infty$, $p_{n} = 0$, and $F_{n} = \emptyset$.

Example 5

Let us reconsider the activities from Fig. 6. Figure 8 illustrates a $\varTheta$-$\varLambda$-tree where all activities have been inserted, but where activities 3 and 4 have been grayed. Notice that activity 4 is the gray responsible one (since $70 > 25 + 20 + 5$) and therefore $\overline{p}_{} = 55$ and $\overline{F}_{} = \{F_1, F_3\}$ in the root node.

As for the extended $\varTheta$-tree introduced in Sect. 4.1, the time complexity for the insertion and the deletion of an activity is $\mathcal {O}(\log (|T|) \cdot \log (|\mathcal {F}|))$. Table 1 summarizes the complexities of all operations on the $\varTheta$-$\varLambda$-tree.

Table 1 Worst-case time complexities of operations on the $\varTheta$-$\varLambda$-tree

4.3 Strengthening $ect ^*_{\varTheta }$ and $\overline{ect} ^{*}_{(\varTheta , \varLambda )}$

The value $ect ^*_{\varTheta }$ is a lower bound for $ect _{\varTheta }^{LB3}$. One can actually strengthen the value computed with the $\varTheta$-tree to get a value closer to $ect _{\varTheta }^{LB3}$. An idea from Brucker and Thiele (1996) and Vilım and Barták (2012) that is also used in Artigues and Feillet (2008) is to pre-compute the exact minimum total transition time for every subset of families.⁹

For a subset of families $\mathcal {F}' \subseteq \mathcal {F}$, let $tt \left( {\mathcal {F}'} \right)$ denote the minimum total transition time used for any activity set $\varTheta$ such that $F_{\varTheta }=\mathcal {F}'$. Assuming $tt \left( {F_{\varTheta }} \right)$ is accessible in $\mathcal {O}(1)$, each time we access to the value $ect ^*_{\varTheta }$ in the algorithms of Sect. 3.3, we can also compute

$$\begin{aligned} ect _{\varTheta }^{ tsp } = est _{\varTheta } + p_{\varTheta } + tt \left( {F_{\varTheta }} \right) \end{aligned}$$

without changing the complexity of the algorithms. The value $tt \left( {F_{\varTheta }} \right)$ must be pre-computed for all subsets of families, so this is tractable only if there are few families¹⁰, as it requires solving many traveling salesman problems of increasing sizes. Moreover, it is necessary to store $2^{|\mathcal {F}|}$ integers in an array. One can then use the bitset representation of a given set $\mathcal {F}' \subseteq \mathcal {F}$ as an index in the array in order to access the value in $\mathcal {O}(1)$. The value $est _{\varTheta }$ can be easily maintained in the $\varTheta$-tree, and the values $p_{\varTheta }$ and $F_{\varTheta }$ can be obtained in $\mathcal {O}(1)$ in the root node of the $\varTheta$-tree.

The value $ect _{\varTheta }^{ tsp }$ can be larger than $ect ^*_{\varTheta }$ because it uses $tt \left( {F_{\varTheta }} \right)$ instead of $\underline{ tt }{\left( |F_{\varTheta }| \right) }$. This typically occurs when $ect _{\varTheta }^{ tsp } = ect _{\varTheta }^{LB3}$. On the contrary, $ect _{\varTheta }^{ tsp }$ might be smaller than $ect ^*_{\varTheta }$ since $ect _{\varTheta }^{ tsp }$ always considers all activities in $\varTheta$, but never a subset $\varTheta ' \subset \varTheta$. Yet, $ect ^*_{\varTheta }$ can rely on a subset $\varTheta ' \subset \varTheta$ such that $est _{\varTheta } + p_{\varTheta } < est _{\varTheta '} + p_{\varTheta '}$. Hence, the algorithms in Sect. 3.3 should use the maximum of those two values instead of $ect ^*_{\varTheta }$ in order to strengthen the filtering.

One can also consider the family of the updated activity: similarly to $tt \left( {\mathcal {F}'} \right)$, let us write $tt \left( {F_{i} \rightarrow \mathcal {F}'} \right)$ the minimum transition time when the processing starts with some activity of the family $F_{i} \in \mathcal {F}'$, and $tt \left( {\mathcal {F}' \rightarrow F_{i}} \right)$ when it completes with an activity of the family $F_{i} \in \mathcal {F}'$. We can pre-compute these values for every set of families $\mathcal {F}' \subseteq \mathcal {F}$ and every family $F_{i} \in \mathcal {F}'$ with a dynamic program running in $\varTheta (|\mathcal {F}|^2 \cdot 2^{|\mathcal {F}|})$ and requiring $\varTheta (|\mathcal {F}| \cdot 2^{|\mathcal {F}|})$ of memory. For instance, for $tt \left( {F_{i} \rightarrow \mathcal {F}'} \right)$, one defines:

$$\begin{aligned} \left\{ \begin{array}{lr} tt \left( {F_{i} \rightarrow \{F_{i}\}} \right) = 0 &{}\quad \forall F_{i} \in \mathcal {F}\\ tt \left( {F_{i} \rightarrow \{\mathcal {F}' \cup F_{i}\}} \right) = \underset{F_{j} \in \mathcal {F}'}{\min } \{ tt _{F_{i},F_{j}}^\mathcal {F} + tt \left( {F_{j} \rightarrow \mathcal {F}'} \right) \} &{}\quad \forall \mathcal {F}' \subset \mathcal {F}, \forall F_{i} \in \mathcal {F}{\setminus } \mathcal {F}' \end{array} \right. \end{aligned}$$

In the case of Detectable Precedences, Eq. DPUR finally becomes:

$$\begin{aligned} est _{i}' \leftarrow \max \left\{ est _{i}', ect ^*_{\varTheta } + \underset{f \in F_{\varTheta }}{\min }\; tt _{f, F_{i}}^\mathcal {F}, est _{\varTheta } + p_{\varTheta } + tt \left( {F_{\varTheta } \rightarrow F_{i}} \right) \right\} \end{aligned}$$

The same idea can be used to strengthen $\overline{ect} ^{*}_{(\varTheta , \varLambda )}$:

$$\begin{aligned} \overline{ect} _{(\varTheta , \varLambda )}^{ tsp } = \min \{ est _{\varTheta }, est _{r}\} + p_{\varTheta \cup \{ r\}} + tt \left( {F_{\varTheta \cup \{ r\}}} \right) \end{aligned}$$

where r is the gray responsible activity (see line 11 in Sect. 3.4). A subtle point is that the responsible activity r is not accessible from the $\varTheta$-$\varLambda$-tree as for $\overline{ect} ^{*}_{(\varTheta , \varLambda )}$, so we should iterate over all $r' \in \varLambda$ to maximize $\overline{ect} _{(\varTheta , \varLambda )}^{ tsp }$. We therefore use the responsible activity of $\overline{ect} ^{*}_{(\varTheta , \varLambda )}$ to compute $\overline{ect} _{(\varTheta , \varLambda )}^{ tsp }$.

5 Lower bounds on the minimum total transition of a set of activities

In this section, we describe different lower bounds (Dejemeppe et al. 2015) for Eq. 4, recalled hereafter:

$$\begin{aligned} \underline{ tt }{\left( k \right) } = \min _{\{\varOmega ' \subseteq T: \ |\varOmega '|=k \} } \left\{ \min _{\pi \in \varPi _{\varOmega '}} tt _{\pi } \right\} \end{aligned}$$

For each k, one has to find the shortest node-distinct ($k-$1)-edge path between any two nodes of the (family) transition graph (see Sect. 2), which is NP-hard, as the traveling salesman problem can be reduced to this problem when $k = |T|$. Even though $\underline{ tt }{\left( k \right) }$ is to be pre-computed, it is desirable to have polynomial pre-computation, which justifies the use of the lower bounds explained in this section. A more detailed description can be found in Dejemeppe (2016); we summarize them here so that the paper is self-contained. Notice that the lower bounds do not dominate each other, so the final lower bound for a given cardinality k will be the maximum between the different lower bounds for this cardinality.

Minimum weight forest This lower bound consists of finding the set of $k - 1$ edges with a minimum cost. Basically, we use Kruskal’s algorithm (Kruskal 1956) to prevent cycles in our selection. As soon as $k - 1$ edges have been selected, the algorithm is stopped. The result being a minimum weight forest in the general case; it is a lower bound of our original problem since it does not ensure obtaining a simple path in the graph.

Shortest walk A dynamic program can be used to compute a lower bound on the minimum transition in a set of cardinality k. The idea is to compute a shortest walk with $k - 1$ edges in the transition graph. Formally, we define $SW (k',i)$ as the shortest walk with $k'$ edges from any node to node i. To compute this value for all number of edges $k'$ and every node i, we rely on the following $\mathcal {O}(k \cdot T^2)$ dynamic program:

$$\begin{aligned} SW (0,i)&= 0, \forall i \in [1..T] \\ SW (k+1,i)&= \min _{j}{ SW (k,j) + tt _{i,j}}, \forall i \in [1..T] \end{aligned}$$

The lower bound for a given cardinality k is, finally:

$$\begin{aligned} \min _{i}{ SW (k,i)} \end{aligned}$$

Notice this lower bound ensures the solution to be a walk in the graph, but it does not prevent cycles. However, as suggested in Christofides et al. (1981), one can strengthen the bound by avoiding 1-cycles, i.e., cycles of the form $i \rightarrow j \rightarrow i$.

Minimum assignment A lower bound based on a minimum assignment problem was proposed by Brucker and Thiele (1996): two sets containing all the nodes of the transition graph are constructed and a minimum assignment of k edges is searched for, that is, the edges always link an activity of one set with an activity of the other set. One can model this problem as a minimum-cost maximum-flow problem in a manner similar to the reduction of a minimum weight bipartite matching.

Lagrangian relaxation To find the shortest simple path with k edges in the transition graph, one can add a source (node 0) and a sink node (node n + 1) to the transition graph so that the edges from the source node to all nodes (but the sink one) and the edges from the nodes (except the source one) to the sink node have a transition of zero. Then, one can solve the problem by searching for the shortest path from the source to the sink with $k + 2$ edges. This can be solved with the following integer linear program:

$$\begin{aligned} \mathbf{minimize} \qquad&\sum _{i} \sum _{j}\; tt _{i,j} \cdot x_{i,j}\\ \mathbf{such} that \qquad&\sum _{j}\; x_{0,j} - \sum _{j}\; x_{j, 0} = 1 \\&\sum _{j}\; x_{n + 1, j} - \sum _{j}\; x_{j, n + 1} = -1 \\&\sum _{j}\; x_{i, j} - \sum _{j}\; x_{j, i} = 0 \\&\sum _{i} \sum _{j}\; x_{i, j} = k \\&x_{i,j} \in \{0, 1\} \end{aligned}$$

(CARD)

This problem is NP-hard, therefore, we solve a Lagrangian relaxation instead: we remove the edge cardinality constraint (i.e., Eq. CARD) and penalize its violation in the objective function. Without the cardinality constraint, the shortest path can be computed with the Bellman–Ford algorithm (Bellman 1956; Moore 1959), which is also able to detect a negative cycle. If this occurs, we use a classic linear relaxation instead of using the Bellman–Ford algorithm.

Exact shortest path for every subset Using the definitions given in Sect. 4.3, one can compute the best possible lower bound based on the cardinality of a set of activities/families. We compute the value of the shortest path for every subset, and for each cardinality k, we take the smallest shortest path of all subsets of cardinality k:

$$\begin{aligned} \underline{ tt }{\left( k \right) } = \min _{|\mathcal {F}'| = k} tt \left( {\mathcal {F}'} \right) \end{aligned}$$

The other lower bounds described before are upper-bounded by this approach. However, it is not polynomial, so it can only be used for problems with a few activities/families.

6 Experimentations

We split our evaluation into two parts: First, we consider the case where there are no optional activities, which has been more widely studied in the literature. The experiments were conducted on JSPSDTT instances. Second, we consider the same problem with alternative machines that are modeled using optional activities from the resource point of view.

Setting We used AMD Opteron processors (2.7 GHz), the Java 8 Runtime Environment and the constraint solver OscaR (OscaR Team 2012). The memory consumption was limited to 4GB.

Replay evaluation In order to derive fair and representative conclusions about the propagators only (i.e., by removing the effects of the search heuristic), we used the Replay evaluation methodology (Van Cauwelaert et al. 2015, 2017). First, for each instance, a baseline model is used to generate a search tree. This baseline model is, among the different compared approaches, the one that prunes the fewest domains. Once the search tree is generated, it is replayed separately with each model. A replay basically consists in reapplying the exact same sequence of modifications to the constraint store (e.g., the branching constraints) that were used to generate the search tree with the baseline model.

The performance of those replays is then used to construct so-called performance profiles (Dolan and Moré 2002), which we built with a public web tool (Van Cauwelaert et al. 2016) made available to the community.¹¹ Performance profiles are cumulative distribution functions of a performance metric ratio $\tau$. In our case, $\tau$ is a ratio of either time or number of backtracks. In the case of time, the function is defined as:

$$\begin{aligned} F_{m}(\tau ) = \frac{1}{|\mathcal {I}|} \left| \left\{ i\in \mathcal {I}: \frac{ time _ replay (m,i)}{\underset{m' \in M}{\min } time _ replay (m',i)} \le \tau \right\} \right| \end{aligned}$$

(7)

where $\mathcal {I}$ is the set of considered instances, $m$ is a model and $M$ is the set of all models. The function is similar for the number of backtracks.

A performance profile that is above the other ones in its graphical representation shows a higher performance than the others. This specific representation allows us to have a global understanding at a glance of the actual performances of a propagator over a full set of instances.

Let us, for example, consider a performance profile with a performance metric ratio $\tau$ representing the time needed to replay instances using a given propagator. If this performance profile has a point in (30% of instances, 2.5), it means that for 30% of the considered instances, the propagator takes at most 2.5 times as much time as the baseline model.

6.1 Experimentations without optional activities

6.1.1 Problem instances

We have used two sets of instances. First, we used the standard t2ps instances from Brucker and Thiele (1996). However, there are only 15 of them, and we wanted to evaluate instances with more families, jobs, and machines in order to challenge the scalability of the different approaches. We therefore generated a new set of 315 instances, here referred to as uttf, with up to 50 jobs, 15 machines and 30 families. The transition times between two families were randomly picked between 5 and 50, and duration of activities were randomly taken between 10 and 100.¹²

6.1.2 State-of-the-art filtering with families

Based on the definition of $tt \left( {F_{i} \rightarrow \{\mathcal {F}'\}} \right)$, two propagators are introduced in Artigues and Feillet (2008):

• A DP-like propagator called UpdateEarliestStart running in $\mathcal {O}(n^2 \cdot \log (n))$.

• An EF-like propagator called PrimalEdgeFinding running in $\mathcal {O}(|\mathcal {F}| \cdot n^2)$.

Although the filtering obtained with these propagators can be stronger than their counterparts from Vilım (2007) and our extensions, the time complexity of the propagators is quite high as compared to $\mathcal {O}(n \cdot \log (n) \cdot \log (|\mathcal {F}|))$. In addition, they do not make use of a Not-First/Not-Last rule and the pre-computation of the minimum exact transition times for every subset of a family is tractable only for small (typically less than 10) values of $|\mathcal {F}|$.

6.1.3 Compared propagators

We compare models with the following propagators for Eq. (URTTO):

• $decomp$: binary decomposition of Equation (URTT) only.

• $urtt$: propagators for URTT from Dejemeppe et al. (2015).

• $art _ ex$: propagators of Artigues and Feillet (2008) using exact values for $tt \left( {\mathcal {F}} \right)$, $tt \left( {F_{} \rightarrow \mathcal {F}} \right)$ and $tt \left( {\mathcal {F} \rightarrow F_{}} \right)$.

• $art _ lb$: propagators of Artigues and Feillet (2008) adapted to make use of cardinality-based lower bounds from Sect. 5 for $tt \left( {\mathcal {F}} \right)$, $tt \left( {F_{} \rightarrow \mathcal {F}} \right)$ and $tt \left( {\mathcal {F} \rightarrow F_{}} \right)$.

• $urttf _ ex$: propagators introduced in this paper making use of the exact values for $\underline{ tt }{\left( \left| \mathcal {F}\right| \right) }$ computed with $\min _{\mathcal {F}': |\mathcal {F}'| = |\mathcal {F}|} tt \left( {\mathcal {F}'} \right)$.

• $urttf _ lb$: propagators introduced in this paper making use of lower bounds of Sect. 5 for $\underline{ tt }{\left( |\mathcal {F}| \right) }$.

6.1.4 Replay evaluation

To generate the search trees, the Conflict Ordering Search (Gay et al. 2015) was used, as it has been shown to be a good search strategy for scheduling problems. The baseline model was $decomp$. The generation lasted for 300 s, and we enforced a timeout of 1800 s for the replay. The running times reported here do not take into account the pre-computation step since they are negligible (generally less than 2 s and max 10 s).

Fig. 9

Performance profiles on t2ps instances for the time metric

Fig. 10

Performance profiles on t2ps instances for the number of backtracks metric

6.1.5 Results on the t2ps instances

Figures 9 and 10 provide the performance profiles for the time and number of backtracks, respectively. Figure 10 shows that, interestingly, $urttf _ lb$ prunes exactly as much as $urttf _ ex$. This is due to the fact that our lower bounds are here able to compute the same values than $\min _{\mathcal {F}': |\mathcal {F}'| = |\mathcal {F}|} tt \left( {\mathcal {F}'} \right)$. This suggests that we often do not have to compute the exact values for $tt \left( {\mathcal {F}} \right)$ with the resource-consuming dynamic program, which is interesting since it is not tractable when there are many families. We can see that from a time perspective (Fig. 9), our approach is the fastest for $\sim$ 80% of the instances ($urttf _ ex$ being here equivalent to $urttf _ lb$, see the function in $\tau = 1$ in Fig. 9). But our approach is also robust, as the other instances (i.e., the remaining 20%) are solved within a factor $\tau < 2$ compared to the best model for those remaining instances. Considering the number of backtracks, our approach generally achieves less pruning than $art _ ex$ (not more than three times), but substantially more than $urtt$. This lack of pruning as compared to $art _ ex$ is compensated in practice by the low time complexity. Although not reported, we tried to combine $urttf _ ex$ and $art _ ex$ and the performances were close to those of $art _ ex$ alone, thus inducing only a small overhead when $urttf _ ex$ does not provide additional pruning.

Fig. 11

Performance profiles on uttf instances with strictly less than 20 families for the time metric

Fig. 12

Performance profiles on uttf instances with more than 20 families for the time metric

6.1.6 Results on the uttf instances

First of all, we consider the approaches $art _ ex$ and $urttf _ ex$ that were unable to solve (i.e., times out by default) the 120 instances (out of 315) with 20 families or more, since the pre-computation becomes too expensive in terms of CPU and memory usage according to our 4Gb limitation.

Figures 11 and 12 provide the time performance profiles for the instances with strictly less than and with more than 20 families, respectively. Figure 11 shows that our approach still outperforms the other ones, although it is the fastest on a smaller percentage of instances than for the t2ps instances. The instances being less structured, the gain in pruning is weaker as compared to the decomposition. However, our method catches up very quickly; for example, it is at most $\sim 1.3$ and 2 times slower than the best approach for almost 60% and 80% of the instances, respectively. Another interesting point is that $urttf _ ex$ and $urttf _ lb$ have very similar time performances, while the values for $\underline{ tt }{\left( k \right) }$ were here generally different (not reported here). This means that computing the exact values for $tt \left( {\mathcal {F}} \right)$ is not mandatory¹³ when used with our propagators, which is profitable since we also target scalability in terms of number of families.

Regarding the instances with more than 20 families (Fig. 12), our approach is significantly better than the other ones, as we are the fastest on almost 70% of the instances and it is at most four times slower than the best approach on the remaining instances. This teaches us that when more families are involved, our approach is both efficient and robust.

Fig. 13

Performance profiles on generated instances of the job-shop problem with two alternative resources

Fig. 14

Performance profiles on generated instances of the job-shop problem with three alternative resources

6.2 Experimentations with optional activities

Optional activities are typically used when modeling problems in which activities can be processed on a set of $a$ alternative resources. Hence, in order to experiment with our approach when optional activities are involved, we experimented on JSPSDTT with alternative resources. In particular, we used an approach that consists in duplicating $a$ times the activities and the resources of an original job-shop problem (Focacci et al. 2000). For each of the original activities, exactly one of its duplicates must then be executed on its corresponding duplicated machine. This amounts to solving the same problem as the original one, but with the additional liberty of choosing on which one of the $a$ alternative machines an activity will be executed.

Formally, for a given activity i and $a$ duplications, we write $i_k$ the $k^ th$ duplicate of activity i. To ensure that one and only one of the alternative machines is used by the activity i, we force one and only one of the $a$ duplicates $i_k$ to be used by its corresponding duplicated machine:

$$\begin{aligned} \exists \, ! \, k \in [1, a] : v_{i_k} \end{aligned}$$

Moreover, the job precedences between activities must be respected by all duplicates, i.e., if there is a precedence between two activities i and j in the original problem, then we must have:

$$\begin{aligned} \forall k \in [1, a] \quad \forall k' \in [1, a] : k \ne k' \implies c_{i_k} \le s_{j_{k'}} \end{aligned}$$

Search heuristic To our knowledge, few search heuristics are actually devoted to the presence of optional activities. For our evaluation, we used a strategy from Barták that avoids taking decisions about optional activities that will actually not be executed in the final schedule (Barták 2008; Cappart et al. 2018). This is important, as it prevents the search from exploring the exact same schedule several times.

The heuristic has two levels: On the first level, it decides whether an activity i is valid or not, i.e., it branches on $v_{i}$. On the left branch, it imposes $v_{i}= true$ and will then branch using the second level, as explained hereafter. On the right branch, $v_{i}= false$ is posted and the activity i will not be considered deeper in the tree; another activity $j \ne i$ will then be considered to be branched on using the first level. In the second level, precedences between i and all activities $j : \lnot (v_{j} = \mathbf {false})$ (i.e., still possibly running on the same resource) will be imposed, until no more precedences involving i can be decided. The first level of branching is then used with a different activity j.

To decide which activity should be branched on first, the activity with the smallest $est _{}$ is chosen (ties are broken by smallest duration and $ect _{}$). Finally, once all decisions have been made, one can assign all activities to their $est _{}$, since the objective is here to minimize the makespan.

Settings We generated 100 instances similar to the five small t2ps instances, i.e., with 10 jobs, 5 machines and 5 families. The instances were kept small because duplicating the alternatives already increased the search space substantially. The models we compared are the same ones as before, but using the approach from Artigues et al., as they do not deal with optional activities. Our approach uses lower bounds for $\underline{ tt }{\left( |\mathcal {F}| \right) }$. We also consider an additional model, called $urV$, that uses the filtering from Vilím.

We also used the Replay evaluation: the generation lasted at most 300 s and we filtered out instances that were solved within less than a second.

Results First, we consider the problem with two alternative resources. The results are given in Fig. 13. A first observation is that $urttf _ lb$ is almost always the fastest and it solves all instances in $\tau < 2$, which makes our approach appealing. Interestingly, one can also see that the profiles of the other approaches are, in this case, quite similar. Finally, for $\sim$ 10% of the instances, $urttf _ lb$ provides a speed-up of $\sim 32$ as compared to the other approaches (see the profiles in $\tau = 32$ in Fig. 13).

Let us now consider the results (given in Fig. 14) when we have three alternative resources. While our approach is still clearly the best one for similar reasons, one can now better separate $decomp$, $urV$, and $urtt$: $urV$ is better than $decomp$ and $urtt$ is better than $urV$. Still, $urtt$ and $urV$ are close to each other and tend to converge. This shows, again, the benefits of reasoning with families of activities.

7 Conclusion

This paper has extended the algorithms and data structures for the unary resource, taking into account family-based transition times in order to perform additional propagation. The method also handles optional activities so that one can model more general problems (e.g., involving alternative resources). The original data structures and algorithms have been adapted accordingly. The approach is lightweight from both the time and space perspectives. Experiments conducted on the JSPSDTT have demonstrated that our work provides a substantial gain and is quite robust to changes in instance characteristics (e.g., number of activities and families).

We would like to consider other types of problems (e.g., the traveling salesman problem with time windows) and combine this work with the use of good lower bounds in a branch-and-bound setting. More importantly, when there are no families defined a priori in an instance, we want to study the benefit of first creating them by means of clustering algorithms and then using the filtering introduced in this paper. This approach might prove to be helpful when the intra-cluster transition times are significantly smaller than the inter-cluster ones.