Shop scheduling problems with pliable jobs

In all models discussed above, processing times \(p_{ij}\) are given for the operations \(O_{ij}\) and these processing amounts have to be completed in full even if splitting happens and/or operation parts are moved to different machines. In this paper, we study a different way of splitting jobs, where operation lengths are not given in advance, but have to be determined. To distinguish our model from those studied previously, we introduce the notion of pliability (note that the term “splitting” is already reserved for other models, see, e.g., Serafini (1996), where a job can be split and then processed independently on different machines). Formally, a pliable job j is given by its total processing amount \(p_{j}\), which has to be split among the m machines. Operation lengths \(x_{ij}\in {\mathbb {R}}_{\ge 0}\) have to be determined as part of the decision making process. The combined length of all operations of job j over all machines has to match the given total processing requirement of job j:We initiate this line of research by introducing three models with varying restrictiveness on the pliability of jobs.Model (i) assumes full flexibility of the machines and admits a low level of job granularity, accepting arbitrarily small operations. Although infinitesimally small operations are allowed, they are treated as zero-length operations rather than missing operations (for these concepts cf. Hefetz and Adiri 1982). They need to be allocated to the corresponding machine in a non-conflict way, and in the flow shop case the required machine order has to be respected.

Model (ii) is characterized by a limited level of job granularity defined by a common parameter \(\underline{p}\) for all jobs, while the limitations in model (iii) can be different for distinct job-machine pairs. Clearly, model (i) is a special case of model (ii) with \(\underline{p}=0\), and model (ii) is a special case of model (iii) with \(\underline{p}_{ij}=\underline{p}\), \(\overline{p}_{ij}=p_{j}\). The classical flow shop and open shop problems are special cases of model (iii) with \(\underline{p}_{ij}=\overline{p}_{ij}=p_{ij}\) for all \(1\le i\le m\), \(1\le j\le n\).

Extending the \(\alpha |\beta |\gamma \)-notation, we denote flow shop and open shop problems with unrestricted pliability of type (i) by \(F|plbl|\gamma \) and \(O|plbl|\gamma \). In the presence of additional restrictions of models (ii)–(iii), the given bounds are indicated in the second field as \(plbl(\underline{p})\) and \(plbl(\underline{p}_{ij},\overline{p}_{ij})\), respectively.

The third field \(\gamma \) denotes the optimization criterion. It may include one of the traditional scheduling functions or simply “f” for an arbitrary non-decreasing objective function depending on completion times \(C_{j}\) of the jobs \(j\in {\mathcal {J}}\). We distinguish between minmax and minsum objectives:where \(f_{j}(C_{j})\) are non-decreasing functions. The two typical minmax examples are the makespan \(C_{\max }=\max \{C_{j}|j\in {\mathcal {J}}\}\) and the maximum lateness \(L_{\max }=\max \{C_{j}-d_{j}|j\in \mathcal {J}\}\), where \(d_{j}\) is the due date of job j. Minsum examples include the total completion time objective \(\sum C_{j}\), total tardiness \(\sum T_{j}\), where \(T_{j} =\max \left\{ C_{j}-d_{j},0\right\} \), or the total number of late jobs \(\sum U_{j}\), where \(U_{j}\in \left\{ 0,1\right\} \), depending on whether a job is completed on time or after its due date \(d_{j}\). If jobs \(j\in \mathcal {J}\) have different weights \(w_{j}\), then the latter functions can be extended to their weighted counterparts \(\sum w_{j}C_{j}\), \(\sum w_{j}T_{j}\), \(\sum w_{j}U_{j}\).

Our main results include a study of general properties of pliability models, formulating a general methodology for handling them and using it to perform a thorough complexity classification of the models. Note that all results are derived under the assumption that the jobs are available simultaneously, at zero release times.

The obtained results for flow shop and open shop problems with pliable jobs are summarized in Tables 1, 2 for the case where the number of jobs is not smaller than the number of machines, \(n\ge m\), and in Table 3 for the case where there are fewer jobs than machines, \(n<m\). For comparison, we also provide related results for traditional (non-pliability) models; for references see, e.g., Brucker (2007), Pinedo (2016).

Note that the input for problems with pliability of type (i) and (ii) consists of O(n) entries, while the output consists of O(nm) entries if it is needed to produce a full characterization of a schedule, specifying starting/completion times of all operations. Whenever an optimal schedule has a special structure and it is possible to derive formulae for computing starting/completion times of individual operations, we list reduced time complexities in Tables 1, 2, 3, associated with finding characteristics of a single operation and for required auxiliary preprocessing. An additional term O(nm) has to be added if an optimal solution should be specified in full (see the entries in the table marked by an asterisk).

The remainder of the paper is organized as follows. In Sect. 2  we provide an overview of related models studied in the literature. General properties of flow shop and open shop models with pliability are discussed in Sect. 3. Our main focus is on the case where the number of jobs is not smaller than the number of machines, \(n\ge m\): pliability models with minmax objectives are discussed in Sects. 4, 5, and 6; results for models with minsum objectives are presented in Sect. 7. The situation \(n<m\) is discussed in Sect. 8. Concluding remarks are summarized in Sect. 9.

