Flowshop scheduling with learning effect and job rejection

Abstract

We study scheduling problems on a proportionate flowshop. Three objective functions are considered: minimum makespan, minimum total completion time, and minimum total load. We consider a learning process; thus, the processing time of a job processed later in sequence is reduced. The scheduler has the option of job rejection; i.e., only a subset of the jobs are processed and the rejected jobs are penalized. An upper bound on the total permitted rejection cost is assumed. Since the single-machine versions of these problems were shown to be NP-hard, we focus on the introduction of pseudopolynomial dynamic programming algorithms, indicating that the problems are NP-hard in the ordinary sense. We provide an extensive numerical study verifying that the proposed solution algorithms are very efficient and instances containing up to 80 jobs are solved in no more than 5 ms.

1 Introduction

In manufacturing, learning is the process by which education increases productivity and results in faster production times. This paper studies production scheduling problems with learning. The machine setting is a proportionate flowshop. Three objective functions are considered: makespan, total completion time, and total load (i.e., the total time that all the machines are active, or equivalently, the sum of the completion times of the last scheduled jobs on all the machines). In all three models, we include a very practical and realistic feature, viz. the option of job rejection. Thus, the scheduler may process only a subset of the jobs, while the others are rejected (e.g., outsourced) and penalized accordingly.

The underlying assumption of learning in the context of production is that a processor (a single worker or a team) improves its performance after repeating the same activity a number of times. “Learning effects refer to cost savings that come from learning by doing. Labor, for example, learns by repetition how to carry out a task, such as assembling airframes, most efficiently. Labor productivity increases over time as individuals learn the most efficient ways to perform particular tasks” (Hill 2016).

Scheduling with the learning effect is an important topic within the broad area of scheduling with time- or position-dependent job processing times (Gawiejnowicz 2008). The first researcher to consider learning in this context was Gawiejnowicz (1996). In his model, the speed of the processor is a function of the number of jobs already processed. The special case of an increasing speed function reflects the learning effect. Biskup (1999) was the first to define an explicit (learning) function of the job processing time as a function of its position in the sequence. A decade later, Biskup (2008) published a survey on scheduling problems with learning, containing various combinations of learning types, objective functions, and machine settings. A recent survey (Azzouz et al. 2018) summarizes the published learning models and provides a new classification scheme for these models and a cartography showing the relation between the different models of scheduling under learning effects. Each model in this class assumes a learning curve that demonstrates the decline in job processing time as a function of the number of repetitions. Following Biskup (1999) and Mosheiov (2001), we consider herein an exponential learning curve.

The option of job rejection has became a popular topic among scheduling researchers in recent years. This is reflected in the recently published survey of Shabtay et al. (2013). Shabtay et al. (2013) emphasize the practicality of job rejection, which is mostly realized “in highly loaded make-to-order production systems, where accepting all jobs may cause a delay in the completion of orders which in turn may lead to high inventory and tardiness cost. In such systems, the firm may wish to reject the processing of some jobs by either outsourcing them or rejecting them all together.” Thus, the method of job rejection provides the operations manager with an analytical tool that enables him to improve the overall performance of the production facilities. Applying job rejection methods, the operations manager can improve the operational expense, enhance the distribution of the resources, and reduce the time-to-market. Since either rejecting or outsourcing a job carries a loss of income, it is common to penalize the scheduler if he decides to take this measure, and consequently, the total rejection cost becomes a factor in the objective function. Some of the relevant recently published articles include, e.g., those of Thevenin et al. (2015), Ou et al. (2015), Shabtay et al. (2015), Ou et al. (2016), Mor and Mosheiov (2016), Epstein and Zebedat-Haider (2016), Zhong et al. (2017), Agnetis and Mosheiov (2017), Gerstl and Mosheiov (2017), Gerstl et al. (2017), Mosheiov and Strusevich (2017), Fiszman and Mosheiov (2018), Mor and Mosheiov (2018), and Mor and Shapira (2018, 2019).

Shabtay et al. (2013) claim that, in scheduling theory, there are four types of problem involving job rejection: (i) minimizing the sum of the scheduling measure and the total rejection cost, (ii) minimizing the scheduling measure subject to an upper bound on the rejection cost, (iii) minimizing the rejection cost subject to a constraint on the scheduling measure, and (iv) determining all the Pareto-optimal points. In this paper, we focus on type ii problems; i.e., we minimize makespan, total completion time, and total load, subject to an upper bound on the total permitted rejection cost.

In summary, we solve scheduling problems with the following features: (i) the machine setting is that of a proportionate flowshop, i.e., the job processing times are machine independent; (ii) we consider a learning effect, i.e., job processing times decrease as a function of the job position; and (iii) job rejection is allowed, i.e., it is possible to process only a subset of the jobs, and the rejected jobs are penalized. All three problems are NP-hard, since their single-machine versions were shown to be NP-hard even with no learning effect (by reduction from the knapsack problem); see Zhang et al. (2010). We thus focus on the introduction of pseudopolynomial dynamic programming (DP) algorithms, proving that the problems are NP-hard in the ordinary sense. We conduct extensive numerical tests to evaluate the performance of the proposed algorithms. Problems of up to 80 jobs are solved in very reasonable running times (up to 5 ms), indicating that the DPs are efficient with respect to such medium-sized instances.

The paper is organized in six sections. Following introductory remarks in Sect. 1, Sect. 2 contains the notation and formulation of the problems. Sections 3, 4, and 5 are dedicated to minimizing the makespan, minimizing the total completion time, and minimizing the total load, respectively. All three sections contain the results of numerical tests. Section 6 contains the conclusions, and ideas for future research are offered.

2 Formulation

