Scheduling a proportionate flow shop of batching machines

Modern medicine can treat some serious illnesses using individualized drugs, which are produced to order for a specific patient and adapted to work only for that unique patient and nobody else. Manufacturing such a drug often involves a complex production line, consisting of many different steps.

If each step of the process is performed manually, by a laboratory worker, then each laboratory worker can only handle materials for one patient at a time. However, in the industrial application which motivates our study, some steps are instead performed by actual machines, like pipetting robots. Such high-end machines can typically handle materials for multiple patients in one go. If scheduled efficiently, this special feature can drastically increase the throughput of the production line. Clearly, in such an environment efficient operative planning is crucial in order to optimize the performance of the manufacturing process and treat as many patients as possible.

In this paper, we present – as part of a larger study of an industrial application – new theoretical results for scheduling problems arising from a manufacturing process as described above. Formally, the manufacturing process we consider is structured in a flow shop manner, where each step is handled by a single, dedicated machine. A job \(J_j\), \(j=1,2, \ldots , n\), representing the production of a drug for a specific patient, has to be processed by machines \(M_1,M_2, \ldots , M_m\) in order of their numbering. Each job \(J_j\) has a release date \(r_j \ge 0\), denoting the time at which the job \(J_j\) is available for processing at the first machine \(M_1\). Furthermore, a job is only available for processing at machine \(M_i\), \(i=2,3, \ldots , m\), when it has finished processing on the previous machine \(M_{i-1}\).

Processing times are job-independent, meaning that each machine \(M_i\), \(i=1,2, \ldots , m\), has a fixed processing time \(p_i\), which is the same for every job when processed on that machine. In the literature, a flow shop with machine- or job-independent processing times is sometimes called a proportionate flow shop, see e.g. (Panwalkar et al. 2013).

Recall that, as a special feature from our application, each machine in the flow shop can handle multiple jobs at the same time. These kind of machines are called (parallel) batching machines and a set of jobs processed at the same time on some machine is called a batch on that machine (Brucker 2007, Chapter 8). All jobs in one batch \(B^{(i)}_k\) on some machine \(M_i\) have to start processing on \(M_i\) at the same time. In particular, all jobs in \(B^{(i)}_k\) have to be available for processing on \(M_i\), before \(B^{(i)}_k\) can be started. The processing time of a batch on \(M_i\) remains \(p_i\), no matter how many jobs are included in this batch. This distinguishes parallel batching machines from serial batching machines, where the processing time of a batch is calculated as the sum of the processing times of the jobs contained in it plus an additional setup time. Each machine \(M_i\), \(i=1,2, \ldots , m\) has a maximum batch size \(b_i\), which is the maximum number of jobs a batch on machine \(M_i\) may contain.

Given a feasible schedule S, we denote by \(c_{ij}(S)\) the completion time of job \(J_j\) on machine \(M_i\). For the completion time of job \(J_j\) on the last machine we also write \(C_j(S)=c_{mj}(S)\). If there is no confusion which schedule is considered, we may omit the reference to the schedule and simply write \(c_{ij}\) and \(C_j\).

As optimization criteria, in this paper we are interested in objective functions of the formswith functions \(f_j\) non-decreasing for \(j=1,2,\ldots ,n\).

In particular, the first part of the paper will be dedicated to the minimization of the makespan \(C_{\max } = \max \left\{ C_j \mid j= 1,2, \ldots , n \right\} \) and of the total completion time \(\sum C_j = \sum _{j=1}^n C_j\), although the obtained algorithms will work for an arbitrary objective function of type (1) or (2), if certain pre-conditions are met.

In the second part of the paper, we assume that for each job \(J_j\) a weight \(w_j\) or a due date \(d_j\) is given. We focus on the following traditional scheduling objectives:whereandNote that all these objective functions are regular, that is, nondecreasing in each job completion time \(C_j\).

Using the standard three-field notation for scheduling problems (Graham et al. 1979), our problem is denoted aswhere f is a function of the form defined above. We refer to the described scheduling model as proportionate flow shop of batching machines and abbreviate it by PFB.

Next, we provide an example in order to illustrate the problem setting.

