Online algorithms to schedule a proportionate flexible flow shop of batching machines

In modern pharmacy, in order to treat various serious illnesses, individualized medicaments are produced to order for a specific patient. These production processes often take place in a complex production line, consisting of many different steps.

As long as each step of the process is still performed manually, for example by a laboratory worker, usually at each step only one patient can be handled at a time. However, once the process is scaled to industrial production levels, instead, for some steps, machines, like pipetting robots, are used. Indeed, at that point, in order to scale up production, usually several machines are used in parallel at each step. What is more, these types of machines can often handle multiple patients simultaneously. 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 as quickly as possible.

In a practical setting, the producer of the individualized drug knows nothing about the patient until the medicine is actually ordered. This naturally creates an online scheduling scenario, for which efficient, computable and, if possible, easy-to-understand scheduling rules are needed. Therefore, in this paper, we specifically deal with the online version of the problem, although some of our findings are interesting in terms of offline scheduling as well.

Formally, the manufacturing process studied in this paper is structured in a flexible flow shop manner (also called hybrid flow shop in the literature). A job \(J_j\), \(j=1,2, \ldots , n\), representing the production of a drug for a specific patient, has to be processed in s stages \(S_1,S_2, \ldots , S_s\) in order of their numbering. At each stage \(S_i\) there are available \(m_i\) identical, parallel machines \(M^{(1)}_i, M^{(2)}_i, \ldots , M^{(m_i)}_i\) to process the jobs. If each stage consists of only one machine, we may drop the machine index and instead identify each stage \(S_i\) with its single machine \(M_i\).

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 stage \(S_1\). We assume that jobs are indexed in earliest release date order. Furthermore, a job is only available for processing at stage \(S_i\), \(i=2,3, \ldots , s\), when it has finished processing at the previous stage \(S_{i-1}\).

Processing times are only dependent on the stage, not on the job or the specific machine where the job is processed (recall that machines at each stage are identical). This means that each stage \(S_i\), \(i=1,2, \ldots , s\), is associated with a fixed processing time \(p_i\), which is the same for every job when processed at that stage on any machine. In the literature, a (flexible) flow shop with such 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 flexible flow shop can potentially 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 on some machine \(M^{(k)}_i\) of stage \(S_i\) have to start processing on \(M^{(k)}_i\) at the same time. In particular, all jobs in one batch at stage \(S_i\) have to be available for processing at \(S_i\), before the batch can be started. The processing time of a batch on \(M^{(k)}_i\) remains \(p_i\), no matter how many jobs are included in this batch. At each stage \(S_i\), \(i=1,2, \ldots , s\), machines have a common maximum batch size (or batch capacity) \(b_i\), which is the maximum number of jobs a batch on machines of stage \(S_i\) may contain.

Given a feasible schedule \(\varsigma \), we denote by \(c_{ij}(\varsigma )\) the completion time of job \(J_j\) at stage \(S_i\). For the completion time of job \(J_j\) on the last machine we also write \(C_j(\varsigma )=c_{sj}(\varsigma )\). 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, we study the four objective functions makespan \(C_{\max } = \max \{C_j \mid j= 1,2, \ldots , n \}\), total completion time \(\sum C_j = \sum _{j=1}^n C_j\), maximum flow time \(F_{\max } = \max \{F_j \mid j = 1, 2, \ldots , n \}\) and total flow time \(\sum F_j = \sum _{j=1}^n F_j\), where \(F_j = C_j - r_j\). Note that the total flow time (or average flow time, if divided by the number of jobs) measures the average time a patient has to wait for his or her medicament, after the production is ordered. As short waiting times are essential in the treatment of life threatening illnesses, this objective is particularly relevant in practice. For more considerations about meaningful performance measures in applications, we refer to Ackermann et al. (2020).

Using the standard three-field notation for scheduling problems (Graham et al., 1979; Pinedo, 2012), our problem is denoted aswhere f is one of the four objective functions from above. We refer to the described scheduling model as proportionate flexible flow shop of batching machines and abbreviate it by PFFB. If we consider the special case where each stage consists of only one machine, we call this the usual proportionate flow shop of batching machines and abbreviate it by PFB.