In order to address type (i) problems O|plbl|f and F|plbl|f, it is often useful to relax the requirement of dedicated machines typical for open shops and flow shops and to consider identical parallel machines instead. The pliability condition, that allows to determine the actual processing times of the operations, can then be interpreted as processing with preemption. The resulting problem is denoted by P|pmtn|f, where P denotes “identical parallel machines” and pmtn denotes preemption. In this problem, jobs may be split into multiple parts and these job parts can be processed on different machines.

Clearly, if in a feasible schedule for problem P|pmtn|f every machine processes exactly n job parts, one for each job, then that schedule also represents a feasible open shop schedule. Alternatively, if every machine processes each job at most once, then the schedule can be converted into a feasible open shop schedule by introducing zero-length operations for missing operations at the beginning of a schedule. We will call a schedule for problem P|pmtn|f with exactly nm job parts, some of which may be of zero length, an “open shop type” schedule, or an O-type schedule for short.

In a “flow shop type” schedule, or an F-type schedule for short, each machine processes exactly one part of each job, as in an O-type schedule; additionally jobs visit the machines in a flow shop manner, moving from machine \(M_{i}\) to \(M_{i+1}\), \(1\le i\le m-1\). As for an O-type schedule, some of the nm operations may be of zero length. However, in F-type schedules, those zero-length operations might appear in the middle of the schedule and zero-length operations which appear on a machine \(M_{i}\) with \(2\le i\le m\) cannot usually be moved to the beginning of the schedule instead. Therefore, as opposed to the open shop case, for F-type schedules such zero-length operations may create idle times on upstream or downstream machines and have an impact on the completion time of the job they belong to.

In the case of permutation schedules, with all machines processing the jobs in the same order, the notion of an F-type schedule coincides with the notion of a “Permutation Flow Shop-like schedule”, introduced by Prot et al. (2013).

For a scheduling problem \(\alpha |\beta |\gamma \), let \(\mathcal {S}(\alpha |\beta |\gamma )\) denote the set of its feasible solutions. Since any feasible solution to F|plbl|f is also feasible for O|plbl|f, and in its turn any feasible solution to O|plbl|f is feasible for P|pmtn|f, we conclude:In what follows we revise known algorithms and NP-hardness results for problem P|pmtn|f with the focus on optimal schedules of O- and F-type. The existence of an optimal F-type schedule for problem P|pmtn|f with any non-decreasing objective function f was proved by Prot et al. (2013).

Clearly, due to the inclosed structure of solution regions (3), an optimal schedule for problem P|pmtn|f, which is of F-type, is also an optimal schedule for problems F|plbl|f and O|plbl|f with pliable jobs. It follows that for problems P|pmtn|f, O|plbl|f and F|plbl|f there exists a common optimal schedule and it is of F-type. Thus the optimal objective values for these three problems are the same, and the following corollary holds.

We use Corollary 1 in order to transfer complexity results from scheduling problems with parallel machines to shop scheduling with pliability.

Consider first the case when a particular version of problem P|pmtn|f is NP-hard. Then, the corresponding versions of F|plbl|f and O|plbl|f are also NP-hard since otherwise, due to the second part of Corollary 1, a polynomial-time algorithm for F|plbl|f or O|plbl|f would also solve problem P|pmtn|f in polynomial time. We combine this observation with the known NP-hardness results for P|pmtn|f (see Brucker 2007; Lawler et al. 1993).

Whenever a job sequence is known for an optimal F-type schedule for problem P|pmtn|f, an optimal allocation of jobs to the machines can be obtained as a solution to the following model, see Prot et al. (2013):Here, it is assumed that the jobs are numbered in the order they appear in an optimal schedule, \(x_{ij}\) is the processing time of operation \(O_{ij}\), \(t_{ij}\) is its starting time, and \(C_{j}\) is the completion time of job j. The range of functions that allow fixing the job sequence includes \(f=C_{\max }\) (the job order can be arbitrary), \(f=L_{\max }\) (earliest due date first; see Sahni 1979) and \(f=\sum C_{j}\) (shortest processing time first; see Conway et al. 1967). Thus, in the case of \(f\in \left\{ C_{\max },L_{\max },\sum C_{j}\right\} \) problems O|plbl|f and F|plbl|f are solvable via linear programming. However, special properties of these pliability problems allow us to develop faster algorithms. We present them in Sects. 4.1, 4.2 and 7.1.

In this section, we establish two important properties for the type (ii) flow shop model \(F|plbl(\underline{p})|f\) with a common lower bound \(\underline{p}\) on operation lengths. Unfortunately these properties cannot be easily generalized to the open shop version of the problem, \(O|plbl(\underline{p} )|f\). They also do not hold for the most general model of type (iii), where job splitting has to respect individual lower and upper bounds on operation lengths.