The rest of the paper is structured as follows. The remaining parts of this section provide an overview of the related literature and our results, respectively. In Sect. 2 we prove that permutation schedules with jobs in earliest release date order are optimal for PFBs with the makespan and total completion time objectives. We also show that permutation schedules are not optimal for any other traditional scheduling objective functions. In Sect. 3 we construct a dynamic program to find the optimal permutation schedule with a given, fixed job order. We show that, if the number of machines m is fixed, the dynamic program can be used to minimize the makespan or total completion time in a PFB in polynomial time. In Sect. 4 we consider PFBs where all release dates are equal. We show that, in this special case, permutation schedules are always optimal and that the dynamic program from Sect. 3 can be applied to solve most traditional scheduling objectives. Finally, in Sect. 5 we draw conclusions, reflect on our results in the context of some additional existing literature, and point out future research directions.

Our approach to scheduling a PFB relies on the well-known concept of permutation schedules. In a permutation schedule the order of the jobs is the same on all machines of the flow shop. This means there exists a permutation \(\sigma \) of the job indices such that \(c_{i\sigma (1)}\le c_{i\sigma (2)} \le \ldots \le c_{i\sigma (n)}\), for all \(i=1,\ldots ,m\). Due to job-independent processing times and since a machine can only process one batch at a time, clearly the same then also holds for starting times instead of completion times. If there exists an optimal schedule \(S^*\) which is a permutation schedule with a certain ordering \(\sigma ^*\) of the jobs, we say that permutation schedules are optimal. A job ordering \(\sigma ^*\) which gives rise to an optimal permutation schedule is then called an optimal job ordering. Often, if the job ordering is clear, we will assume that jobs are already numbered with respect to that ordering and drop the notation of \(\sigma \) or \(\sigma ^*\). Finally, an ordering \(\sigma \) of the jobs is called an earliest release date ordering, if \(r_{\sigma (1)} \le r_{\sigma (2)} \le \ldots \le r_{\sigma (n)}\).

Suppose that for some problempermutation schedules are optimal. Then the scheduling problem can be split into two parts: In this section we deal with part (i) and show that for \(f\in \{C_{\max },\sum C_j\}\) optimal job orderings exist and can be found in \(O(n \log n)\) time. Then, in Sect. 3, we show that under certain, very general preconditions part (ii) can be done in polynomial time via dynamic programming.

We begin with a technical lemma which will help us to show optimality of permutation schedules in this section and also in Sect. 4.

Note that, in particular, if all release dates are equal, then any ordering \(\sigma \) is an earliest release date ordering of the jobs. This fact will be used in Sect. 4.

Now we show that for a PFB with the makespan or total sum of completion times objective, permutation schedules are optimal and that any earliest release date ordering is an optimal ordering of the jobs. This result generalizes Sung and Yoon (1997), Proposition 1 to arbitrarily many machines. For makespan and total completion time, it also extends Sung et al. (2000), Lemma 1 to the case with release dates.

Hence, when minimizing the makespan or the total completion time in a PFB, it is valid to limit oneself to permutation schedules in an earliest release date order.

To conclude this section, we present an example where no permutation schedule is optimal for a bunch of other objective functions. This shows that Theorem 3 does not hold for these objective functions. It also implies that the statements made in Sung and Yoon (1997, Proposition 1), Sung et al. (2000, Lemma 1), and Sung and Kim (2003, Lemma 1) cannot be generalized to settings in which release dates and due dates or release dates and weights are present.

In this section we show that for a fixed number m of machines and a fixed ordering of the jobs \(\sigma \), we can construct a polynomial time dynamic program, which finds a permutation schedule that is optimal among all schedules obeying job ordering \(\sigma \). The algorithm works for an arbitrary regular sum or bottleneck objective function. Combined with Theorem 3 this shows that the makespan and the total completion time in a PFB can be minimized in polynomial time for fixed m.

The dynamic program is based on the important observation that, for a given machine \(M_i\), the set of possible job completion times on \(M_i\) is not too large. In order to formalize this statement, we introduce the notion of a schedule being \(\varGamma \)-active. For ease of notation, we use the shorthand \([k]=\{1,2,\ldots ,k\}\).

Note that on machine \(M_i\), there are only \(|\varGamma _i|\le n^{i+1}\le n^{m+1}\) possible job completion times to consider for any \(\varGamma \)-active schedule S.

Now we show that for a PFB problem with a regular objective function, any schedule can be transformed into a \(\varGamma \)-active schedule, without increasing the objective value. To do so, we prove that this is true even for a slightly stronger concept than \(\varGamma \)-active.