We study an n-job m-machine permutation flowshop problem. We assume a proportionate flowshop, where the job processing times are machine independent. On the other hand, as mentioned above, we consider a learning effect; i.e., the job processing times are assumed to be position dependent. Specifically, the job processing times decrease as a function of their position in the sequence. Following Biskup (1999), we assume exponential learning, and thus, the actual processing time of job j if assigned to position r on machine i is given by $p_{ijr} = p_{jr} = p_{j} r^{a} , j,r = 1, \ldots ,n, i = 1, \ldots ,m$, where $p_{j}$ is the job basic integer processing time, and $a$ is a negative constant reflecting the learning index. Note that, in practice, there must be a lower bound on the actual job processing time, and thus, $p_{jr} = { \hbox{max} }\{ p_{j} r^{a} , p\}$ for some constant $p > 0$.

For a given job schedule, $C_{ij}$ is the completion time of operation (i, j), i.e., the completion time of job j on machine i, $i = 1, \ldots ,m; \quad j = 1, \ldots ,n$. The completion time of the entire job is the completion time of its last operation (on machine m): $C_{j} = C_{mj} , j = 1, \ldots ,n$. The makespan is the completion time of the last scheduled job on machine m: $C_{ \hbox{max} } = { \hbox{max} }\left\{ {C_{j} ;j = 1, \ldots ,n} \right\}$. A second scheduling measure considered in this paper is the total completion time, i.e., ${\text{TCT}} = \sum\nolimits_{j = 1}^{n} {C_{j} }$. We also consider the measure of total load, which is the sum of the completion times of the last jobs on all m machines. Thus, let $C_{\hbox{max} }^{\left( i \right)} = C_{in}$, then the total load is given by ${\text{TL}} = \sum\nolimits_{i = 1}^{m} {C_{\hbox{max} }^{\left( i \right)} }$.

The scheduler is given the option to process only a subset of the jobs and reject the remaining jobs. Let ${\mathcal{J}}$ denote the set of all n jobs. Let A denote the set of the processed (accepted) jobs, and R denote the complementary set (of the rejected jobs), implying that ${\mathcal{J} } = P \cup R$ and $P \cap R = \emptyset$. If the scheduler decides to reject a job, he is penalized by a job-dependent rejection cost denoted by $e_{j} ,j = 1, \ldots ,n$. We assume a given upper bound denoted by E on the total permitted rejection cost $\left( {E \ge \sum\nolimits_{j \in R} {e_{j} } } \right)$.

The first scheduling problem studied here is makespan minimization. Our goal is to minimize the makespan subject to an upper bound on the total rejection cost. Thus, using the standard three-field formulation of scheduling problems, the first problem studied here is

$$ {\mathbf{P1}}:Fm/LE,p_{ijr} = p_{jr} ,\mathop \sum \limits_{j \in R} e_{j} \le E/C_{ \hbox{max} } . $$

The second problem solved here is minimizing the total completion time, subject to an upper bound on the total permitted rejection cost:

$$ {\mathbf{P2}}:Fm/LE,p_{ijr} = p_{jr} ,\mathop \sum \limits_{j \in R} e_{j} \le E/{\text{TCT}} . $$

The third problem is minimizing the total load subject to E:

$$ {\mathbf{P3}}:Fm/LE,p_{ijr} = p_{jr} ,\mathop \sum \limits_{j \in R} e_{j} \le E/{\text{TL}} . $$

3 Minimizing makespan

Zhang et al. (2010) proved that the single-machine version with no learning effect $\left( {1/\sum\nolimits_{j \in R} {e_{j} } \le E/C_{\hbox{max} } } \right)$ is NP-hard in the ordinary sense, implying that the extension to a flowshop is at least NP-hard in the ordinary sense. In this section, we introduce an efficient pseudopolynomial dynamic programming algorithm, proving that problem P1 remains NP-hard in the ordinary sense. Mosheiov (2001) proved that the single-machine version with learning effect and no job rejection $1/LE/C_{\hbox{max} }$ is solved by sequencing the jobs in SPT (shortest processing time first) order with respect to the basic processing times. We prove in the following that SPT remains optimal (for the processed jobs) in the more general setting of P1 (assuming a flowshop and job rejection).

Proposition 1

An optimal schedule exists for problem P1 such that the processed (nonrejected) jobs are sequenced in SPT order (with respect to the basic processing times).

Proof

By a pairwise interchange argument. Consider a sequence $S_{1}$ which is not SPT. Let $i$ and $j$ be the first pair of consecutive jobs which does not follow SPT order, i.e., $p_{i} > p_{j}$. Assume that job $i$ is in position $r$ and job $j$ is in position $r + 1$. Note that in $S_{1}$ there is no idle time between jobs $i$ and $j$ because $p_{i} r^{a} > p_{j} (r + 1)^{a}$. Let $k$ be the job preceding job $i$ (i.e., processed in position $r - 1$). [Note that, since $i$ and $j$ is the first pair of consecutive jobs which violates the SPT property, it is clear that $p_{k} \le p_{i}$. Moreover, we can assume without loss of generality that $p_{k} \le p_{j}$ because otherwise, after the pairwise interchange of jobs $i$ and $j$ (see below), the resulting sequence is not SPT, and an additional interchange of $k$ and $j$ is required. Such interchanges may be repeated until all jobs prior to and including $j$ are ordered according to SPT.] Also, let $t$ denote the completion time of job $k$ on machine 1 (and the starting time of job $i$ on machine 1).

The sequence $S_{2}$ is obtained from $S_{1}$ by interchanging jobs $i$ and $j$.

Case 1: $p_{i} r^{a} \ge p_{k} \left( {r - 1} \right)^{a}$. (In $S_{1}$ job $i$ is processed along the flowshop with no delay.)

In this case, the completion time of job $j$ is

$$ C_{j} \left( {S_{1} } \right) = t + p_{i} r^{a} m + p_{j} \left( {r + 1} \right)^{a} . $$