In this paper we deal with the online problem to schedule a PFFB where each job is unknown until its release date. In particular, this means that the total number n of jobs remains unknown until the end of the scheduling process.

Throughout this paper, we write \(\varphi =\frac{1+\sqrt{5}}{2}\approx 1.618\) for the golden ratio.

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

To the best of our knowledge, neither the online PFFB problem, nor its special case, the online PFB problem, have been studied before. A practical study specific to the application introduced in the beginning can be found in Ackermann et al. (2020). Some of the concepts investigated in this paper in general have already been introduced in an application specific sense in that paper.

Even for the offline PFFB problem, little is known. Previous work has been focused on (usually non-proportionate) NP-hard generalizations motivated by applications in various manufacturing industries. Common techniques include mixed-integer programming models or application-specific heuristics. See, e.g., Amin-Naseri and Beheshti-Nia (2009), Luo et al. (2011), Li et al. (2015), Tan et al. (2018).

In the special case of offline PFBs, with only one machine per stage, proportionate versions have been studied explicitly. Sung et al. (2000) propose heuristic approaches to minimize the makespan and the total completion time in a PFB. However, they do not establish any complexity result. For the special case of two stages, Ahmadi et al. (1992), as well as Sung and Yoon (1997) present polynomial time algorithms. In a previous paper (Hertrich et al., 2020), we present a dynamic program that can be used to minimize several traditional objective functions (including the four objectives studied in this paper) in polynomial time for any fixed number s of stages. For the case of s being part of the input, the complexity status of offline PFBs is open. Significant hardness results have, to the best of our knowledge, not been achieved at all. See also (Hertrich et al., 2020), for an in-depth literature review for offline PFBs.

Although the PFFB problem itself has not been investigated from an online or offline perspective before, there are several helpful results for related online problems in the literature. For our purposes, the most interesting family of related problems is online scheduling of single and parallel batching machines. With job-independent processing times, these problems can be viewed as the one-stage versions of P(F)FBs. We refer to Tian et al. (2014) for a survey.

Concerning online makespan minimization for a single batching machine with identical processing times, Zhang et al. (2001) and Deng et al. (2003) show that no deterministic online algorithm can achieve a competitive ratio better than the golden ratio \(\varphi \). Fang et al. (2011) provide a deterministic online algorithm matching this bound, even in a slightly more general setting, where processing times are not assumed to be identical, but only grouped, that is, differing by a factor of at most \(\varphi \) from each other. Moreover, Zhang et al. (2003) show that \(\varphi \) is also the precise competitive ratio for makespan minimization on parallel batching machines with identical processing times, that is, a one-stage PFFB. Li and Chai (2018) extend this result to minimizing the maximum weighted completion time.

Concerning the total completion time objective, Cao et al. (2011) present a 2-competitive online algorithm for parallel batching machines with identical processing times, which even works in the presence of precedence constraints. For the generalization where jobs are allowed to have unequal processing times and the total weighted completion time objective, \((4+\varepsilon )\)-competitive algorithms are known (Chen et al., 2004; Ma et al., 2014).

Research on scheduling parallel batching machines to minimize maximum flow time started with the case where batches may have unbounded size (Li & Yuan, 2011). For the bounded batch model, as we consider it in this paper, Jiao et al. (2014) provide a \(\varphi \)-competitive deterministic online algorithm to minimize maximum flow time on parallel batching machines with identical processing times, i.e., a one-stage PFFB, and prove that this is best possible. Hence, the competitive ratio for makespan minimization by Zhang et al. (2003) carries over to maximum flow time. Recently, it has been shown that the competitive ratio of \(\varphi \) for maximum flow time remains also valid for maximum weighted flow time (Chai et al., 2019) or maximum flow time with delivery times (Lin et al., 2019).

Although total flow time seems to be a very reasonable objective function from a practical perspective, we are not aware of any previous research about competitive algorithms for bounded p-batching problems on single or parallel machines to minimize total flow time.

In this section we provide lower bounds on the competitiveness of deterministic online algorithms for PFFB problems with our considered objective functions \(C_{\max }\), \(\sum C_j\), \(F_{\max }\), and \(\sum F_j\).