In Sect. 3.2.1, we prove that for problem \(F|plbl(\underline{p})|f\) with an arbitrary (not necessarily non-decreasing) objective function f, there exists an optimal permutation schedule. Note that in Prot et al. (2013) Theorem 1 was proved for a more restricted type (i) problem (\(\underline{p}=0\)) with a non-decreasing objective function. Their technique cannot be reused for our proof, as it involves cutting jobs into arbitrarily small pieces.

In Sect. 3.2.2, we present the common methodology for solving problem \(F|plbl(\underline{p})|f\) with \(f\in \{C_{\max },L_{\max },\sum C_{j}\}\) based on job disaggregation and decomposing the problem into two subproblems. The implementation details of that methodology are then elaborated in Sects. 5.1, 5.2 and 7.2.

The following proposition establishes basic reductions for type (iii) problems.

Here \(A\propto B\) indicates that problem A polynomially reduces to problem B, see Garey et al. (1976).

Reduction (6) follows from the fact that the pliability problem \(\alpha |plbl(\underline{p}_{ij},\overline{p}_{ij})|f\) with \(\underline{p}_{ij}=\overline{p}_{ij}\), \(1\le i\le m\), \(1\le j\le n\), coincides with the traditional flow shop problem (if \(\alpha =F\)) or open shop problem (if \(\alpha =O\)). The chain of reductions (7) reflects the fact that pliability model (i) is a special case of model (ii), which in its turn is a special case of model (iii).

Using (6), we can transfer all NP-hardness results known for F||f and O||f to the corresponding pliability problems of type (iii), concluding that problem \(O3|plbl(\underline{p}_{ij},\overline{p}_{ij} )|C_{\max }\) is NP-hard in the ordinary sense, while problems \(F3|plbl(\underline{p}_{ij},\overline{p}_{ij})|C_{\max }\), \(O|plbl(\underline{p}_{ij},\overline{p}_{ij})|C_{\max }\) and \(\alpha 2|plbl(\underline{p}_{ij},\overline{p}_{ij})|f\) with \(\alpha \in \left\{ F,O\right\} \) and \(f\in \left\{ L_{\max },\sum C_{j}\right\} \) are NP-hard in the strong sense.

Similarly, using (7), we transfer the NP-hardness results for \(f\in \{\sum w_{j}C_{j},\)\(\sum T_{j},\)\(\sum w_{j}T_{j},\)\(\sum U_{j},\)\(\sum w_{j}U_{j}\}\), discussed in Sect. 3.1 in relation to type (i) problems \(\alpha |plbl|f\) to the pliability problems of types (ii) and (iii). Note that for the problems of type (iii) these results are dominated by those obtained through reduction (6).

Consider problem \(P|pmtn|C_{\max }\). An optimal schedule can be constructed in O(n) time by the wrap-around algorithm (McNaughton 1959), achieving the optimum makespan valuewhere \(p(\mathcal {J})=\sum _{j\in \mathcal {J}}p_{j}\). In order to force McNaughton’s wrap-around algorithm to produce a solution of F- and O-type, suitable for problems \(F|plbl|C_{\max }\) and \(O|plbl|C_{\max }\), we consider the jobs in the order of their numbering and allocate them in the time window \(\left[ 0,C_{*}\right] \) first on machine \(M_{m}\), then on \(M_{m-1}\), etc., until all jobs are fully allocated. Notice that machine \(M_{m}\) is always fully occupied in the interval \(\left[ 0,C_{*}\right] \), while other machines might only be partly occupied in that interval, if \(C_{*}=p_{q}\) for a job \(q\in \mathcal {J}\) with the longest processing time. Note that after performing the wrap-around algorithm, there exist at most \(m-1\) jobs which have operations of length greater than zero on more than one machine while all other jobs are processed on a single machine for their whole processing time. The order in which the machines are considered, gives an easy way for introducing zero-length operations, as illustrated in Fig. 4. The resulting schedule satisfies the requirements of F- and O-type schedules, has the minimum makespan \(C_{*}\), and is therefore optimal for both problems, \(F|plbl|C_{\max }\) and \(O|plbl|C_{\max }\).

Consider the open shop problem \(O|plbl|L_{\max }\) and its relaxed counterpart \(P|pmtn|L_{\max }\). Our approach to find an optimal O-type schedule for the latter problem consists of two stages. First calculate an optimal value \(L_{*}\) of the objective using, for example, the closed form expression for \(L_{*}\) from Baptiste (2000). That calculation requires \({O}(n\log n)\) time due to the sorting of the jobs. In the second stage, adjust the due dates to \(\overline{d}_{j}=d_{j}+L_{*}\), treat them as deadlines, and find a feasible schedule for \(P|pmtn,C_{j}\le \overline{d}_{j}|-\). The fastest algorithm is due to Sahni (1979); its time complexity is \({O}(n\log (nm))\) or \(O(n\log n)\) under our assumption \(n\ge m\). It is a property of Sahni’s algorithm that the resulting parallel machine schedule has at most one preemption per job, and a preempted job is not restarted on the same machine. Therefore, the schedule is of O-type, if zero-length operations are added at the beginning of the schedule.