Clearly, given a schedule S that is not batch-active, by successively removing unnecessary idle times we can obtain a new, batch-active schedule \(S^\prime \). Furthermore, for regular objective functions, \(S^\prime \) has objective value no higher than the original schedule S. These two observations immediately yield the following lemma.

Now we show that, indeed, being batch-active is stronger than being \(\varGamma \)-active, in other words that every batch-active schedule is also \(\varGamma \)-active. This result generalizes an observation made by Baptiste (2000, Section 2.1) from a single machine to the flow shop setting.

Together, Lemmas 7 and 8 imply the following desired property.

In particular, Lemma 9 shows that, if for a PFB problem an optimal job ordering \(\sigma ^*\) is given, then there exists an optimal schedule which is a permutation schedule with jobs ordered by \(\sigma ^*\) and in addition \(\varGamma \)-active.

From this point on, we assume that the objective function is a regular sum or bottleneck function, that is, \(f(C) = \bigoplus _{j=1}^n f_j(C_j)\), where \(\bigoplus \in \{\sum ,\max \}\) and \(f_j\) is nondecreasing for all \(j\in [n]\). We also use the symbol \(\oplus \) as a binary operator. In what follows, we present a dynamic program which, given a job ordering \(\sigma \), finds a schedule that is optimal among all \(\varGamma \)-active permutation schedules obeying job ordering \(\sigma \). For simplicity, we assume that jobs are already indexed by \(\sigma \). The dynamic program schedules the jobs one after the other, until all jobs are scheduled. Due to Lemma 9, if \(\sigma \) is an optimal ordering, then the resulting schedule is optimal.

Given an instance I of a PFB and a job index \(j\in [n]\), let \(I_j\) be the modified instance which contains only the jobs \(J_1,\dots ,J_j\). We write \(\varGamma =\varGamma _1 \times \varGamma _2 \times \ldots \times \varGamma _m\) and \({\mathcal {B}}=\left[ b_1\right] \times \left[ b_2\right] \times \ldots \times \left[ b_m\right] \), where \(\times \) is the standard Cartesian product. For a vectorof m possible completion times and a vectorof m possible batch sizes, we say that a schedule S for instance \(I_j\)corresponds to t and k if, for all \(i\in [m]\), \(c_{ij}=t_i\) and job \(J_j\) is contained in a batch with exactly \(k_i\) jobs (including \(J_j\)) on \(M_i\).

Next, we define the variables g of the dynamic program. Let \({\mathcal {S}}(j,t,k)\) be the set of feasible permutation schedules S for instance \(I_j\) satisfying the following properties: Then, for \(j\in [n]\), \(t\in \varGamma \), and \(k\in {\mathcal {B}}\), we defineto be the minimum objective value of a schedule in \({\mathcal {S}}(j,t,k)\) for instance \(I_j\). If no such schedule exists, the value of g is defined to be \(+\infty \).

Using the above definitions as well as Lemma 9, the objective value of the best permutation schedule ordered by the job indices is given by \(\min _{t,k} g(n,t,k)\), \(t\in \varGamma \), \(k\in {\mathcal {B}}\). In Lemmas 10 and 11 (below) we provide formulas to recursively compute the values g(j, t, k), \(j=1,2,\ldots ,n\), \(t\in \varGamma \), \(k \in {\mathcal {B}}\). In total, we then obtain Algorithm 1 as our dynamic program.

The remainder of this section deals with proving the correctness and running time bound of Algorithm 1. As mentioned above, in Lemmas 10 and 11 we define and prove the correctness of a recursive formula to compute all values of function g. Lemma 10 deals with the starting values g(1, t, k) while Lemma 11 deals with the recurrence relation. Finally, in Theorem 12 we connect the results of this section to prove the correctness of Algorithm 1.

Now we turn to the recurrence formula to calculate g for \(j>1\) from the values of g for \(j-1\).

Using Lemmas 9, 10, and 11 we can now prove correctness of Algorithm 1 and show that its runtime is bounded polynomially (if m is fixed).

Combining Theorems 3 and 12, we obtain:

In particular, for any fixed number m of machines, the problemswith \(f\in \{C_{\max }, \sum C_j \}\) can be solved in polynomial time.

The dynamic program presented in the previous section works for a very general class of objective functions. Still, Corollary 13 only holds for makespan and total completion time because for other standard objective functions permutation schedules are not optimal, as shown in Example 4.

