Packing-based branch-and-bound for discrete malleable task scheduling

The relevance of parallel tasks (Drozdowski, 2009) goes beyond the initial context of multiprocessor scheduling rooted in information technology environments. In fact, tasks or activities that require more than one processor or, more generally, resource unit at a time are also typically found in manufacturing or project scheduling environments. The background of the research presented in this paper is a petrochemical research and development facility, conducting product tests on different kinds of resources. The resource capacities are aggregated to daily or weekly buckets, rendering the problem a multi-capacitated one. Each product test involves a number of test specimen, each having the same resource requirements. There is no upper limit on the number of specimen of the same product processed per day or week, but once the product test is started, gaps in its processing time window, that is, days or weeks where no specimen of this product are processed, are to be avoided. One of the objectives in the associated scheduling problem is to keep the utilization as high as possible in earlier time periods, while it is allowed to drop toward the end of the planning horizon. This requirement originates from the rolling-horizon nature of planning, aiming at both freezing parts of the schedule and leaving space for new tests. The analogy of this kind of problem to a multiprocessor scheduling problem with a total weighted completion time objective is pointed out in Braune (2019).

As a consequence, the problem can be seen from two different perspectives. The first, low-level perspective is the one of the task slices. Related work in the corresponding literature is concerned with chains of rigid unit-time tasks (see, e.g., Blazewicz & Liu, 1996). However, those chains do not allow to simultaneously process two tasks of the same chain and also do not account for maximum delays. The second point of view emanates from the high-level tasks. Treating them as a compound during scheduling may result in varying resource requirements over time due to the potential concurrent processing of two or more of its slices. Modifying a task’s resource requirements at scheduling time is known as malleability in the associated literature (see, e.g., Blazewicz et al., 2006). In the discrete case, the smallest increment or decrement is one single resource unit. For the problem at hand, in contrast, the smallest step size is a slice, leading to a somewhat more coarse-grained malleability. To the best of the author’s knowledge, this kind of discrete malleable tasks has not been covered in the literature so far. No matter which viewpoint is adopted, the special type of constraints prohibit an immediate adaptation of existing solution approaches from this area of research.

The solution method proposed in this paper is based on a bin packing reformulation of the scheduling problem in question. The problem mapping itself arises from the unit-time slices of fixed size and the capacity limitation of the multiprocessor resource. Although existing work in this area in fact also covers precedence constraints, this specific combination of minimum and maximum delays has not been considered so far. The methodological contributions of this paper can be identified as follows:Finally, all the presented techniques are successfully embedded into a dedicated branch-and-bound (B &B) algorithm, as confirmed by an extensive computational study. To demonstrate the genericity of the proposed concepts and in particular the B &B algorithm, the experimental evaluation is extended toward the objective of minimizing the makespan or, equivalently, the number of allocated bins.

Section 2 introduces the scheduling problem that is the subject of this paper, both from a real-world and an abstract perspective. An overview of related scientific literature is given in Sect. 3. Section 4 introduces the packing-oriented view on the problem that is the basis for the methodological and computational part of the paper. The bound tightening technique is presented in Sect. 5, while the proposal of symmetry breaking and dominance rules is the subject of Sect. 6. A custom B &B algorithm as the central solution approach is outlined in Sect. 7. Computational results and a performance assessment of the proposed B &B approach are the subject of Sect. 8. Concluding remarks and an outlook on potential future research topics are given in the final Sect. 9.

The tests themselves can be of mechanical, thermic, or purely analytical (e.g., gas chromatography) nature. The objects on which the tests are executed are called test specimen and are in fact small pieces of plastic. A product test is usually made up of several individual tests, each involving multiple such specimen. A test is thus represented by an activity or task, and each task belongs to a job or work order. The task itself is structured into sub-tasks, each of which represents a test of one single specimen.

When scheduling test activities on a resource, it is mandatory to respect custom precedence constraints between the sub-tasks. Figure 1 shows three such activities, belonging to different jobs, and each of them involves multiple test specimen. From a workflow management perspective, it is of crucial importance not to interrupt a test activity. Consider the analytical test in job 1. It consists of six individual tests, one for each specimen. While it is allowed to process more than one specimen in a time period, it is prohibitive to introduce breaks into the test flow. For example, it would not be possible to stop job 1 after time period 1 and continue its execution in time period 3, without any of its sub-tasks being scheduled in period 2. In other words, once started, at least one specimen of a test has to be processed in each time period of its execution time window.