Before we start, note that lower bounds on PFFBs with only one stage naturally extend to PFFBs with arbitrarily many stages by choosing negligible processing times for all stages but the first one. Therefore, in the following, we focus on such instances with \(s=1\).

For the makespan objective, Zhang et al. (2003) prove that the golden ratio \(\varphi \) is a lower bound on parallel batching machines with identical processing times, i.e., a one-stage PFFB. Furthermore, Jiao et al. (2014) prove the same bound of \(\varphi \) for the maximum flow time objective.

By using constructions similar to Zhang et al. (2003) and Jiao et al. (2014), we also obtain lower bounds on the competitive ratio for the total completion and flow time objectives. We first show that the golden ratio \(\varphi \) is also a lower bound for the competitiveness for the total completion time objective.

Finally, for the total flow time, we can obtain a lower bound of 2. The construction is very similar to the last proof, but instead of using \(t= \varphi -1\) as the border between the two cases, this time we use \(t=1\).

In a permutation schedule the order of the jobs is the same on all stages of the flexible flow shop. This means there exists a permutation \(\pi \) of the job indices such that \(c_{i\pi (1)}\le c_{i\pi (2)} \le \ldots \le c_{i\pi (n)}\), for all \(i=1,\ldots ,s\). Since the processing times only depend on the stage and no preemption is possible, clearly the same then also holds for starting times instead of completion times. Note that this definition is not dependent on the specific machine where a job is scheduled. If there exists an optimal schedule which is a permutation schedule with a certain ordering \(\pi \) of the jobs, we say that permutation schedules are optimal. A job ordering \(\pi \) which gives rise to an optimal permutation schedule is then called an optimal job ordering. Finally, an ordering \(\pi \) of the jobs is called an earliest release date ordering, if \(r_{\pi (1)} \le r_{\pi (2)} \le \ldots \le r_{\pi (n)}\).

Using the techniques in the proofs of Lemma 2 and Theorem 3 from (Hertrich et al., 2020), we obtain the following theorem. For the interested reader, details of the proof are available in the appendix.

From now on, we assume that jobs are indexed in earliest release date order and restrict our attention to permutation schedules where the job order is given by the indices. We therefore drop the notation of \(\pi \). It remains to decide, for each stage, how the job set should be divided into batches on the individual machines and when to process these batches. In other words, every time a machine becomes idle and at least one job is available for processing, we have to decide how long to wait for the arrival of more jobs before starting the next batch. Waiting for additional jobs incurs the cost of delaying the already available jobs.

When analyzing approximation or online algorithms, one typically compares the quality of the solution produced by the algorithm with the optimal offline solution. However, for many problems, including PFFBs, it is difficult to make a precise statement about the quality of such an optimal solution in the offline scenario. In these cases, a common approach is to use a lower bound for comparison instead. Therefore, in the first part of this section we develop a lower bound \(c^*_{ij}\) for the completion time \(c_{ij}\) of each job \(J_j\) at each stage \(S_i\). No feasible permutation schedule with job order given by the indices can yield smaller completion times.

In the second part of this section, we show how this lower bound can be interpreted as a solution of a proportionate flexible flow shop problem without batching machines.

Finally, we conclude the section by comparing our bound to another one given by Sung et al. (2000).

This section is devoted to establishing a simple, yet reasonably effective online scheduling rule for a PFFB. Again we focus on permutation schedules with job order \(J_1, J_2,\dots ,J_n\). Hence, on each stage, when a machine is idle and jobs are available, the main scheduling decision is how long to wait until starting a new batch. One obvious strategy is to always immediately start a batch when jobs are present and a machine is idle. We call this strategy the Never-Wait algorithm. Another strategy, in some ways the opposite to the Never-Wait algorithm, is to always wait until a full batch can be started. This strategy is called the Full-Batch algorithm. In this section, we show that the Never-Wait algorithm is a 2-approximation with respect to various objective functions and, hence, 2-competitive when seen as an online algorithm. Furthermore, we show that the Full-Batch algorithm admits no constant approximation guarantee at all.