Consider now the flow shop problem \(F|plbl|L_{\max }\), using again its relaxed counterpart \(P|pmtn|L_{\max }\). The approach discussed above for constructing an O-type schedule is no longer applicable, since Sahni’s algorithm used at the second stage does not guarantee that the resulting schedule is of F-type. An alternative approach for solving the second stage problem is to apply the \({O}(n\log n+mn)\)-time algorithm by Baptiste (2000), which does find an optimal schedule of F-type, thus providing a solution to problem \(F|plbl|L_{\max }\).

Interestingly, the term mn in the complexity estimate cannot be reduced, since there are instances which require \(\Omega (nm)\) nonzero operations in an optimal schedule. One such instance is presented in Appendix 2. Recall that for problem \(F|plbl|C_{\max }\) with the makespan objective, there exists an optimal schedule with the total number of nonzero operations bounded by \(n+m-1\), see Sect. 4.1.

By Theorem 3 we limit our consideration to the class of permutation schedules and use the disaggregation technique from Sect. 3.2 to construct an optimal schedule and to justify its optimality. Given an instance I of problem \(F|plbl|C_{\max }\), introduce instances \(I^{d}\) and \(I^{e}\) as in Definition 1.

Let \(S^{d}\) be a permutation schedule for instance \(I^{d}\) with every machine working contiguously from time 0 [in accordance with (D3) from Sect. 3.2.2], and let \(S^{e}\) be a solution to \(I^{e}\) in the staircase form, which uses the same job permutation as \(S^d\) [in accordance with (D1) and (D2) from Sect. 3.2.2]. Let S be the schedule for the original instance I obtained by combining \(S^{d}\) and \(S^{e}\). By Theorem 4,Thus, if \(C_{\max }(S^{d})\) achieves its minimum value, then \(C_{\max }(S)\) is minimum as well.

Following the approach from Sect. 4.1, construct an optimal schedule \(S_{*}^{d}\) by McNaughton’s wrap-around algorithm, using an arbitrary job permutation. Note that, by construction, schedule \(S_{*}^{d}\) is of permutation type. The illustrative example presented in Fig. 2 satisfies this requirement. Without loss of generality, we assume that the jobs are sequenced in the order of their numbering, and the same job order is used in an optimal solution \(S_{*}^{e}\) to \(I^{e}\).

Consider the aggregate schedule \(S_{*}\), obtained as a merger of \(S_{*}^{d}\) and \(S_{*}^{e}\). Due to (9), \(S_{*}\) is an optimal schedule among all permutation schedules, and by Theorem 3 it is globally optimal among all schedules.

The most time-consuming step in the described approach is the merger of \(S_{*}^{d}\) and \(S_{*}^{e}\). Its time complexity is O(nm), and it defines the overall time complexity for constructing a complete optimal schedule for \(F|plbl(\underline{p})|C_{\max }\).

Following the ideas of a compact encoding of an optimal solution, known in the context of high-multiplicity scheduling problems (see, e.g., Brauner et al. 2005), we specify formulae for starting times of all operations, each of which can be computed in \(O(1)\ \)time, provided a special O(n) preprocessing is done.

At the preprocessing stage, the diminished instance \(I^{d}\) is analyzed and the calculations related to McNaughton’s wrap-around algorithm are performed. The optimal schedule \(S_{*}^{d}\) can be specified by \(m-1\) split jobs, which define three types of operations in \(S_{*}^{d}\): zero-length initial operations \(\mathcal {I}\), zero-length final operations \(\mathcal {F}\), and the remaining nonzero middle operations \(\mathcal {M}\) characterized by starting times \(t_{ij}(S_{*}^{d})\) and processing times \(p_{ij}(S_{*}^{d})\) for operations \(O_{ij}\).

After the merger of the two schedules \(S_{*}^{d}\) and \(S_{*}^{e}\), the aggregate initial and final operations \(\mathcal {I}\cup \mathcal {F}\) become of length \(\underline{p}\), while the lengths of the middle operations \(\mathcal {M}\) increase by \(\underline{p}\); see Fig. 2 where the middle operations \(\mathcal {M}\) are represented as shaded boxes. For the resulting schedule, the processing times and the starting times are calculated aswhere \(C_{*}(M_{i})\) is the completion time of the last operation on machine \(M_{i}\) in schedule \(S_{*}^{d}\), \(1\le i\le m\).

Notice that the makespan formula (12) follows from (9):where \(C_{*}^{d}\) is the optimal makespan of the diminished instance calculated as Here \(p_{j}^{d}=p_{j}-m\underline{p}\) is the processing time of job j in the diminished instance \(I^{d}\) and \(p^{d}(\mathcal {J})\) is the total processing time of all jobs in the diminished instance.