However, in the case where all release dates are equal, it turns out that permutation schedules are always optimal. We first show that in the case of equal release dates, any feasible schedule S can be transformed into a feasible permutation schedule \(S^\prime \) with equal objective value.

From Lemma 15, it follows that permutation schedules are optimal for PFBs with equal release dates, as stated in the following theorem. The theorem generalizes the result presented by Rachamadugu et al. (1982) for usual proportionate flow shop without batching. Also compare Sung et al. (2000, Lemma 1). In the theorem, we use the term scheduling objective function to describe any objective function only dependent on the completion times of the jobs.

Note that for all regular objective functions (including those studied in this paper), at least one optimal solution always exists. Indeed, Lemma 7 shows that for regular objective functions batch-active schedules are optimal, and there are only finitely many batch active schedules for a PFB. Thus, the restriction in the statement of the theorem is only a formality. However, Theorem 16 holds for a much wider range of scheduling objective functions than studied in this paper. Importantly, since finish times for all jobs stay exactly the same when moving from schedule \(S^*\) to schedule \(S^\prime \) in the proof of Theorem 16, the theorem holds also for non-regular objective functions (as long as they are defined in such a way that at least one optimal solution exists).

Of course, it may still be hard to find optimal permutations. However, the following theorem shows that for several traditional objective functions, an optimal permutation can be found efficiently. For the solution of due date related objectives, earliest due date orderings are of particular importance. They are defined analogously to earliest release date orderings: an ordering \(\sigma \) is an earliest due date ordering, if \(d_{\sigma (1)} \le d_{\sigma (2)} \le \ldots \le d_{\sigma (n)}\).

From Theorems 12 and 17, we obtain the following complexity results.

It is also possible to minimize the (weighted) number of late jobs in \(O(n^{m^2+2m-1})\) time. However, to achieve this result, it is necessary to adjust the algorithm from Sect. 3 slightly. Suppose that jobs are ordered in an earliest due date order and suppose further \({\mathcal {J}}\) is the set of on-time jobs in an optimal solution for PFB to minimize the (weighted) number of late jobs. Note that in this case, we can find an optimal schedule by first scheduling all jobs in \({\mathcal {J}}\), in earliest due date order, using the algorithm from Sect. 3, and then schedule all late jobs in an arbitrary, feasible way.

Usually, however, the optimal set of on-time jobs is not known in advance. Thus the dynamic program has to be adapted in such a way that it finds the optimal set of on-time jobs and a corresponding optimal schedule simultaneously. This can be done by, roughly speaking, allowing the algorithm to ignore a job: in the j-th step of the algorithm, when job \(J_j\) (in earliest due date order) is scheduled, the algorithm can not only decide to schedule the job in sequence, but can alternatively decide to skip it, making it late (and paying a penalty \(w_j\)). In all other regards, the algorithm remains exactly the same as presented in Sect. 3. The technical details to prove correctness and running time of the algorithm are, as one would expect, very similar to Sect. 3 and are moved to the appendix.

We obtain the following theorem. The additional factor n in comparison to Theorem 18 stems from the fact that we do not know the optimal permutation in advance, and therefore we cannot make use of last-only-empty batching on the first machine as easily as in the proof of Theorem 18.

In particular, combining Theorems 18 and 19, we obtain that, for any fixed number m of machines, the problemswith \(f\in \{\sum w_jC_j, L_{\max }, \sum T_j, \sum U_j, \sum w_j U_j \}\) can be solved in polynomial time.

Note that, while minimizing makespan and total completion time in a PFB with a fixed number m of machines and without release dates can be handled in the same manner, a time complexity of \(O(n^{m^2+2m-2})\) is strictly speaking no longer polynomial for those two problems. Indeed, since in problemswith \(f \in \{C_{\max }, \sum C_j \}\), jobs are completely identical, an instance can be encoded concisely by simply encoding the number n of jobs, rather than every job on its own. Such an encoding of the jobs takes only \(O(\log n)\) space, meaning that even algorithms linear in n would no longer be polynomial in the length of the instance.