In the following, let \(c_{ij}\), \(i\in [s]\), \(j\in [n]\), be the completion times resulting from the Never-Wait algorithm and \(c^*_{ij}\) be the bound defined in Sect. 5. We also write \(c_{0j}=c^*_{0j}=r_j\) for the time at which \(J_j\) becomes available at \(S_1\).

Since the Never-Wait algorithm greedily starts as many available jobs as possible, the following property holds.

Now we are ready to show that the completion times produced by the Never-Wait algorithm can be bounded from above in terms of the lower bound \(c_{ij}^*\) of the previous section.

Using this, we obtain the desired competitiveness result.

Corollary 12 and Theorem 4 imply the following corollary.

Next, we show by an example that the competitive ratio of the Never-Wait algorithm is not smaller than 2 with respect to any of the considered objectives.

We have seen that the competitive ratio of the Never-Wait algorithm is 2 with respect to all four objective functions considered in this paper. Comparing with the lower bounds of Sect. 3, this is best possible for the total flow time objective. However, for the other three objectives, there is a gap between the lower bound of the golden ratio \(\varphi \) and the upper bound of 2. In this section, we close this gap in the special case of \(s\le 2\) for makespan and total completion time by presenting a specialized \(\varphi \)-competitive algorithm for this case. This extends the result of Zhang et al. (2003), who provide a \(\varphi \)-competitive algorithm for makespan minimization with \(s=1\), i.e., on identical, parallel batching machines.

Let \(t=\varphi p_1+ (\varphi -1)p_2\). This is the latest possible time at which the first batch must be started at the second stage if we want that a job released at time zero is completed at time \(\varphi (p_1+p_2)\), which is the minimal completion time of such a job multiplied with \(\varphi \). The idea of the following algorithm is to schedule \(S_1\) in a way such that as many jobs as possible have completed \(S_1\) at time t, while the machines of \(S_2\) stay idle until time t and are scheduled according to the Never-Wait algorithm afterwards.

Next, we prove three lemmas that help to show \(\varphi \)-competitiveness. In the following, let \(c_{1j}\) and \(c_{2j}\), \(j\in [n]\), be the completion times produced by the t-Switch algorithm and let \(c^*_{1j}\), \(c^*_{2j}\), \(j\in [n]\), be the lower bounds of Sect. 5.

Now we are ready to prove \(\varphi \)-competitiveness of the t-Switch algorithm.

Theorem 23 in combination with Theorems 2 and 3 implies the following corollary.

In this paper, we consider proportionate flexible flow shops with batching machines (PFFBs). We put a special focus on the online version of the problem, which is highly relevant for applications in the production of modern, individualized medicaments. To the best of our knowledge, the online version has not been studied before, not even in the special case of proportionate (non-flexible) flow shops with batching machines (PFBs).

We describe and analyze two algorithms: the very general Never-Wait algorithm and the more specialized t-Switch algorithm. The Never-Wait algorithm works for an arbitrary number of stages and machines. What is more, its description is relatively simple and therefore it is easy to implement in practice. We show that, despite its simplicity, the Never-Wait algorithm is 2-competitive for minimizing the makespan, total completion time, maximum flow time, and total flow time. Furthermore, we show that for the total flow time objective, no deterministic online algorithm can, in general, do better than the Never-Wait algorithm.

Note that the total flow time, which is equivalent with the average flow time by dividing by the constant number of jobs, is particularly important for our application: it measures the average time patients have to wait for their medicament after production is ordered. Obviously, a low average waiting time is necessary for patients to benefit from the medicine as quickly as possible. Interestingly, studying a particular industrial instance, Ackermann et al. (2020) have also done some initial work to confirm that the theoretical usefulness of the Never-Wait algorithm is also coherent with its practical behavior.

The t-Switch algorithm is specialized for PFFBs with only two stages and the makespan or total completion time objective. For these versions of the online problem, the t-Switch algorithm is a \(\varphi \)-competitive algorithm, with \(\varphi = \frac{1 + \sqrt{5}}{2}\), the golden ratio. By using and extending lower bounds known from the literature, we show that no deterministic online algorithm to minimize the makespan or total completion time in PFFBs with two stages can, in general, be better than the t-Switch algorithm.