Now, we consider problem \(F|plbl(\underline{p})|L_{\max }\). By Theorem 3, it is sufficient to consider permutation schedules. The following lemma justifies that we can fix the job sequence in accordance with the earliest due date order (EDD).

The lemma can be proved using pairwise interchange arguments by swapping adjacent jobs violating the EDD order and verifying that the \(L_{\max }\)-value does not increase. Note that the swapping of adjacent jobs is always feasible, as established in Lemma 1.

Given an instance I of \(F|plbl(\underline{p})|L_{\max }\), renumber the jobs so that \(d_{1}\le d_{2}\le \cdots \le d_{n}\), and apply the job disaggregation methodology of Sect. 3.2.2. Define the two instances:Notice that the original instance I satisfiesIn the class of permutation schedules with the fixed job sequence \(\left( 1,2,\ldots ,n\right) \), let \(S^{e}\), \(S^{d}\) and S be the schedules for instances \(I^{e}\), \(I^{d}\) and I, respectively. Note that \(S^{e}\) is the same as the top left schedule in Fig. 2 with \(L_{\max }(S^{e})=0\). By Theorem 4,so that \(L_{\max }(S)=L_{\max }(S^{d})\).

An optimal F-type schedule \(S^{d}\) with the EDD job sequence \(\left( 1,2,\ldots ,n\right) \) can be constructed by the algorithm from Baptiste (2000); see Sect. 4.2. Combining \(S^{d}\) (with the smallest possible value of \(L_{\max }\)) and \(S^{e}\) (with the same job sequence) delivers an optimal schedule S for the original instance I. The most time-consuming step is the algorithm from Baptiste (2000), which takes \({O}(n\log n+mn)\) time, dominating the time needed to renumber the jobs in the EDD order and the time for combining the two schedules.

Note that as opposed to Sect. 5.1, we cannot eliminate the term mn from the complexity estimate by introducing compact encoding. Indeed, even the easier problem \(F|plbl|L_{\max }\) with unrestricted pliability, which needs to be solved as a subproblem, already requires \(O(n\log n + mn)\) time; see Sect. 4.2.

The open shop problem \(O|plbl(\underline{p})|C_{\max }\) appears to be much harder to handle than the corresponding flow shop version. While for the model studied in the previous section, F-type permutation schedules have a well-defined structure, the O-type schedules for the current model provide a greater level of flexibility. Another difficulty comes from the optimality check: in contrast to problem \(O|plbl|C_{\max }\), there exist instances for \(O|plbl(\underline{p})|C_{\max }\) where the lower bound \(C_{*}\), defined by (8) for the related parallel machine problem, cannot be reached. For example, consider instances \(I_{1}\) and \(I_{2}\) as follows.

The average machine workload \(\frac{1}{3}p(\mathcal {J})\) and the processing time of the longest job \(p_{1}\) have the same value of 21, resulting in the lower bound value \(C_{*}=21\). For instance \(I_{1}\) that lower bound can be achieved, while for instance \(I_{2}\) the lower bound is unachievable: it is impossible to process job 1 without some waiting time in-between its operations, while observing the restriction \(\underline{p}=2\) and ensuring that no machine is idle before it finishes processing all jobs. This is due to the fact that all operations of all other jobs are of even length 2, but job 1 has odd processing time and cannot be split into three even length operations; see Fig. 5 for an illustration.

In the following, we consider the cases from Table 4 where problem \(O|plbl(\underline{p})|C_{\max }\) can be solved efficiently. We use the notations \(p_{1}\), \(p_{2}\) and \(p_{3}\) for the processing times of the three longest jobs, assuming \(p_{1}\ge p_{2}\ge p_{3}\).

In Case 1 we adjust the approach from Sect. 5.1 developed for problem \(F|plbl(\underline{p} )|C_{\max }\). Using the concept of the diminished instance with \(p_{j} ^{d}=p_{j}-m\underline{p}\), the inequality that defines Case 1 can be rewritten asor equivalentlyIt implies that there exists an optimal flow shop schedule for problem \(F|plbl(\underline{p})|C_{\max }\) withsee Theorem 8. An optimal open shop schedule can be obtained from the optimal flow shop schedule by moving to the front the last \(k-1\) operations of length \(\underline{p}\) on every machine \(M_{k}\), \(2\le k\le m\). These moves do not cause any conflicts since \(n\ge m\), and the flow shop makespan value \(C_{*}^{\mathrm {FlowShop}}\) decreases by \((m-1)\underline{p}\):By the same theorem, an optimal schedule can be fully defined in O(nm) time.

Case 2 follows immediately from the more general result for problem \(O2|plbl(\underline{p}_{ij},\overline{p}_{ij})|C_{\max }\), which we present in Sect. 6.2.