In the literature, scheduling problems for which such a concise encoding in \(O(\log n)\) space is possible are usually referred to as high-multiplicity scheduling problems (Hochbaum and Shamir 1990, 1991). They are often difficult to handle and require additional algorithmic consideration, since even specifying a full schedule normally takes at least O(mn) time (one start and end time for each job on each machine). In order to resolve this issue, for these high-multiplicity scheduling problems special attention is often paid to finding optimal schedules with specific, regular structures. Such a structure may then allow for a concise \(O(\log n)\) encoding of the solution. Notice, however, that a priori the dynamic programming algorithm presented in this paper does not give rise to such a regular structure.

In the case of \(m =2\) machines and the makespan objective, Hertrich (2018) shows that the O(n) algorithm by Ahmadi et al. (1992) can be adjusted to run in polynomial time, even in the high multiplicity sense. For all other cases, the theoretical complexity of the two problemswith \(f \in \{C_{\max }, \sum C_j \}\) is left open for future research. However, note that in practical applications jobs usually have additional meaning attached (for instance patient identifiers, in our pharmacy example from the beginning) and thus such instances are usually encoded with a length of at least n.

In this paper, motivated by an application in modern pharmaceutical production, we investigated the complexity of scheduling a proportionate flow shop of batching machines (PFB). The focus was to provide the first complexity results and polynomial time algorithms for PFBs with \(m> 2\) machines.

Our main result is the construction of a new algorithm, using a dynamic programming approach, which schedules a PFB with release dates to minimize the makespan or total completion time in polynomial time for any fixed number m of machines. In addition, we showed that, if all release dates are equal, the constructed algorithm can also be used to minimize the weighted total completion time, the maximum lateness, the total tardiness, and the (weighted) number of late jobs. Hence, for a PFB without release dates and with a fixed number of m machines, these objective functions can be minimized in polynomial time. Previously these complexity results were only known for the special case of \(m=2\) machines, while for each \(m\ge 3\) the complexity status was unknown. For minimizing weighted total completion time and weighted number of late jobs, these results were even unknown in the case of \(m=2\).

An important structural result in this paper is that permutation schedules are optimal for PFBs with release dates and the makespan or total completion time objective, as well as for any PFB problem without release dates. This result was needed in order to show that the constructed algorithm can be correctly applied to the problems named above.

Concerning PFBs with release dates, recall that in the presence of release dates permutation schedules are not necessarily optimal for traditional scheduling objective functions other than makespan and total completion time (see Example 4). However, there are several special cases for which permutation schedules remain optimal, in particular if the order of release dates corresponds well to the order of due dates (in the case of due date objectives) and/or weights (in the case of weighted objectives). For example, Hertrich (2018) shows that, when minimizing the weighted total tardiness, if there exists a job order \(\sigma \) that is an earliest release date ordering, an earliest due date ordering, and a non-increasing weight ordering at the same time, then there exists an optimal schedule which is a permutation schedule with jobs ordered by \(\sigma \). This, of course, implies analogous results for weighted total completion time, total tardiness and maximum lateness (again, see Hertrich (2018)). In those special cases, clearly the algorithm presented in this paper can be used to solve the problems in polynomial time. Still, the complexity status of PFBs with release dates in the general case, where orderings do not correspond well with each other, remains open for all traditional scheduling objectives other than makespan and total completion time.

Another problem left open for future study is the complexity of minimizing the weighted total tardiness in the case where all release dates are equal. This problem is open, even for the special case of \(m = 2\). In this paper, it is shown that permutation schedules are optimal for all objective functions in the absence of release dates. Furthermore, if an optimal job order is known and the number of machines is fixed, then an optimal schedule can be found in polynomial time, using the algorithm presented in this paper.

Unfortunately, the complexity of finding an optimal job order to minimize the weighted total tardiness in a PFB remains open. Note that for scheduling a single batching machine with equal processing times and for usual proportionate flow shop without batching the weighted total tardiness can be minimized in polynomial time (Brucker and Knust (2009)). Here, proportionate flow shop can be reduced to the single machine problem with all processing times equal to the processing time of the bottleneck machine (see, e.g., Sung et al. (2000)). However, such a reduction is not possible for PFBs, since there may be several local bottleneck machines which influence the quality of a solution.

Observe also that, in the special case of \(m = 2\) machines, given an arbitrary schedule for the first machine, finding an optimal schedule for the second machine is similar to solving problem \(1\mid p_j = p, r_j \mid \sum w_j T_j\) or the analogous problem on a batching machine, which also both have open complexity status (see Baptiste (2000), Brucker and Knust (2009)). So attempting to split up the problem in such a manner does not work either. Of course, if instead of an arbitrary schedule on the first machine, some special schedule is selected, it may be possible that the special structure for the release dates on the second machine helps to solve the problem. Notice, though, that this still leaves open the question of which schedule to select on the first machine.