Both results are based on the observation that for all objectives we consider, there exists an optimal permutation schedule with start times of jobs ordered by a non-decreasing release date ordering on all stages. We show this as an extension to the theorem proved by Hertrich et al. (2020).

Notice that for the offline version, our results imply that the Never-Wait algorithm is a 2-approximation algorithm for PFFBs to minimize the makespan, total completion time, maximum flow time or total flow time. This is interesting as so far, for PFFBs with arbitrarily many stages, no exact polynomial algorithm has been found even in the case where all stages consist of only one machine (see, e.g., Hertrich et al. (2020)).

As this is the first study of online PFFBs, it is natural that some open questions remain. Most importantly, there remains a gap between the competitiveness of the Never-Wait algorithm and the lower bound of competitiveness in the case of three or more stages for makespan and total completion time, and even in the case of two stages, for the maximum flow time. Of course, it would be desirable to close this gap, either by proving a larger lower bound of competitiveness or by finding a better algorithm than the Never-Wait algorithm. As we have shown in Example 14, the Never-Wait algorithm itself cannot be better than 2-competitive in general. One way to improve the Never-Wait algorithm could be to better forecast what happens on the later stages of the PFFB. Observe that, despite the online situation, we can forecast job arrivals on later stages once the jobs become available at the first stage. Indeed, at any time step t, the full schedule (and thus arrival forecast) at each stage can be computed for all jobs which become available before t. Thus, for the later stages in the PFFB, the Never-Wait algorithm might be improved by using this additional knowledge of future job arrivals. Note that in the practical study mentioned above, such an improvement has been successfully attempted for a specific problem instance (see Ackermann et al. (2020)).

In addition to closing these gaps, for the total completion time and total flow time objectives, it might be possible to achieve better competitive ratios for special cases where a certain minimum number of machines per stage is guaranteed. Observe that the lower bound constructions in Sect. 3 (Theorems 3 and 4) only use a single machine. It might be the case that the same lower bounds do no longer hold if each stage contains several parallel machines. Possibly, better competitive ratios dependent on \(m:=\min _{i\in [s]}m_i\) could be established. Cao et al. (2011) provide a result of this kind for parallel machines (only one stage) with unbounded batch capacity. For the makespan and maximum flow time objectives, however, the lower bounds by Zhang et al. (2003) and Jiao et al. (2014) involve arbitrarily many parallel machines. Hence, for these objectives, it is not possible to achieve better competitive ratios for high values of m.

Another open question concerns different objective functions. We have shown that in a schedule computed by the Never-Wait algorithm the finishing time of a job \(J_j\) is at most twice the least possible finishing time of \(J_j\) in any permutation schedule ordered by release dates. Unfortunately, for most traditional scheduling objectives beyond those studied in this paper, permutation schedules ordered by release dates are not, in general, optimal (see, e.g., Hertrich et al. (Hertrich et al. (2020), Example 4)). Still, the Never-Wait strategy may help with these objective functions, if jobs are prioritized differently. For example, instead of scheduling jobs in order of their release dates, each time a machine is started in the Never-Wait algorithm, one may instead pick the available jobs with the largest weight, if the objective involves job weights. It is, at the moment, unclear whether such an algorithm may be competitive and, if yes, what its competitiveness bound would be.

On the other hand, in the online scenario, it may be valid to restrict the study of other objectives to the case where jobs are ordered by their release dates on all stages. In other words, instead of searching for an optimal schedule amongst all possible schedules, we search for an optimal schedule amongst all permutation schedules with jobs ordered by release dates. Especially in the pharmacological application we consider, such a first-in-first-out approach may be mandated due to ethical and fairness considerations. For this type of restricted problem, the Never-Wait algorithm may well prove to be competitive for many objectives beyond the ones considered in this paper, as long as these objectives are regular. For example, using the same arguments as before, the Never-Wait algorithm is 2-competitive w.r.t. the weighted total completion time / flow time. Indeed, as for the non-weighted versions, the factor 2 from Theorem 11 can be moved in front of the sum objectives to immediately see 2-competitiveness.