Optimal schedules for Cases 1-2 have a common permutation-like structure, with job sequences on machines \(M_{1},M_{2},\ldots ,M_{m}\) selected from the set of sequencesConditions that define Cases 3–5 also result in optimal schedules with permutation-like structure. They were derived by Koulamas and Kyparisis (2015) for the open shop problem with \(m=3\) machines and with each job consisting of equal-size operations. Due to our assumption \(p_{j}\ge m\underline{p}\) (necessary for feasibility), splitting each job into m equal-size operations of length \(\frac{p_{j}}{m}\) leads to a feasible schedule for the model with pliable jobs. Moreover, the makespan of each optimal schedule for Cases 3-5 achieves the lower bound \(C_{*}\). Therefore, the resulting schedules are optimal for \(O|plbl(\underline{p})|C_{\max }\).

The longest processing time order, assumed in Koulamas and Kyparisis (2015) for the whole set of jobs \(\mathcal {J}\), is not needed once the three longest jobs \(\left\{ 1,2,3\right\} \) are identified, so that the optimal schedules in Cases 3-5 can be found in O(n) time.

It is likely that the permutation-like property holds for the general case of problem \(O|plbl(\underline{p})|C_{\max }\). An optimal job splitting may violate the equal-size property, with possibly unequal splitting of a job into m operations, as illustrated by the top schedule of Fig. 5. However, a proportionate open shop schedule, where jobs are split into equal-size operations, can be a good starting point for identifying the boundary jobs, processed at the beginning and at the end on each machine. The optimal operation lengths can then be found via linear programming. Unfortunately, we were unable to prove the correctness of the outlined approach and leave it for future research.

We demonstrate that problem \(F2|plbl(\underline{p}_{ij},\overline{p} _{ij})|C_{\max }\) is NP-hard and its special case with a fixed job order can be solved via linear programming. Interestingly, the counterpart of the problem with flexible operations is NP-hard in both cases; see Gupta et al. (2004) and Lin et al. (2016).

The problem becomes solvable via linear programming if a job sequence is fixed, even in the case of more than two machines and for more general objective functions. For this, we need to extend the LP formulation (4) by Prot et al. (2013), adding box inequalities \(\underline{p} _{ij}\le x_{ij}\le \overline{p}_{ij}\) for all variables \(x_{ij}\).

Solving problem \(O2|{plbl(\underline{p}_{ij},\overline{p}_{ij})}|C_{\max } \) involves two decisions: finding the job splitting \(p_{j}=a_{j}+b_{j}\) for all jobs \(j\in \mathcal {J}\), and sequencing the operations with fixed lengths on two machines to minimize the makespan. The second task can be done in O(n) time using the well-known algorithm by Gonzalez and Sahni (1976), which constructs an optimal schedule with the makespanHere, the first two terms correspond to the loads of machines A and B, while the last term is the processing time of a longest job q,In what follows we formulate three LP problems LP(A), LP(B), and LP(q), one for each term in (16), aimed at finding an optimal job splitting. Notice that some of the problems may be infeasible. An optimal solution is selected among the solutions to these three problems as the one with the smallest makespan value.

Consider first problem LP(A) formulated for the class of schedules with \(C_{\max }=\sum _{j\in \mathcal {J}}a_{j}\), assuming that the first term in (16) determines the maximum. If \(\Delta \) denotes the difference between the third and the first term in (16), then this class of schedules is characterized by \(\sum _{j\in \mathcal {J}}a_{j}=p_{q}+\Delta \ge \sum _{j\in \mathcal {J}}b_{j}\), where \(\Delta \ge 0\), and minimizing the makespan is equivalent to minimizing \(\Delta \):From the first and the third constraints we derive the following expressions for \(\Delta \) and \(b_{j}\):and rewrite LP(A) as follows:whereThe resulting problem is the knapsack problem with continuous variables \(a_{j} \), \(j\in \mathcal {J}\), solvable in O(n) time (Balas and Zemel 1980).

Problem LP(B) is formulated similarly for the class of schedules with \(C_{\max }=\sum _{j\in \mathcal {J}}b_{j}\); it is also solvable in O(n) time.

Consider now problem LP(q) formulated for the class of schedules with \(C_{\max }=p_{q}\). Since the makespan value is constant, there is no objective function to minimize, and we only need to find a feasible solution with respect to the following constraints:Using expression \(b_{j}=p_{j}-a_{j}\) for \(j\in \mathcal {J}\) we obtain:where \(\ell _{j}\) and \(u_{j}\) are given by (19). The latter problem can be solved in O(n) time by performing the following steps.To summarize, each of the problems LP(A), LP(B) and LP(q) can be solved in O(n) time, and this is the overall time complexity of the described approach for solving \(O2|{plbl(\underline{p}_{ij},\overline{p}_{ij})}|C_{\max }\).

We conclude this section by reviewing the results for another related problem, namely the parallel machine problem with restricted preemption and the makespan objective studied by Ecker and Hirschberg (1993), Baranski (2011), and Pienkosz and Prus (2015). In that problem, job preemption may happen several times, but each job part has to be at least \(\underline{p}\) time units long, for some lower bound \(\underline{p}\). Notice that unlike the pliability problem \(O|plbl(\underline{p})|C_{\max }\), it is not required that every job is split exactly into m pieces, one per machine.