From the company’s point of view, the primary optimization objective is to keep the resource allocation profiles as left-shifted as possible. This in turn means that ideally no resource idle time exists in earlier time periods. Figure 2 shows such a left-shifted load profile, as opposed to a balanced one. The total load is the same in both cases, but the profile on the right-hand side (Fig. 2b) is not desirable. As already mentioned, schedules are generated on a rolling-horizon basis, usually for six weeks in advance. The management wants to “freeze” the schedule and to keep the resource utilization high for the very near future, that is, the immediately upcoming time periods. If the resource load is balanced and idle time exists in those time periods, new activities might be inserted at the corresponding positions during the next planning iteration, leading to disturbances and disruptions in the laboratory. A left-shifted schedule on the other hand prevents such disruptions and maximizes the resource utilization typically for the next two or three weeks.

When adopting a more formal perspective, the above real-world scheduling problem can be specified as a multiprocessor scheduling problem with particular precedence constraints. A set of n tasks (= test activities) \(T = \{1,\ldots ,n\}\) is to be processed on a set of m identical parallel processors, representing the daily (or weekly) capacity of a workgroup resource. Every task \(i \in T\) consists of \(n_i\) sub-tasks, called slices, each of which corresponds to a test specimen. A slice is identified by a pair (i, j), with \(i \in T\) and \(j \in \{1,\ldots ,n_i\}\). The number of processors to be allocated simultaneously for the execution of a task slice is denoted by \(size_{i,j}\). All slices that make up a task \(i \in T\) have unit processing time, that is, \(p_{ij}=1\), \(j \in \{1,\ldots ,n_i\}\), and share the same size, hence, \(size_{i,1}=size_{i,2}=\ldots =size_{i,n_i}\).