Subcase 1.1: After the job interchange, job $i$ in position $r + 1$ remains larger than job $j$ in position $r$, i.e., $p_{i} \left( {r + 1} \right)^{a} \ge p_{j} r^{a}$ (and an idle time is created between jobs $j$ and $i$).

In this subcase, the completion time of job $i$ is

$$ C_{i} \left( {S_{2} } \right) = t + p_{j} r^{a} + p_{i} \left( {r + 1} \right)^{a} m. $$

We have to show that

$$ C_{j} \left( {S_{1} } \right) = t + p_{i} r^{a} m + p_{j} \left( {r + 1} \right)^{a} \ge t + p_{j} r^{a} + p_{i} \left( {r + 1} \right)^{a} m = C_{i} \left( {S_{2} } \right). $$

It is sufficient to show that

$$ t + p_{i} r^{a} + p_{i} r^{a} \left( {m - 1} \right) + p_{j} \left( {r + 1} \right)^{a} \ge t + p_{j} r^{a} + p_{i} \left( {r + 1} \right)^{a} + p_{i} \left( {r + 1} \right)^{a} (m - 1), $$

and this is true since

$$ \begin{aligned} \left({\text{i}}\right)\quad &p_{i} r^{a} \left( {m - 1} \right) \ge p_{i} \left( {r + 1} \right)^{a} (m - 1); \\ \left( {\text{ii}}\right) \quad &r^{a} (p_{i} - p_{j} ) \ge (r + 1)^{a} (p_{i} - p_{j} ). \end{aligned} $$

Subcase 1.2: After the job interchange, job $j$ in position $r$ becomes larger than job $i$ in position $r + 1$, i.e., $p_{i} \left( {r + 1} \right)^{a} < p_{j} r^{a}$. (No idle time is created between jobs $j$ and $i$.)

In this subcase, the completion time of job $i$ is

$$ C_{i} \left( {S_{2} } \right) = t + p_{j} r^{a} m + p_{i} \left( {r + 1} \right)^{a} . $$

We have to show that

$$ C_{j} \left( {S_{1} } \right) = t + p_{i} r^{a} m + p_{j} \left( {r + 1} \right)^{a} \ge t + p_{j} r^{a} m + p_{i} \left( {r + 1} \right)^{a} = C_{i} \left( {S_{2} } \right). $$

It is sufficient to show that

$$ t + p_{i} r^{a} + p_{i} r^{a} \left( {m - 1} \right) + p_{j} \left( {r + 1} \right)^{a} \ge t + p_{j} r^{a} + p_{j} r^{a} \left( {m - 1} \right) + p_{i} \left( {r + 1} \right)^{a} , $$

and this is true since

$$ \begin{aligned} &\left( {\text{i}} \right)\quad p_{i} r^{a} \left( {m - 1} \right) \ge p_{j} r^{a} (m - 1); \hfill \\ &\left( {\text{ii}} \right)\quad r^{a} (p_{i} - p_{j} ) \ge (r + 1)^{a} (p_{i} - p_{j} ). \hfill \\ \end{aligned} $$

Case 2: $p_{i} r^{a} < p_{k} \left( {r - 1} \right)^{a}$ (In $S_{1}$, there is no idle time between jobs $k$ and $i$.)

In this case, the completion time of job $j$ is

$$ C_{j} \left( {S_{1} } \right) = t + p_{k} \left( {r - 1} \right)^{a} (m - 1) + p_{i} r^{a} + p_{j} \left( {r + 1} \right)^{a} . $$

After the interchange, job $k$ in position $r - 1$ remains larger than job $j$ in position $r$ (since $p_{k} \left( {r - 1} \right)^{a} > p_{i} r^{a} > p_{j} r^{a}$) and larger than job $i$ in position $r + 1$ (since $p_{k} \left( {r - 1} \right)^{a} > p_{i} r^{a} > p_{i} (r + 1)^{a}$).

In this case, the completion time of job $i$ is

$$ C_{i} \left( {S_{2} } \right) = t + p_{k} \left( {r - 1} \right)^{a} (m - 1) + p_{j} r^{a} + p_{i} \left( {r + 1} \right)^{a} . $$

We have to show that

$$ \begin{aligned} C_{j} \left( {S_{1} } \right) & = t + p_{k} \left( {r - 1} \right)^{a} \left( {m - 1} \right) + p_{i} r^{a} + p_{j} \left( {r + 1} \right)^{a} \\ & \quad \ge t + p_{k} \left( {r - 1} \right)^{a} (m - 1) + p_{j} r^{a} + p_{i} \left( {r + 1} \right)^{a} = C_{i} \left( {S_{2} } \right). \\ \end{aligned} $$

It is sufficient to show that $p_{i} r^{a} + p_{j} \left( {r + 1} \right)^{a} \ge p_{j} r^{a} + p_{i} \left( {r + 1} \right)^{a}$.

The latter inequality is true since $r^{a} (p_{i} - p_{j} ) \ge (r + 1)^{a} (p_{i} - p_{j} )$.□

Next, we introduce the dynamic programming algorithm (DP1) for solving P1.

Based on Proposition 1, we begin by sorting the jobs in SPT order. Given this order, in each iteration of DP1, a single job is handled. If the job is processed, the maximum processing time (so far) is updated, and consequently, the new makespan is computed. If rejection is possible (i.e., without exceeding the upper bound on the rejection cost), this option is considered as well. If the job is rejected, the total rejection cost is updated, while the makespan remains unchanged.

We thus define the following state variables:

$j$: the number of jobs already handled

$e$: the available rejection cost