The last open complexity question concerns the case where the number of machines is no longer fixed, but instead part of the input. We are unfortunately not aware of any promising approaches to find reductions from NP-hard problems. However, interestingly, Hertrich (2018) proves that for all versions of PFBs, minimizing the total completion time is always at least as hard as minimizing the makespan. This reduction does not hold for scheduling problems in general.

One noteworthy special case, where positive complexity may be more readily achievable, arises from fixing the number of jobs n, leaving only the number of machines m as part of the input. Note that in this case, high-multiplicity, as described in Sect. 4, is not a concern: since n is fixed, a schedule can be put out in O(m) time and since each machine has an individual processing time, the input also has at least size O(m). For PFBs with exactly two jobs, \(n=2\), and an arbitrary number of machines, Hertrich (2018) shows that the makespan can be minimized in \(O(m^2)\) time. A machine-wise dynamic program is provided that finds all schedules, in which the completion time of one job cannot be improved without delaying the other job. In other words, the program constructs all Pareto-optimal schedules, if the completion time of each job is considered as a separate objective. If the number of jobs n is larger than 2, then the dynamic program can still be applied, but its runtime in that case is pseudo-polynomial (see Hertrich (2018)).

Finally, note that while the algorithm provided in this paper has the benefit of being very general, thus being applicable to many different problems, it incurs some practical limitations due to its relatively large running time. For example, for \(m=2\), our algorithm to minimize the makespan has a runtime of \({\mathcal {O}}(n^{6})\) (Corollary 14). In contrast, the algorithm specialized to the case of \(m=2\) by Sung and Yoon (1997) runs in \({\mathcal {O}}(n^2)\). The reason for the larger runtime of our dynamic program is that, due to its generality, it needs to consider all possible job completion times in the set \(\varGamma \), while the algorithm by Sung and Yoon (1997) makes use of the fact that this is not necessary in the special case \(m=2\).

Now that many of the previously open complexity questions are solved, for future research it would be interesting to find more practically efficient algorithms, in particular for small numbers of machines like \(m = 3\) or \(m = 4\), and/or for specific objective functions. This might be possible by using some easy structural properties, which were not of use for speeding up the algorithm in the general case but which may well help with dedicated algorithms for small numbers of machines. For example, if the objective function is regular, then on any machine, when a batch is started, it is always optimal to include as many jobs as possible (either all waiting jobs, or as many as the maximum batch size). For the general algorithm provided in this paper, this property was not of use, as our algorithm adds the jobs one by one to the schedule and it only becomes clear how many jobs wait at a machine during the backtracking phase. For a dedicated algorithm, on the other hand, it may well be possible use this property to reduce the number of possible schedules that have to be considered.

If fast, dedicated algorithms cannot be obtained, then instead approximations or heuristics need to be considered in order to solve PFBs in practice. In the literature, approximations and heuristics often use restrictions to permutation schedules in order to simplify difficult scheduling problems. To this end, the results on the optimality of permutation schedules presented in this paper can be of great use to future work. In particular, the results from Sect. 2 can be of help when designing fast heuristics for makespan, total completion time and related objective functions. For the same reason, it would be interesting to quantify the quality of permutation schedules (e.g. in terms of an approximation factor) for PFB problems where permutation schedules are not optimal.

Another approach to improving the algorithms’ efficiency, especially if negative complexity results for the case with an arbitrary number of machines are achieved, would be to consider PFBs from a parameterized complexity point of view. Recently, parameterized complexity has started to receive more attention in the scheduling community (cf. Mnich and Wiese (2015), Weiß et al. (2016), Mnich and van Bevern (2018), Diessel and Ackermann (2019)). A problem with input size n is said to be fixed-parameter tractable with respect to a parameter k if it can be solved in a running time of \({\mathcal {O}}(f(k)p(n))\) where f is an arbitrary computable function and p a polynomial not depending on k. Although our algorithm is polynomial for any fixed number m of machines, it is not fixed-parameter tractable in m because m appears in the exponent of the running time. Clearly, a fixed-parameter tractable algorithm would be preferable, both in theory and, most likely, in practice, if one could be found.