A task with multiple slices is modeled as a chain-like structure by defining appropriate precedence constraints. Those constraints are imposed on every two slices that belong to one and the same high-level task and have adjacent slice indices. While minimum time lags ensure a partial order among slices, maximum time lags prevent the encompassing task from being preempted. Given a task \(i \in T\), let \(l_{i,j,j'}\) denote the start-to-start time lag (delay) between two task slices (i, j) and \((i,j')\), with \((j,j') \in \{1,\ldots ,n_i\} \times \{1,\ldots ,n_i\}\) and \(j \not = j'\). Then, \(l_{i,j,j+1} = 0\), for \(j \in \{1,\ldots ,n_i-1\}\) and \(l_{i,j,j-1} = -1\), for \(j \in \{2,\ldots ,n_i\}\).

A feasible schedule S is defined as a matrix of (integer) starting times \((s_{i,j})_{(i,j) \in T \times \{1,\ldots ,n_i\}}\) that have to satisfy the following constraints:Although maximum time lags are not present in classical chain precedence constraints known from scheduling (Blazewicz et al., 1996), the high-level tasks are referred to as chains henceforth, for ease of writing. Due to the fact that the number of scheduled slices of a chain may change from one time period to the next, the corresponding high-level task are considered malleable. Since resource allocation occurs on a discrete scale, this property is referred to as discrete malleability throughout the paper.

As far as the objective function is concerned, a left-shifted resource allocation profile, like the one shown in Fig. 2a, can be achieved by minimizing the total weighted completion time (TWCT) of the slices, where the weight \(w_{ij}\) of a slice is set equal to its size \(size_{ij}\). The completion time \(C_{i,j}\) of a slice in a feasible schedule S is equal to \(s_{i,j} + 1\). To simplify the notation, and since all slices of a chain share the same weight, weights are considered at the chain level, using \(w_i\) as the common, individual weight for all slices of a chain \(i \in T\). The value \(w_i\) is therefore also called the base weight of chain i in this specific context.

In the common three-field notation of Graham et al. (1979), the problem under consideration is of type \(P \mid chains(l); size_{ij};p_{ij}=1; w_{ij}=size_{ij} \mid \sum w_{ij} C_{ij}\). The property chains(l) means that the chain precedence constraints are subject to constant delays. The symbol l denotes the constant time lag that is imposed between two consecutive elements of the chain. As far as the problem’s complexity is concerned, it can be considered a generalization of \(P \mid size_i;p_i=1 \mid \sum C_i\), that is, the multiprocessor scheduling problem with unit time tasks and total completion time objective. The latter problem has been proven to be NP-hard in the strong sense by Drozdowski and Dell’Olmo (2000), therefore also implying strong NP-hardness for the discrete malleable task scheduling problem at hand.

The sub-tasks or slices that are the core of the considered scheduling problem are classified as rigid parallel tasks according to the taxonomy of Drozdowski (2009). They require a fixed number of processors (or resource units) that cannot be changed during processing. Contrary to that, the high-level tasks (chains) can be seen as a special kind of malleable tasks. These are parallel tasks that are permitted to change the number of processors allocated to them during execution. Discrete and continuous variants of the problem are discussed by Blazewicz et al. (2004) and Blazewicz et al. (2006) under the objective of makespan minimization. The authors focus on two versions of this problem, including continuously and discretely divisible resources, and propose an O(n) algorithm for both in case convex processing speed functions. In the completion (flow) time minimization context, Caramia and Drozdowski (2006) incorporate release times and deadlines and present two polynomially solvable cases, while the NP-hardness result of \(P \mid pmtn; r_i \mid \sum C_i\) transfers to the general problem. Flow time minimization is also the subject of Hendel et al. (2015) who analyze this objective in a semi-malleable setting and on two processors only, resulting in a polynomial time algorithm for this variant.

The work of Sadykov (2012) is devoted to the total weighted completion time variant of the problem, denoted as \(P \mid var; \delta _i \mid \sum w_i C_i\), where \(\delta _i\) represents an upper bound on the number of allocatable processors. This makes it a generalization of \(P \mid pmtn \mid \sum w_i C_i\), a problem that has been shown to be NP-hard in the strong sense. Zhang et al. (2013) directly prove that \(Pm \mid var \mid \sum w_iC_i\) is strongly NP-hard as long as m is part of the problem input. They give a two-approximation algorithm for the general case and a polynomial time algorithm for problems with a restricted number of different task sizes (work contents). Wang et al. (2018) revisit this kind of problem and devise both, a polynomial time approximation scheme for a fixed number of machines and a polynomial time algorithm for a special case with fixed m and weights proportional to the task sizes.

Task malleability is also closely related to the field of variable intensity or energy scheduling. The latter was originally defined for discrete cumulative resources, representing the counterpart of multiprocessors in classical resource-constrained (project) scheduling (e.g., Baptiste et al., 1999). In the energy scheduling problem (Artigues et al., 2013), the duration of a task is not fixed, as the amount of resource units (“energy”) allocated to it can vary during its execution, as long as it stays within predefined limits and a total required amount of energy is supplied. The problem setting has later been transferred also to the fully continuous case (Artigues & Lopez, 2015). Kis (2005) describes similar task characteristics, also in the context of continuously divisible renewable resources, referring to them as variable-intensity activities.

On the slice level, the problem covered in this paper is made up of unit time tasks of fixed size. Scheduling such tasks on parallel processors for makespan minimization (\(P \mid size_i; p_i=1 \mid C_{\text {max}}\)) dates back to the 1980s (e.g., Lloyd, 1981; Blazewicz et al., 1986). Polynomially solvable cases are limited to a constant (fixed) range of task sizes, while the problem in its general form (arbitrary task sizes) is known to be NP-hard in the strong sense for an arbitrary number processors (Lloyd, 1981). The objective of mean flow time minimization is considered, for example, by Drozdowski and Dell’Olmo (2000) who also prove the NP-hardness of problem \(P \mid size_i; p_i=1 \mid \sum C_i\).

Given those unit time task slices of predefined size, the analogy to bin packing is obvious (Garey et al., 1976; Coffman et al., 1978). The uniform character of the chains is in fact reminiscent of what is known as high-multiplicity bin packing (Gabay, 2014). As long as the number of distinct sizes is a fixed constant, such type of problem can be solved in polynomial time (Goemans & Rothvoß, 2014; Jansen, 2017).

Rigid parallel tasks on multiprocessor resources can also be linked by chain precedence constraints. Blazewicz and Liu (1996) show that scheduling arbitrary chains of rigid unit-time tasks on three processors, that is, \(P3 \mid size_i; p_i=1; chains \mid C_{\text {max}}\), is strongly NP-hard. Some special cases, like uniform chains involving only tasks with \(size_i \in \{1,k\}\) (\(k \le m\) arbitrary), are solvable in polynomial time.

While maximum time lags do not seem to be an issue in classical, single-resource multiprocessor scheduling itself, they received at least some attention in related fields, like resource-constrained project scheduling (see, e.g., Schutt et al., 2013). Although (sparse) research has been conducted on bin packing with precedence constraints (Dell’Amico et al., 2012; Pereira, 2016), time lags, and in particular those of maximum-type, did not play a role so far. Scholl et al. (2010) include them as distance constraints in their model formulation of a generalized assembly line balancing problem, but they drop them later when it comes to problem solving due to a lack of practical relevance.

As already indicated in Sect. 3, an analogy can be established between the scheduling problem at hand and one-dimensional bin packing. Each slice can be directly mapped to an item. Its weight \(w_{ij} = size_{ij}\) and thus simply \(w_i\) (see Sect. 2). To keep the notation consistent throughout the paper, the term slice will be continued to be used, also in the packing context. Each bin k corresponds to a time period of the original scheduling problem, imposing an absolute order among the bins. In other words, it actually matters to which of the available bins a slice is allocated. The number of available bins is denoted by \({\bar{k}}\), representing the length of the planning horizon. A schedule with starting times \(s_{ij}\) for each slice can be mapped to a bin packing (and vice versa) in the following manner: a slice with \(s_{ij}=0\) is assumed to be placed in the first bin, a slice with \(s_{ij}=1\) in the second bin, and so on. Given the order among the bins, it is easy to also transfer the chain-like precedence constraints from the scheduling problem, including the minimum and maximum delays. All delays can simply be represented by “distances” between numbered bins. Although all the developed concepts would basically support varying bin capacities, one and the same capacity \({\mathcal {C}}\), equal to the number of processors m, is used for all bins.

This section first introduces some fundamental concepts and symbol notation that is used throughout the paper. Then a packing-based mixed integer programming (MIP) formulation is presented, modeling the precedence constraints in a non-standard fashion. The given model also constitutes the comparison baseline for the computational experiments in Sect. 8.

To allow for an easier look-up, the symbols that are used in the remainder of the paper are summarized in Tables 1 (constants) and 2 (sets & functions).

Various custom lower bounds for a bin packing problem with linear usage cost have recently been proposed in Braune (2019). The linkage to this kind of problem is pointed out in Sect. 4. The main difference, on the other hand, is the absence of precedence constraints in the referenced problem.

In this section, an approach is proposed to exploit those constraints with regard to tightening the existing lower bounds. The resulting lower bounds are “local” in the sense that they have to be recomputed each time a partial packing (or schedule) has been fixed. In fact, some slices have to be already packed for precedence constraints to take effect. The maximum time lags then lead to a situation where a certain part of the packing in yet unpacked bins is already predetermined. Suppose that a particular partial packing has been fixed and that the bins are re-indexed such that the last packed bin and the first unpacked bin receive the indices 0 and 1, respectively. Assume further that at this state of packing, a maximum number of additional \({\bar{k}}\) bins can still be packed in a way such that no trivial improvements can be made without violating the precedence constraints.

The compulsory part of a feasible set \(F_k\) (see Definition 1 in Sect. 4.1) is given by \({\underline{F}}_k = \{(i, 1) \mid i \in T \wedge F_{k}(i) \ge 1 \wedge F_{k-1}(i) \ge 1\}\) and hence consists of exactly one slice for each chain which is also packed into the previous bin and is not yet finished, meaning that it has slices left to be packed. The notion of a compulsory part directly follows from the precedence constraints with maximum time lags. It means that the underlying feasible set could be altered by shifting slices to earlier or later bins, but its compulsory part must remain untouched in order not to violate the non-preemption constraints.

Since a packing \(F \in {\mathbb {F}}^{{\bar{k}}}\) can be considered as a vector of feasible sets, one for each bin \(1 \le k \le {\bar{k}}\), the compulsory part \({\underline{F}}\) of a packing can be defined in an analogous way.

If the intersection of all compulsory parts of all potential feasible packings, denoted by \({\underline{F}}^*\), was known, a notable portion of the unpacked bins could already receive some fixed load up front, regardless of which packing is implemented afterward. Figure 3 illustrates the idea, based on a concrete example. The area below the bold, dotted line represents the common compulsory part \({\underline{F}}^*\), pretending that it is known. The shaded in dark grey represents an approximation of \({\underline{F}}^*\), as it will be proposed below. Finally, the feasible set composition around that part is just one particular option to complete the packing.

In terms of the already mentioned lower bounds, such a fixed, rigid block might ideally lead to less fractional load and thus to tighter bounds in general. Unfortunately, the determination of \({\underline{F}}^*\) would require the enumeration of all feasible sets and is thus computationally prohibitive. Therefore, the remainder of this section is dedicated to an approximation of \({\underline{F}}^*\).

The main challenges of developing such an approximation, referred to as \(\underline{{\tilde{F}}}\) henceforth, are (9) to ensure that the lower bound property is not violated and (10) to keep the fixed area as large as possible to ensure a proper tightening effect. The key to the computation of \(\underline{{\tilde{F}}}\) is to focus on chains that are in progress at the transition between packed and unpacked bins. A chain is considered in progress if it has at least one unpacked slice remaining. In fact, the remaining number of slices of in-progress chains determines the shape of the rigid load that extends into the unpacked bins. The proposed approximation is therefore based on determining the minimum possible number of remaining slices for each unpacked bin \(1 \le k \le {\bar{k}}\).

From a more general point of view, let \({\tilde{T}}_k\) denote the set of in-progress chains before packing bin k. Assuming that this property holds for q chains after packing the most recent bin, \({\tilde{T}}_1=\{i_1,i_2,\ldots ,i_q\}\) is predetermined and thus constant, as illustrated in Fig. 3. Accordingly, the first fragment of the approximation, \(\underline{{\tilde{F}}}_1 = \{(i, 1) \mid i \in {\tilde{T}}_1\}\), can also be fixed. All subsequent sets \({\tilde{T}}_k\), with \(k \ge 2\), again depend on the actual packing and again cannot be determined without excessive computational effort. However, it is possible to approximate the sets \({\tilde{T}}_k\): let \({\underline{r}}(i,k)\) denote a function yielding a lower bound on the number of remaining slices for chain i before packing bin k. Based on the (known) number of remaining slices \(n_i'\) at the boundary between the packed and the unpacked areas, a recursive definition of function \({\underline{r}}\) can be given as follows:The idea of the approach is to use up all the residual space of a bin for slices of a particular chain \(i \in {\tilde{T}}_1\). This is done for each chain separately and independently from the other chains. Hence, the residual space is essentially used q times, which constitutes a relaxation of the capacity constraints. An approximation set \(\underline{{\tilde{F}}}_k\) can then be defined as

Lemma 1 allows to finally prove the lower bound property of the proposed approximation \(\underline{{\tilde{F}}}\).

The proposed branch-and-bound (B &B) algorithm constructs a schedule in a chronological fashion, starting at time period 0 (bin 1). Its core concept is to enumerate feasible sets for each time period or bin. From a packing-oriented point of view, it can therefore be classified as a “bin-completion” algorithm (Fukunaga & Korf, 2007).

Note that a slice-saturated feasible set can still be extensible (see Definition 2), because there may be enough space for a slice of a chain that is not yet included. On the other hand, an extensible feasible set does not necessarily have to be slice-saturated. Let \({\mathscr {F}}_k^s\), \({\mathscr {F}}_k^e\) and \({\mathscr {F}}_k^m\) denote the set of slice-saturated, extensible and maximal feasible sets packable in bin k, respectively. Then the following set relations hold: \({\mathscr {F}}_k^m \subset {\mathscr {F}}_k^s\) and \({\mathscr {F}}_k^m \cap {\mathscr {F}}_k^e = \emptyset \).

As already indicated in Sect. 6.3, in order to find an optimal solution to the problem at hand, it is not sufficient to restrict the search to maximal feasible sets. Rather, the search has to be extended to sets that are extensible and slice-saturated. An optimization algorithm therefore has to consider the set union \({\mathscr {F}}_k^o = {\mathscr {F}}_k^m \cup ({\mathscr {F}}_k^s \cap {\mathscr {F}}_k^e)\), as depicted in Fig. 9 by the areas shaded in light gray. Note that a feasible set that is not extensible but slice-saturated has to be a maximal one.

Every node in the B &B tree corresponds to a partial packing up to a particular bin \({\hat{k}}\) (starting from bin 1). Branching is conducted by determining the set of potential feasible sets for bin \({\hat{k}}+1\), that is, \({\mathscr {F}}_{{\hat{k}}+1}^o\). Hence, each branch is an extension of the current partial packing by exactly one additional (packed) bin. To avoid the exploration of non-promising regions of the search space, a variety of techniques is used to filter the potential feasible sets. The most important concepts have already been presented in Sects. 5 and 6 and will therefore be discussed with regard to their embedding into the B &B algorithm only. It must be emphasized at this point that conventional techniques for filtering feasible sets in bin packing, like the ones proposed by Martello and Toth (1990) and Scholl et al. (1997), cannot be applied to the problem at hand. The interchange arguments used in the corresponding proofs are not generally valid under the presence of precedence constraints.

Algorithm 1 gives an outline of the flow structure of the proposed B &B algorithm. To keep it short, it is an informal, high-level description, leaving out implementation details. Rather, its main goal is to illustrate the sequence in which the major steps of the algorithm (bounding, filtering and consistency checking) are executed. The three filtering procedures called at the beginning (lines 2, 3, and 4), are not further outlined. The corresponding techniques have been introduced in Sects. 6.2 and 6.3. Note that the incumbent solution and its associated objective value \(U\!B\) are treated as global variables here (lines 14 and 20). It is assumed that they are initialized before the algorithm is run, by using a constructive heuristic, for example.

A series of computational experiments were conducted to empirically assess the performance of the proposed Branch-and-Bound algorithm for the discrete malleable task scheduling problem in comparison to “off-the-shelf” commercial MIP and CP solvers. The following subsections first describe the experimental conditions under which the study took place and then discuss the obtained results in detail. Besides the main optimization objective, that is, the minimization of the total weighted completion time (TWCT), an alternative objective, namely the minimization of the makespan (and thus the number of occupied bins) is addressed as well. This should point out the versatility of the proposed base concepts.

An exact solution method has been presented for solving a multiprocessor scheduling problem in which the tasks are subject to a restricted form of discrete malleability and the objective is to minimize the total weighted completion time. Delayed precedence constraints of min/max type are used to concatenate unit-time task slices which suggest adopting a bin packing-oriented point of view. In fact, a packing-based branch-and-bound algorithm is proposed that makes use of several non-trivial, problem-specific enhancements. These include on the one hand a tightening approach for lower bounds that takes advantage of the special kind of precedence constraints. On the other hand, symmetry breaking and dominance rules have been devised to help reduce the size of the search tree. Since also non-maximal feasible sets of task slices have to be taken into consideration for computing optimal solutions to the problem at hand, these enhancements to the B &B method turn out to be of crucial importance, as confirmed by computational experience. As a side track to the main solution approach, a pre-optimization phase has been proposed, based on a limited enumeration of subset-sum solutions. This kind of primal heuristic specifically aims at scenarios with small slices and thus a high probability of completely (and exactly) using up the capacity in each time period.

Due to a lack of benchmark sets in related multiprocessor literature, the computational evaluation is based on dedicated randomized instances, adapted benchmark problems from classical bin packing and data taken from a real-world setting. A custom MIP and a scheduling-oriented CP formulation serve as the comparison baseline. It must be pointed out again that the problem structure prohibits a simple adaptation or a direct transfer of existing sophisticated solution approaches (like column generation) from both fields, scheduling and packing.

In all the scenarios, the new B &B algorithm proves very effective in obtaining optimal solutions within the predefined time limit. The required computation times are more than an order of magnitude smaller than those needed by the MIP in the majority of cases. Whenever the average computation time of the MIP is smaller, its percentage of achieved optimal solutions is also notably lower. Surprisingly, the CP solver was not able to yield competitive results, most likely because of the structure (min-sum) of the objective function and the special type of precedence constraints. The good overall performance of the B &B method is mainly owed to the symmetry breaking and dominance rules, as well as the bound tightening approach, as an in-depth analysis reveals.

Instances with slices requiring between zero and half the number of resource units still seem to pose a challenge to the new method. Potential reasons might be the insufficient lower bound quality for this size configuration (Braune, 2019), and the inability of the primal heuristic to take effect. The real-world data in its current form mainly consists of slices that are small compared to the processor capacity. Thanks to the primal heuristic, this kind of problem can be handled quite well, and still better than through the MIP formulation.

The sample application to makespan minimization as an alternative objective gives an indication of the generalizability of the proposed concepts. Even without an appropriate constraint propagation mechanism, the B &B algorithm can still solve more instances than the MIP and CP models, but the advantage is notably smaller.

Gaining deeper insights into the real-world setting will hence be one of the key aspects of future research activities. On the theoretical side, there is still room for improvement with regard to feasible set combinatorics. The number of such sets to be created especially in the root node is still enormous for 40 or more chains. The development of even more effective elimination techniques or dominance rules will be of central concern in this context. Yet another stream of research might focus on the generalization of the proposed techniques and the overall optimization approach toward size-independent weights and/or arbitrary minimum and maximum time lags.