Polynomial-time algorithms for the parallel machine problem with restricted preemption where no job part may be shorter than \(\underline{p}\) are known only for special cases with two machines; see Table 5. The complexity of the general case with \(m=2\) is left as open in the literature. Interestingly, our algorithm presented in this section finds an optimal schedule not only for the pliability problem \(O2|{plbl(\underline{p}_{ij},\overline{p}_{ij})}|C_{\max }\), but it also solves the problem with restricted preemption for \(m=2\) machines, assuming \({\underline{p}_{ij}=\underline{p}}\) for all operations and \(p_{j}\ge 2\underline{p}\).

As observed in Sect. 3.1, problem \(F|plbl|\sum C_{j}\) can be solved in polynomial time via linear programming, considering a fixed sequence of job completion times corresponding to the shortest processing time (SPT) order; the optimality of that order for \(P|pmtn|\sum C_{j}\) is stated, e.g., in Conway et al. (1967).

A faster algorithm is based on the approach which constructs an optimal F-type schedule for problem \(P|pmtn|\sum C_{j}\), formulated by Bruno and Gonzalez (1976) and Labetoulle et al. (1984) for the more general problem \(Q|pmtn|\sum C_{j}\), where machines have different processing speeds. The algorithm can be described as follows.

Algorithm F-SumSteps 1 and 2 of the algorithm are illustrated by the two schedules of Fig. 7. Note that Step 1 constructs an optimal schedule for problems \(P||\sum C_{j}\) and \(P|pmtn|\sum C_{j}\), while Step 2 reshuffles operation parts without increasing completion times of individual jobs, producing an F-type solution for \(P|pmtn|\sum C_{j}\). By Corollary 1, the resulting schedule is optimal for \(F|plbl|\sum C_{j}\).

The combined time complexity of the two steps is \({O}(n\log n+mn)\). Following the ideas of compact encoding of an optimal solution, we can use the following function J(i, u) that specifies for each machine-interval pair \(\left( i,u\right) \ \)the job which is processed by machine \(M_{i}\) in interval \(\mathcal {I}_{u}\):where the job index 0 means that no job is assigned.

Consider now problem \(O|plbl|\sum C_{j}\). The task of constructing an O-type schedule optimal for problem \(P|pmtn|\sum C_{j}\) is a simpler task than constructing an F-type schedule. It is sufficient to adjust an SPT schedule produced by Step 1 of Algorithm F-Sum by adding zero-length operations in the beginning of the schedule, so that every job has an operation on every machine.

In order to solve problem \(F|plbl(\underline{p})|\sum C_{j}\), we use the disaggregation methodology from Sect. 3.2.2, which results in two simplified instances: one instance of problem \(F|plbl|\sum C_j\) with unrestricted pliability, which can be solved by the approach from the previous section, and one instance with equal processing times. Let the two instances be \(I^{d}\) and \(I^{e}\), as in Definition 1, and the corresponding schedules be \(S^{d}\) and \(S^{e}\). We assume that \(S^{d}\) and \(S^{e}\) satisfy conditions (D1)-(D3) required for Theorem 4. Note that if (D3) is not satisfied for \(S^{d}\), i.e., if there are idle times on some machines, then they can be eliminated, without increasing job completion times, by left-shifting operations or by moving processing load to downstream machines.

By Theorem 4, the schedule S obtained as a merger of \(S^{d}\) and \(S^{e}\) satisfies:As the objective value \(\sum _{j=1}^{n}C_{j}^{e}\) of schedule \(S^{e}\) for instance \(I^{e}\) is the same for any permutation schedule \(S^{e}\), \(\sum _{j=1}^{n}C_{j}\) achieves its minimum value if and only if \(\sum _{j=1} ^{n}C_{j}^{d}\) is minimum. Thus, an optimal schedule for problem \(F|plbl(\underline{p})|\sum C_{j}\) can be found as a merger of schedule \(S^{e}\) defined in Sect. 3.2.2 and schedule \(S^{d} \) constructed by Algorithm F-Sum for instance \(I^{d}\) as in Sect. 7.1.

The merger involves \(n+m-1\) intervals of schedule \(S^{e}\), which we denote by \(\mathcal {I}_{v}^{\prime }\), \(1\le v\le \left( m-1\right) +n\), and n intervals of schedule \(S^{d}\), defined in the previous section as \(\mathcal {I}_{u}\), \(1\le u\le n\). Notice that the last n intervals of schedule \(S^{e}\) have exactly the same job allocation as the n intervals of schedule \(S^{d}\). Thus, as a result of the merger, the combined schedule gets the first \(\left( m-1\right) \) intervals of length \(\underline{p}\) taken from \(S^{e}\), and the next n intervals taken from \(S^{e}\) and \(S^{d}\); resulting intervals are of length \(\left| \mathcal {I}_{u}\right| +\underline{p}\), \(1\le u\le n\). We modify the function J(i, u), introduced in the previous section for a compact encoding of schedule \(S^{d}\). For the current problem \(F|plbl(\underline{p})|\sum C_{j}\), function \(J^{\prime } (i,v)\) specifies for each machine-interval pair \(\left( i,v\right) \ \)the job which is processed by machine \(M_{i}\) in the v-th interval:where the job index 0 means that no job is assigned. Here the expression \(v-i+1\) corresponds to the main expression \(u+m-i\) from (21) after substituting \(u=v-\left( m-1\right) \), the link between the u-th interval of \(S^{d}\) and the v-th interval of \(S^{e}\).