Note that the extension of $Fm/LE,p_{ijr} = p_{jr} /C_{\hbox{max} }$ to include also job rejection is not straightforward, and the above state variables are not sufficient. Although the actual processing time is a decreasing function (due to the learning effect), a decision to reject (one or several) jobs causes the jobs scheduled later to move backward and therefore increases their actual processing time. However, it may still be cheaper to reject a later job, rather than rejecting several shorter jobs scheduled earlier. Consider for example a sequence of four jobs $(x, y, z, w)$. If both jobs $x$ and $y$ are rejected, the larger jobs $z$ and $w$ are moved two positions backward. When job $z$ is rejected, job $w$ is moved a single position backward. Each of these options may be better, and thus, both should be considered. Specifically, if jobs $x$ and $y$ have been rejected, and we find at a later stage that it is better to reject job $z$, the former decision should be canceled. In order to demonstrate this phenomenon, consider the following four-job single-machine instance: The job processing times (sorted in SPT order), the rejection costs, the upper bound on the total rejection, and the learning factor are

$$ p_{j} = \left( {10, 25, 30, 60} \right),e_{j} = (1, 1, 3, 6),E = 3\;{\text{and}}\;a = - 0.32. $$

One can either reject jobs 1 and 2 with $\mathop \sum \nolimits p_{j} = 35$ and $\mathop \sum \nolimits e_{j} = 2$ or reject job 3 with $\mathop \sum \nolimits p_{j} = 30$ and $\mathop \sum \nolimits e_{j} = 3$. Option 1 seems to be better: if jobs 1 and 2 are rejected, the actual processing times, $p_{jr}$, of jobs 3 and 4 are 30 and 47.99, respectively, and $C_{\hbox{max} } = 77.99$. However, option 2 is, in fact, better. When rejecting job 3, $p_{11} = 10$, $p_{22} = 19.99$, and $p_{43} = 42.12$, attaining a smaller makespan value: $C_{\hbox{max} } = 72.12$.

Hence, we define an additional state variable:

$r$: the possible position for job $j$.

We use this variable to compute the objective function $f$ for job $j$ in case it is feasible to assign it to position $r$ such that $1 \le r \le j$, which practically allows the option to revoke previous decisions. When scheduling job $j$ at position $r$, previous jobs $1, \ldots , j - 1$ are scheduled up to position $r - 1$; thus, only $r \le j$ jobs are scheduled, while the remaining jobs are rejected. When the total rejection cost of the remaining jobs exceeds $e$, this option is not applicable, and the cost becomes unbounded. Note that position $r$ is advanced only in case the job is processed. We note that the above justification for the additional state variable $r$ is also relevant to the other problems studied in this paper, i.e., total completion time and total load.

Let $f\left( {j,r,e} \right)$ denote the minimum makespan of the partial schedule of jobs $1, \ldots ,j$, and maximum rejection cost $e$, in case job $j$ is assigned to position $r \le j$. At each iteration of the DP, the makespan of jobs 1 to $j$, having an upper bound $e \,(0 \le e \le E)$ on the rejection cost and position $r$, is computed. This computation is based on the processing costs of jobs 1 to $j - 1$ at possible positions 1 to $r - 1$, with an upper bound rejection cost of either $e$ or $e - e_{j}$.

In the recursion, we use a variable $\left( {p_{\hbox{max} } } \right)_{j}$, which is stored in memory. This variable is used to hold the largest actual processing time among the accepted jobs in the subset $\left\{ {1, \ldots ,j} \right\}$, attaining the minimum makespan with maximum rejection cost $e$. $\left( {p_{\hbox{max} } } \right)_{j}$ is updated if $p_{jr} > \left( {p_{\hbox{max} } } \right)_{j}$ as follows:

$$ \left( {p_{\hbox{max} } } \right)_{j} = \left\{ {\begin{array}{*{20}l} {\hbox{max} \left\{ {\left( {p_{\hbox{max} } } \right)_{j - 1} , p_{jr} } \right\},\quad {\text{if job }}j {\text{is processed}}} \hfill \\ {\left( {p_{\hbox{max} } } \right)_{j - 1} ,\quad {\text{else}}} \hfill \\ \end{array} ,\;{\text{where}}\;\left( {p_{\hbox{max} } } \right)_{0} = 0 .} \right. $$

Thus, if job $j$ is accepted and assigned to position $r$, its actual processing time is given by $p_{jr} = p_{j} \cdot r^{a}$.

In order to compute the completion time of job $j$, we define the (possible) idle time prior to its starting time on machine $m$:

$$ {\text{IT = }}\left( {m - 1} \right)\hbox{max} \left\{ {0,\left( {p_{\hbox{max} } } \right)_{j} - p_{jr} } \right\}. $$

Thus, we obtain the following recursion:

$$ f\left( {j,r,e} \right) = \left\{ {\begin{array}{*{20}l} {\hbox{min} \left( {f\left( {j - 1,r - 1,e} \right) + {\text{IT}} + p_{jr} ,f\left( {j - 1,r,e - e_{j} } \right)} \right),\quad e_{j} \le e} \hfill \\ {f\left( {j - 1,r - 1,e} \right) + \text{IT} + p_{jr} , \quad e_{j} > e} \hfill \\ \end{array} } \right. $$

The first line of the recursion reflects the option to accept or reject job $j$. The second line addresses the case where $e_{j}$ exceeds the current rejection cost limit $e$, implying that job $j$ must be accepted.

The boundary conditions are

$$ \begin{aligned} f\left( {j,j,0} \right) & = \mathop \sum \limits_{k = 1}^{j} p_{k} k^{a} + \left( {m - 1} \right) \left( {p_{\hbox{max} } } \right)_{j} , j, 1 \le j \le n, \\ f\left( {j,r,0} \right) & = \infty ,\;{\text{for}}\;r < j. \\ \end{aligned} $$

$$ f\left( {0,0,e} \right) = 0, e, 0 \le e \le E. $$

Note that $f\left( {j,r,0} \right) = \infty$, for $r < j$, since when the upper bound on the rejection cost is 0, all jobs must be processed, and their corresponding position $r$ must be $j$.

The optimal solution is given by $\min\nolimits_{\mathop{\mathop{\,}\limits_{1 \le r \le n}}\limits_{0 \le e \le E}} f \left( {n,r,e} \right)$.

Theorem 1

The computational complexity of DP1 is ${\varvec{O}\left( {\varvec{n}^{{\mathbf{2}}} \varvec{E}} \right)}$.

Proof

The recursive function is calculated for every job $j, 1 \le j \le n$, for every $1 \le r \le j$, and every rejection cost $e \le E$, resulting in running time of $O\left( {n^{2} E} \right)$. Reconstructing the solution is done by backtracking, starting at $f\left( {n,r_{0} ,e_{0} } \right)$ where $f\left( {n,r_{0} ,e_{0} } \right) = \min\nolimits_{\mathop{\mathop{\,}\limits_{1 \le r \le n}}\limits_{0 \le e \le E}} f \left( {n,r,e} \right)$, and ending at $f(0,0,0)$, for an addition of $O\left( {nE} \right)$ operations for finding $\min\nolimits_{\mathop{\mathop{\,}\limits_{1 \le r \le n}}\limits_{0 \le e \le E}} f \left( {n,r,e} \right)$, and $O\left( {n + E} \right)$ operations for the backtracking. We conclude that the total computational effort is $O\left( {n^{2} E} \right)$.□

Numerical example 1

Consider a six-job four-machine proportionate flowshop problem, and assume that the rejection upper bound is $E = 14$. The learning index value, $a = - 0.322$, reflects an 80% learning curve. The integer basic processing times are generated uniformly in the interval $\left[ {1, 50} \right]$ and then sequenced in SPT order and renumbered:

$$ p_{j} = (12, 19, 23, 24, 33, 48). $$

The integer job rejection costs are generated uniformly in the interval $\left[ {1, 50} \right]$:

$$ e_{j} = (2, 9, 4, 14, 9, 11). $$

Applying DP1, we obtain the following optimal solution:

The set of rejected jobs: $R = \{ J_{6} \}$, with total rejection cost $\sum\nolimits_{ j \in R} {e_{j} } = 11 \le 14 = E$.

The sequence of the processed jobs: $P = (J_{1} ,J_{2} ,J_{3} ,J_{4} ,J_{5} )$.

The actual processing times are $p_{jr} = \left( {12.000, 15.199, 16.147, 15.358, 19.654} \right)$, implying that the optimal makespan is $C_{\hbox{max} } = 137.320$.

3.1 Numerical study

We execute numerical tests in order to measure the running times of DP1. Random instances are generated with $n = 20, 40, 60, 80$ jobs and $m = 4$ machines. Processing times are generated uniformly in the interval [1, 100]. Three learning indices are chosen: $a = - 0.322$ (reflecting learning of 80%), $a = - 0.737$ (reflecting learning of 60%), and $a = - 1.322$ (reflecting learning of 40%). Rejection costs are generated uniformly in the interval [1, 50]. We utilize a tightness factor $\theta = 0.010, 0.020, 0.030$ to generate the upper bound on the total rejection cost. For each instance, the sum of the generated job rejection costs is computed and the upper bound is set to $E = \theta \sum\nolimits_{j = 1}^{n} {e_{j} }$. For each combination of $n, a$ and $E$, 20 instances are generated and solved. [The C ++ program is executed on an Intel (R) Core ™ i7-8650U CPU @ 1.90 GHz 16.0 GB RAM platform.]

The results are reported in Tables 1, 2, and 3 and verify that DP1 performs very well on medium-sized instances (of up to 80 jobs). Note that the worst-case running time does not exceed 5 ms even for instances of 80 jobs with the 40% learning rate and about 12% rejected jobs.

Table 1 DP1 (makespan)—average and worst-case running times with 80% learning curve

Table 2 DP1 (makespan)—average and worst-case running times with 60% learning curve

Table 3 DP1 (makespan)—average and worst-case running times with 40% learning curve

4 Minimizing total completion time

In this section, we focus on the objective function of minimum total completion time. First, we mention the paper of Biskup (1999), who proved that the shortest processing time (SPT) rule is optimal for the single-machine version $\left( {1/{\text{LE}}/{\text{TCT}}} \right)$. As mentioned above, Zhang et al. (2010) proved that the single-machine version with the option of job rejection $\left( {1/\sum\nolimits_{j \in R} {e_{j} } \le E/{\text{TCT}}} \right)$ is NP-hard in the ordinary sense. It follows that the problem studied here (P2) is NP-hard as well.

We start by proving that, in P2, SPT is optimal (for the processed jobs).

Proposition 2

An optimal schedule exists for problem P2 such that the processed (nonrejected) jobs are sequenced in SPT order (with respect to the basic processing times).

Proof

The proof is similar to that of Proposition 1 (based on a pairwise interchange argument). As above, let $S_{1}$ denote a sequence which is not SPT, and let $i$ and $j$ be the first pair of consecutive jobs which does not follow SPT order, i.e., $p_{i} > p_{j}$. Assume that job $i$ is in position $r$ and job $j$ is in position $r + 1$. Recall that in $S_{1}$ there is no idle time between jobs $i$ and $j$ because $p_{i} r^{a} > p_{j} (r + 1)^{a}$. As above, let $k$ be the job preceding job $i$ (i.e., processed in position $r - 1$), and $t$ denote the completion time of job $k$ on machine 1 (and the starting time of job $i$ on machine 1). The sequence $S_{2}$ is obtained from $S_{1}$ by interchanging jobs $i$ and $j$. Based on Proposition 1, the completion time of job $i$ in $S_{2}$ is not larger than the completion time of job $j$ in $S_{1}$. Proposition 1 focuses on the last machine, but it is clear that we can consider each machine as the last one, implying that the result is valid for all the machines. It follows that the total completion time of the jobs following job $i$ in $S_{2}$ (on all machines) is not larger than the total completion time of the jobs following $j$ in $S_{1}$. It remains to prove that the contribution of jobs $i$ and $j$ to the total completion time in $S_{2}$ is not larger than their contribution in $S_{1}$. The proof follows similar subcases to those specified in the proof of Proposition 1:

Case 1: $p_{i} r^{a} \ge p_{k} \left( {r - 1} \right)^{a}$. (In $S_{1}$, job $i$ is processed along the flowshop with no delay.)

In this case, the completion times of jobs $i$ and $j$ are

$$ C_{i} \left( {S_{1} } \right) = t + p_{i} r^{a} m. $$

$$ C_{j} \left( {S_{1} } \right) = t + p_{i} r^{a} m + p_{j} \left( {r + 1} \right)^{a} . $$

Thus, $C_{i} \left( {S_{1} } \right) + C_{j} \left( {S_{1} } \right) = t + p_{i} r^{a} m + t + p_{i} r^{a} m + p_{j} \left( {r + 1} \right)^{a}$.

Subcase 1.1: After the job interchange, job $i$ in position $r + 1$ remains larger than job $j$ in position $r$, i.e., $p_{i} \left( {r + 1} \right)^{a} \ge p_{j} r^{a}$. (An idle time is created between jobs $j$ and $i$.)

In this subcase, the sum of the completion times of jobs $j$ and $i$ is

$$ C_{j} \left( {S_{2} } \right) + C_{i} \left( {S_{2} } \right) = t + p_{j} r^{a} m + t + p_{j} r^{a} + p_{i} \left( {r + 1} \right)^{a} m. $$

We have to show that

$$ \begin{aligned} C_{i} \left( {S_{1} } \right) + C_{j} \left( {S_{1} } \right) & = t + p_{i} r^{a} m + t + p_{i} r^{a} m + p_{j} \left( {r + 1} \right)^{a} \\ & \quad \ge t + p_{j} r^{a} m + t + p_{j} r^{a} + p_{i} \left( {r + 1} \right)^{a} m = C_{j} \left( {S_{2} } \right) + C_{i} \left( {S_{2} } \right). \\ \end{aligned} $$

It is sufficient to show that

$$ p_{i} r^{a} m + p_{i} r^{a} m + p_{j} \left( {r + 1} \right)^{a} \ge p_{j} r^{a} m + p_{j} r^{a} + p_{i} \left( {r + 1} \right)^{a} m, $$

or equivalently that

$$ p_{i} \left[ {r^{a} m + \left( {r^{a} - \left( {r + 1} \right)^{a} } \right)m} \right] \ge p_{j} \left[ {r^{a} m + \left( {r^{a} - \left( {r + 1} \right)^{a} } \right)} \right]. $$

The latter is true since

$$ \begin{aligned} &\left( {\text{i}} \right)\quad p_{i} > p_{j} ; \hfill \\ &\left( {\text{ii}} \right)\quad\left( {r^{a} - \left( {r + 1} \right)^{a} } \right)m > r^{a} - \left( {r + 1} \right)^{a} . \hfill \\ \end{aligned} $$

Subcase 1.2: After the job interchange, job $j$ in position $r$ becomes larger than job $i$ in position $r + 1$. (There is no idle time between jobs $j$ and $i$.)

In this subcase, the sum of the completion times of jobs $j$ and $i$ is

$$ C_{j} \left( {S_{2} } \right) + C_{i} \left( {S_{2} } \right) = t + p_{j} r^{a} m + t + p_{j} r^{a} m + p_{i} \left( {r + 1} \right)^{a} . $$

We have to show that

$$ \begin{aligned} C_{i} \left( {S_{1} } \right) + C_{j} \left( {S_{1} } \right) & = t + p_{i} r^{a} m + t + p_{i} r^{a} m + p_{j} \left( {r + 1} \right)^{a} \\ & \quad \ge t + p_{j} r^{a} m + t + p_{j} r^{a} m + p_{i} \left( {r + 1} \right)^{a} = C_{j} \left( {S_{2} } \right) + C_{i} \left( {S_{2} } \right). \\ \end{aligned} $$

The latter inequality is true since

$$ p_{i} \left( {2r^{a} m - \left( {r + 1} \right)^{a} ) \ge p_{j} (2r^{a} m - \left( {r + 1} \right)^{a} } \right). $$

Case 2: $p_{i} r^{a} < p_{k} \left( {r - 1} \right)^{a}$ (In $S_{1}$, there is no idle time between jobs $k$ and $i$.)

In this case, the completion time of jobs $i$ and $j$ is

$$ \begin{aligned} C_{i} \left( {S_{1} } \right) + C_{j} \left( {S_{1} } \right) = t + p_{k} \left( {r - 1} \right)^{a} \left( {m - 1} \right) + p_{i} r^{a} + t + p_{k} \left( {r - 1} \right)^{a} \left( {m - 1} \right) + p_{i} r^{a} + p_{j} \left( {r + 1} \right)^{a} . \\ \end{aligned} $$

As in the proof of Proposition 1, after the interchange, job $k$ in position $r - 1$ remains larger than job $j$ in position $r$ (since $p_{k} \left( {r - 1} \right)^{a} > p_{i} r^{a} > p_{j} r^{a}$) and larger than job $i$ in position $r + 1$ (since $p_{k} \left( {r - 1} \right)^{a} > p_{i} r^{a} > p_{i} (r + 1)^{a}$).

In this case, the completion times of jobs $j$ and $i$ are

$$ \begin{aligned} C_{j} \left( {S_{2} } \right) + C_{i} \left( {S_{2} } \right) = t + p_{k} \left( {r - 1} \right)^{a} (m - 1) + p_{j} r^{a} + t + p_{k} \left( {r - 1} \right)^{a} (m - 1) + p_{j} r^{a} + p_{i} \left( {r + 1} \right)^{a} . \\ \end{aligned} $$

We have to show that

$$ \begin{aligned} C_{i} \left( {S_{1} } \right) + C_{j} \left( {S_{1} } \right) & = t + p_{k} \left( {r - 1} \right)^{a} \left( {m - 1} \right) + p_{i} r^{a} + t + p_{k} \left( {r - 1} \right)^{a} \left( {m - 1} \right) + p_{i} r^{a} + p_{j} \left( {r + 1} \right)^{a} \\ & \quad \quad \ge \,t + p_{k} \left( {r - 1} \right)^{a} \left( {m - 1} \right) + p_{j} r^{a} + t + p_{k} \left( {r - 1} \right)^{a} \left( {m - 1} \right) + p_{j} r^{a} + p_{i} \left( {r + 1} \right)^{a} \\ & = C_{j} \left( {S_{2} } \right) + C_{i} \left( {S_{2} } \right). \\ \end{aligned} $$

This inequality is true since

$$ p_{i} \left( {2r^{a} - \left( {r + 1} \right)^{a} ) \ge p_{j} (2r^{a} - \left( {r + 1} \right)^{a} } \right). $$

□

Next, we introduce the dynamic programming algorithm (denoted DP2) for solving P2. Based on Proposition 2, we begin by sorting the jobs in SPT order.

Let $f\left( {j,r,e} \right)$ denote the minimum total completion time (TCT) of the accepted jobs in subset $\left( {1, \ldots ,j} \right)$ and maximum rejection cost $e$, in the case that job $j$ is assigned to position $r \le j$. At each iteration of the DP, the TCT of jobs 1 to $j$, having an upper bound $e\;(0 \le e \le E)$ on the rejection cost and position $r$, is computed. As above, the computation is based on the processing costs of jobs 1 to $j - 1$ at possible positions 1 to $r - 1$, with an upper bound rejection cost of either $e$ or $e - e_{j}$.

The variable $C_{j}$ is used to hold the completion time (on machine $m$) of the accepted jobs in subset $\left\{ {1, \ldots ,j} \right\}$, attaining the minimum TCT with maximum rejection cost $e$, and is defined as follows:

$$ C_{j} = \left\{ {\begin{array}{*{20}l} {C_{j - 1} + \text{IT} + p_{jr} ,\quad {\text{if job }}j {\text{is processed}}} \hfill \\ {C_{j - 1} ,\quad {\text{else}}} \hfill \\ \end{array} ,\;{\text{where}}\;C_{0} = 0.} \right. $$

($p_{jr}$ and IT are defined in Sect. 3.)

As above (see DP1), at each iteration of the algorithm, the scheduler needs to decide whether to accept or reject job $j$. Job $j$ must be accepted in case its rejection cost exceeds the current rejection cost limit $e$. Otherwise, job $j$ is either accepted or rejected.

We obtain the following recursion formula for DP2:

$$ f\left( {j,r,e} \right) = \left\{ {\begin{array}{*{20}l} {\hbox{min} \left( {f\left( {j - 1,r - 1,e} \right) + C_{j} ,f\left( {j - 1,r,e - e_{j} } \right)} \right),\quad e_{j} \le e} \hfill \\ {f\left( {j - 1,r - 1,e} \right) + C_{j} ,\quad e_{j} > e} \hfill \\ \end{array} .} \right. $$

As in DP1, the first line of the recursion reflects the option to accept or reject job $j$. The second line addresses the case where $e_{j}$ exceeds the current rejection cost limit $e$, implying that job $j$ must be accepted.

The boundary conditions are

$$ \begin{aligned} f\left( {j,j,0} \right) & = \mathop \sum \limits_{k = 1}^{j} C_{k} , j, 1 \le j \le n, \\ f\left( {j,r,0} \right) & = \infty ,\;{\text{for}}\;r < j. \\ \end{aligned} $$

$$ f\left( {0,0,e} \right) = 0, e, 0 \le e \le E. $$

The optimal solution is given by $\min\nolimits_{\mathop{\mathop{\,}\limits_{1 \le r \le n}}\limits_{0 \le e \le E}} f \left( {n,r,e} \right)$.

Theorem 2

The computational complexity of DP2 is ${\varvec{O}\left( {\varvec{n}^{{\mathbf{2}}} \varvec{E}} \right)}$.

The proof is identical to that given in Sect. 3 for DP1 and is thus omitted.

Numerical example 2

We use the input designated for example 1. The optimal solution (obtained by DP2) is

$$ R = \{ J_{3} ,J_{5} \} ,\;{\text{with}}\;\sum\nolimits_{j \in R} {e_{j} } = 13 \le 14 = E. $$

$$ P = (J_{1} ,J_{2} ,J_{4} ,J_{6} ). $$

$p_{jr} = \left( {12.000, 15.199, 16.849, 30.717} \right)$, and the optimal total completion time is

$$ {\text{TCT}} = 382.309. $$

4.1 Numerical study

We apply the scheme designated in Sect. 3 to evaluate the efficiency of DP2. The tightness factor values, used to generate the upper bound on the total rejection cost, are $\theta = 0.007, 0.014, 0.021$. The results are reported in Tables 4, 5, and 6. Similar to the results obtained by DP1, the worst-case running time does not exceed 4 ms (in the same setting of 80 jobs, 40% learning rate, and about 12% rejection). As above, based on our results, it is clear that DP2 can easily solve medium-sized instances and thus may be appropriate for real-life settings.

Table 4 DP2 (TCT)—average and worst-case running times with 80% learning curve

Table 5 DP2 (TCT)—average and worst-case running times with 60% learning curve

Table 6 DP2 (TCT)—average and worst-case running times with 40% learning curve

5 Minimizing total load

The problem of minimizing the total load on a proportionate flowshop with general position-dependent job processing times has been solved in polynomial time by Fiszman and Mosheiov (2018). It follows that the special case of exponential learning is solved in polynomial time. On the other hand, in a single-machine setting, minimizing total load is reduced to minimizing makespan. As mentioned above, minimizing makespan on a single machine with the option of rejection (and an upper bound on the total permitted rejection cost) was shown to be NP-hard (Zhang et al. 2010). Hence, problem P3 studied in this section is NP-hard.

Note that in Proposition 1 we proved that, when minimizing makespan, the processed (nonrejected) jobs are sequenced in SPT. Since this proof is valid for the largest completion time on any machine, we obtain the following corollary:

Corollary 3

An optimal schedule exists for problem P3 such that the processed (nonrejected) jobs are sequenced in SPT order.

Based on Corollary 3, we propose the following DP for problem $Fm/LE,p_{ijr} = p_{jr} ,\sum\nolimits_{j \in R} {e_{j} } \le E/{\text{TL}}$, denoted DP3. The DP requires appropriate adaptations due to the new objective function. As above, we begin by sorting the jobs in SPT order.

In this case, $f\left( {j,r,e} \right)$ denotes the minimum total load (TL) of the accepted jobs in subset $\left( {1, \ldots ,j} \right)$ with maximum rejection cost $e$, in case job $j$ is assigned to position $r \le j$. Again, at each iteration of the DP, the TL of jobs 1 to $j$ is computed (with an upper bound $e \,(0 \le e \le E)$ on the rejection cost and position $r$). The computation is based on the processing costs of jobs 1 to $j - 1$ at possible positions 1 to $r - 1$, with an upper bound rejection cost of either $e$ or $e - e_{j}$.

In order to compute the makespan on machine $i$, we define the (possible) idle time prior to the starting time of job $j$ on machine $i$:

$$ {\text{IT}}_{i} = (i - 1)\hbox{max} \left\{ {0, \left( {p_{\hbox{max} } } \right)_{j} - p_{jr} } \right\}, $$

where $p_{jr}$ and $\left( {p_{\hbox{max} } } \right)_{j}$ are as defined in Sect. 3.

Again, at each iteration of the algorithm, a job is either accepted and processed or rejected. If the job’s rejection cost exceeds the current cost limit $e$, then the job must be rejected. Otherwise, the scheduler may decide either to accept or to reject it.

The recursion formula for DP3 is

$$ f\left( {j,r,e} \right) = \left\{ {\begin{array}{*{20}l} {\hbox{min} \left( {f\left( {j - 1,r - 1,e} \right) + \mathop \sum \limits_{i = 1}^{m} \left( {{\text{IT}}_{i} + p_{jr} } \right),f\left( {j - 1,r,e - e_{j} } \right)} \right),\quad e_{j} \le e} \hfill \\ {f\left( {j - 1,r - 1,e} \right) + \mathop \sum \limits_{i = 1}^{m} \left( {{\text{IT}}_{i} + p_{jr} } \right), \quad e_{j} > e} \hfill \\ \end{array} } \right.. $$

The boundary conditions are

$$ \begin{aligned} f\left( {j,j,0} \right) & = f\left( {j - 1,j - 1,0} \right) + \mathop \sum \limits_{i = 1}^{m} \left( {{\text{IT}}_{i} + p_{jr} } \right), j, 1 \le j \le n, \\ f\left( {j,r,0} \right) & = \infty ,\;{\text{for}}\;r < j. \\ \end{aligned} $$

$$ f\left( {0,0,e} \right) = 0, e, 0 \le e \le E. $$

The optimal solution is given by $\min\nolimits_{\mathop{\mathop{\,}\limits_{1 \le r \le n}}\limits_{0 \le e \le E}} f \left( {n,r,e} \right)$.

Theorem 3

The computational complexity of DP3 is ${\varvec{O}\left( {\varvec{n}^{{\mathbf{2}}} \varvec{E}} \right)}$.

(As above, the proof is omitted since it is similar to that of Theorem 1.)

Numerical example 3

Again, we consider the input of example 1. The optimal solution obtained by DP3 is

$$ R = \{ J_{1} ,J_{6} \} ,\;{\text{with}}\sum\nolimits_{ j \in R} {e_{j} } = 13 \le 14 = E. $$

$$ P = (J_{2} ,J_{3} ,J_{4} ,J_{5} ). $$

$$ p_{jr} = (19.000, 18.399, 16.849, 21.118). $$

The optimal total load: ${\text{TL}} = 428.172$.

5.1 Numerical study

We repeat the procedure for creating the input parameters of Sect. 3, with two modifications: $n = 10, 20, 30, 40, 50$ and $\theta = 0.003, 0.006, 0.009$. The results obtained by DP3 are reported in Tables 7, 8, and 9. In this case, the worst-case running time did not exceed 3 ms on the largest setting consisting of 50 jobs, 40% learning, and 21.5% rejection rate. As in the previous sections, we conclude that, for the objective function of total load, DP3 solves medium-sized instances in reasonable running time.

Table 7 DP3 (TL)—average and worst-case running times with 80% learning curve

Table 8 DP3 (TL)—average and worst-case running times with 60% learning curve

Table 9 DP3 (TL)—average and worst-case running times with 40% learning curve

6 Conclusions

We study three scheduling problems on a proportionate flowshop. The objective functions considered are minimum makespan, minimum total completion time, and minimum total load. In all settings, we assume: (i) a learning process (implying that the processing time of a job processed later in the sequence is reduced) and (ii) the option of job rejection (i.e., the scheduler may process only a subset of the jobs and be penalized for the rejected jobs). An upper bound on the total permitted rejection cost is assumed. All three problems studied here are NP-hard, and we thus focus on the introduction of pseudopolynomial dynamic programming algorithms. Our extensive numerical study indicates that the proposed algorithms are very efficient for handling medium-sized problems. A challenging topic for future research is the extension of our proposed solution procedures to the more general machine setting of a (general) flowshop.