We find an optimal schedule for problem \(O|plbl(\underline{p})|\sum C_{j}\) by constructing a common optimal schedule for problems \(P||\sum C_{j}\) and \(P|pmtn|\sum C_{j}\) and reorganizing its structure in order to achieve a solution of O-type.

Without loss of generality, we assume that n is a multiple of m, i.e., \(n=Qm\) for some integer Q. Otherwise, we add as many jobs of maximum length as needed to satisfy this condition (at most \(m-1\) jobs are sufficient). Then we apply the approach described below, which would place the longest jobs at the end of the schedule, and remove the added jobs from the resulting schedule.

Construct an SPT schedule by assigning a shortest job to the earliest available machine; see the top schedule in Fig. 8. In what follows, we assume that the jobs are renumbered in SPT order, and the job numbering is from 0 up to \(n-1\) (in order to improve readability of the formulae for an optimal schedule).

Consider Q sections of the schedule, each of length \(m\underline{p}\): the first section is given by the interval \(\left[ 0,m\underline{p}\right] \) and the remaining sections by intervals \(\left[ C_{qm-1},C_{qm-1}+m\underline{p} \right] \), \(1\le q\le Q-1\). In each section q, there are m jobs \(\mathcal {J}_{q}=\left\{ j=qm+r|0\le r\le m-1\right\} \) allocated to m machines, one job per machine. To justify this, notice that all jobs from \(\mathcal {J}_{0}\) start at time 0 and have processing times no less than \(m\underline{p}\). The property holds for every subsequent section q sinceand \(C_{j}\ge C_{qm}\) for any \(j\in \mathcal {J}_{q}\). Note that each job appears in exactly one of the Q sections.

In order to produce a feasible O-type schedule with m operations per job, each of length no less than \(\underline{p}\), we adopt a two-stage approach: first redistribute the jobs within every section q, \(0\le q\le Q-1\); next redistribute the jobs in-between the sections. Stage 1 ensures that every machine gets one operation of every job of length \(\underline{p}\); Stage 2 places a nonzero operation of a job from in-between two sections next to the \(\underline{p}\)-operation of the same job and combines them into one operation, see Fig. 8 for an illustration.

Formally, in Stage 1 we split every section q into m subintervals of length \(\underline{p}\) and reshuffle the jobs in each subinterval in a wrap-around manner. The reshuffling is done slightly differently, depending on whether q is even or odd:

After Stage 1, the following property holds for any pair of jobs \(j \in \mathcal {J}_{q}\) and \(j+m \in \mathcal {J}_{q+1}\), which were adjacent in the initial schedule: the last \(\underline{p}\)-operation of j in section q and the first \(\underline{p}\)-operation of \(j+m\) in the next section are assigned to the same machine (compare the last column of the top table with the first column of the bottom one). Due to this, at Stage 2 we can rearrange the job parts in-between the sections while keeping j and \(j+m\) adjacent: the last part of job j is placed on the same machine as the last \(\underline{p}\)-operation of that job in section q, and the two operations are merged; the first part of \(j+m\) is placed on the same machine as the first \(\underline{p}\)-operation of that job in the section \(q+1\), and the two operations are also merged; see the bottom schedule in Fig. 8. Thus, we create a schedule with exactly m operations per job, the \(m-2\) middle operations are of minimum length \(\underline{p}\) while the first and last operation of each job may be larger.

The operation lengths are thus defined as follows:For a compact encoding, the machine order can be represented by the function M(j, k) which defines the machine index for the k-th operation of job \(j=qm+r\) that appears in the schedule (this is not necessarily the operation on machine \(M_{k}\)):Note that here \(1\le k\le m\) and \(0\le r\le m-1\).

The described approach finds an optimal open shop schedule, since the job completion times in it are the same as in an optimal schedule for problem \(P|pmtn|\sum C_{j}\). If \(n\ne Qm\) and auxiliary jobs of maximum length have been added initially, we can assume without loss of generality that they are the last \(\Gamma \) jobs to finish processing, for some \(\Gamma <m\). Their removal from the final schedule keeps completion times of the remaining jobs equal to their competition times in an optimal schedule to \(P|pmtn|\sum C_{j}\).

In this section, we give a brief overview of other traditional minsum criteria \(f\in \left\{ \sum w_{j}C_{j},\sum U_{j},\sum w_{j}U_{j},\sum T_{j},\right. \left. \sum w_{j}T_{j}\right\} \).