1 Introduction

Flowshop setting is characterized by several different machines in series and each job must undergo an operation on each of the machines. A special case of the flowshop environment is the proportionate flowshop (PFS) setting where the processing times are machine-independent and the storage between consecutive machines is assumed to be unlimited. This setting replicates many production systems where each operation is relatively short and the goods are small in size. Thus, each machine can start its operation on the next job in the queue regardless of the status of the job on the succeeding machine, implying that the production line is not susceptible to blocking.

The PFS machine setting can be seen as a generalization of the single machine setting and its importance is revealed by the comprehensive review of Panwalkar et al. (2013) and the following recent studies by Mor and Mosheiov (2014), Panwalkar and Koulamas (2015, 2017), Cheng et al. (Cheng et al. 2018), Gerstl et al. (2019). Quite a few solutions to classical problems on a single machine can be applied, in a straightforward manner, to their PFS equivalents. Such problems include, among others, minimizing the total completion time, minimizing the total tardiness, and minimizing the number of tardy jobs (see Pinedo 2016). In other problems, the sequencing of the jobs may cause idle times between consecutive jobs, affecting the complexity of the solution. Several solutions thus consider a more involved approach, such that solutions to the problem of maximizing the number of just-in-time jobs (Gerstl et al. 2015), the minmax earliness problem (Mor and Mosheiov 2015a), minimizing the number of early jobs (Mor and Mosheiov 2015b), and minsum/minmax common flow allowance (Mor and Mosheiov 2016a).

Several recent articles, Shabtay and Oron (2016), Li et al. (2017), Fiszman and Mosheiov (2018) and Mor et al. (2019), combine the setting of PFS machine with the method of job rejection. This method is usually implemented in manufacturing systems to overcome overloaded assembly lines. Thus, the operation management is given the option to process a subset of the jobs, and reject, or alternatively out-source, the complementary subset. Utilizing this method may decrease the overload, optimize the utilization of the inputs, improve the time to market, and eventually increase the profit. To simulate real-life situations, each rejected job incurs a job-dependent penalty. Hence, the given total rejection cost is limited and may impact the profit of the production plant, suggesting solutions based on analytical methods. The intensive research on job rejection is exposed by the survey of Shabtay et al. (2013) as well as later papers: Shabtay (2014), Gerstl and Mosheiov (2015), Koulamas and Panwalkar (2015), Mor and Mosheiov (2016b), Agnetis and Mosheiov (2017), Gerstl et al. (2017), Zhong et al. (2017), and Mor and Mosheiov (2018).

Recently, Mor and Shapira (2019) improved the computational complexity of two problems studied in Shabtay and Oron (2016): minimizing the makespan subject to an upper bound on the total rejection cost, and minimizing the total rejection cost subject to a constraint on the makespan. In the current paper, we complement the results of the last two articles by addressing four regular performance measures, that is, when the objective function is a non-decreasing function of the completion times of the jobs. In more detail, the objective functions studied here are total completion time, maximum tardiness, total tardiness, and total weighted number of tardy jobs. The goal is to minimize these objective functions subject to a constraint on the total rejection cost. All the addressed problems are NP-hard as their single machine counterpart variants were proved to be NP-hard by Zhang et al. (2010). To the best of our knowledge, there are no detailed solutions in scheduling literature to the first two problems, whereas the last two problems were never addressed. For each problem, we, therefore, provide a pseudo-polynomial dynamic programming (DP) solution algorithm; furthermore, we enhance the reported running time of the first two problems. Our extensive numerical study demonstrates the DPs ability to solve real-life instances efficiently.

The paper is organized as follows. The notations are presented in Sect. 2. Sections 3–6 address our proposed solutions to the problems of minimizing the total completion time, maximum tardiness, total tardiness, and total weighted number of tardy jobs, respectively. The conclusions are finally provided in Sect. 7.

2 Notations

Assume that there are given \( n \) jobs to be processed on an \( m \)-machine PFS. The processing times of the jobs are independent of the machine they are processed on, i.e., \( p_{ij} = p_{j} , i = 1, \ldots ,m, j = 1, \ldots ,n \).

Let \( A \) and \( \bar{A} \) denote the subsets of accepted and rejected jobs, respectively. Clearly, their intersection is empty and their union is the complete set of jobs.

The notations \( p_{{max}} \) and \( P \) are used to denote the processing time of the longest job between those jobs that are processed and the total processing time of all jobs, correspondingly, i.e., \( p_{{max}} = {{max}}_{j \in A} \left\{ {p_{j} } \right\} \) and \( P = \sum \nolimits_{j = 1}^{n} p_{j} \).

Each job is assigned a rejection cost \( e_{j} \), and contributes this value to the total rejection cost in case it is rejected. The latter quantity is upper bounded by a predefined constant \( E \); formally, the restriction is that \( \sum \nolimits_{{ j \in \bar{A}}} e_{j} \le E. \)

Given a schedule of the processed jobs, the notation \( C_{ij} \) denotes the completion time of job \( j \), \( j \in A \) on machine \( i, i = 1, \ldots ,m \). The completion time of the last operation of job \( j \), i.e., on machine \( m \) is denoted by \( C_{j} \), i.e., \( C_{j} \equiv C_{mj} \). The makespan on a given \( m \)-machine PFS is attained by \( C_{{max}} = \left( {m - 1} \right) {{max}}_{1 \le j \le n} \left\{ {p_{j} } \right\} + \sum \nolimits_{j = 1}^{n} p_{j} = \left( {m - 1} \right) {{max}}_{1 \le j \le n} \left\{ {p_{j} } \right\} + P \) (see Pinedo 2016) and does not depend on a certain order. Thus, the makespan of the accepted jobs is \( C_{{max}} = \left( {m - 1} \right)p_{{max}} + \sum \nolimits_{ j \in A} p_{j} \).

Let \( d_{j} \) denote the due-date of job \( j, j = 1, \ldots ,n \). The tardiness of job \( j \) (on machine \( m \)) is defined as \( T_{j} = \hbox{max} \left\{ {0, C_{j} - d_{j} } \right\} \), and the maximum tardiness, among all accepted jobs, is given as \( T_{{max}} = {{max}}_{j \in A} \left\{ {T_{j} } \right\} \).

Let, \( U_{j} \) denote the tardiness unit penalty of job \( j, j = 1, \ldots n \), such that \( U_{j} = 1 \) if \( T_{j} > 0 \) and \( U_{j} = 0 \), otherwise. In addition, we denote by \( w_{j} \) the weight (relative importance) of job \( j, j = 1, \ldots ,n \). Thus, the total weighted number of the (accepted) tardy jobs is defined as \( \sum \nolimits_{ j \in A} w_{j} U_{j} \).

All the objective functions which we focus on are regarded as regular performance measures, i.e., non-decreasing functions of the jobs’ completion times. In this paper, our goal is to minimize each of these measures subject to the constraint that the total rejection cost cannot be greater than a given upper bound \( E \). In the following, we utilize the three-field notation introduced by Graham et al. (1979), to formulate the four addressed problems.

In our first problem, the scheduling measure is total completion time, that is:

$$ P1: F_{m} /p_{ij} = p_{j} , {\text{rej}}, \mathop \sum \limits_{{ j \in \bar{A}}} e_{j} \le E/\mathop \sum \limits_{ j \in A} C_{j} . $$

Next, our aim is to minimize the maximum tardiness:

$$ P2:F_{m} /p_{ij} = p_{j} , {\text{rej}},\mathop \sum \limits_{{ j \in \bar{A}}} e_{j} \le E/T_{{\max}} . $$

To formulate the last two problems, we define a common due-date, denoted by \( d \), that is shared by all jobs. Thus, in the third problem, the objective is to minimize the total tardiness with a common due-date, that is:

$$ P3:F_{m} /p_{ij} = p_{j} , d_{j} = d,{\text{rej}},\mathop \sum \limits_{{ j \in \bar{A}}} e_{j} \le E/\mathop \sum \limits_{ j \in A} T_{j} . $$

Finally, the aim is to minimize the total weighted number of tardy jobs with a common due-date:

$$ P4:F_{\text{m}} /p_{ij} = p_{j} ,d_{j} = d, {\text{rej}},\mathop \sum \limits_{{ j \in \bar{A}}} e_{j} \le E/\mathop \sum \limits_{ j \in A} w_{j} U_{j} . $$

3 Problem \( P1: F_{\text{m}} /p_{ij} = p_{j} , {\text{rej}}, \sum \nolimits_{{ j \in \bar{A}}} e_{j} \le E / \sum \nolimits_{ j \in A} C_{j} . \)

Problem \( 1/ {\text{rej}}, \sum \nolimits_{{ j \in \bar{A}}} e_{j} \le E / \sum \nolimits_{ j \in A} C_{j} \) was reported by Shabtay et al. (2012) to be solved in \( O\left( {n^{2} \sum \nolimits_{{ j \in \bar{A}}} e_{j} } \right) \) time, although no explicit solution was provided. In this section, we provide a DP, which is faster by a factor of \( n \), i.e., \( O\left( {n \sum \nolimits_{{ j \in \bar{A}}} e_{j} } \right) \), even for the setting of PFS and not only for a single machine environment.

The order of the jobs in an optimal instance of the classical problem \( 1\text{ / / }\sum C_{j} \) is known to be in accordance with the Shortest Processing Time first (SPT) rule. The same order of the jobs is also valid for the PFS setting (see Pinedo 2016). As stated in Sect. 2, the completion time of job \( j \) on a PFS setting is sequence independent, and is given by \( C_{j} = \left( {m - 1} \right) {\hbox{max} }_{1 \le k \le j} \left\{ {p_{k} } \right\} + \sum\nolimits_{k = 1}^{j} {p_{k} } = \left( {m - 1} \right)p_{j} + \sum\nolimits_{k = 1}^{j} {p_{k} } \), where the last equation follows from the SPT order existence in an optimal schedule.

The DP for P1 uses a variable \( P_{j} \) in correspondence to every job \( j \), which is stored in memory. \( P_{j} \) is used to hold the total processing times of the accepted jobs in the subset of jobs \( \left( {1, \ldots ,j} \right) \) that achieves the minimum total completion time having maximum rejection cost \( e \), and is defined as follows:

$$\begin{aligned} P_{j} = \left\{ {\begin{array}{llll} {P_{j - 1} + p_{j} ,} &\quad { {\text{if job}} j \;{\text{is processed}}} \\ {P_{j - 1} , } &\quad {{\text{othewise}} } \\ \end{array} } \right.,\;{\text{where}}\;P_{0} = 0.\end{aligned} $$

Thus, the completion (on machine \( m \)) of job \( j \) in subset \( \left( {1, \ldots ,j} \right) \), can be calculated in a straightforward manner using the simple equation, \( C_{j} = \left( {m - 1} \right)p_{j} + P_{j} \).

Let \( f\left( {j,e} \right) \) denote the minimum total completion time for the partial schedule of jobs \( 1, \ldots ,j \) with maximum rejection cost \( e \). At each iteration of the DP, the scheduling cost of jobs 1 to \( j \) having an upper bound \( e \left( {0 \le e \le E} \right) \) on the rejection cost, is computed, based on the processing costs of jobs 1 to \( j - 1 \), with an upper bound on the rejection cost of either \( e \) or \( e - e_{j} \). Thus, at each iteration of the algorithm, the scheduler needs to decide whether to accept or reject job \( j \), as follows:

  • Job \( j \) must be accepted in case its rejection cost exceeds the current rejection cost limit \( e \).

  • Job \( j \) may be accepted in case its cost is not greater than the minimum processing cost of jobs 1 to \( j - 1 \), and upon acceptance, the cost is increased by \( \left( {m - 1} \right)p_{j} + P_{j} \).

  • Job \( j \) may be rejected in case this minimizes the processing cost.

Now, we are ready to present the DP.

Dynamic programming algorithm DP1

$$ f\left( {j,e} \right) = \left\{ {\begin{array}{*{20}l} {{\min} \left( {\begin{array}{*{20}l} {f\left( {j - 1,e} \right) + \left( {m - 1} \right)p_{j} + P_{j} } \\ {f\left( {j - 1,e - e_{j} } \right) \hfill } \\ \end{array} } \right), \quad e_{j} \le e } \\ {f\left( {j - 1,e} \right) + \left( {m - 1} \right)p_{j} + P_{j} ,\quad {\text{othewise}}} \hfill\\ \end{array} } \right. $$
(1)

The boundary conditions are:

$$ \begin{aligned} f\left( {j,0} \right) & = \left( {m - 1} \right)p_{j} + \mathop \sum \limits_{k = 1}^{j} p_{k} , \quad j, 1 \le j \le n \\ f\left( {0,e} \right) & = 0,\quad e, 0 \le e \le E. \\ \end{aligned} $$

The optimal solution is given as \( f\left( {n,E} \right) \).

Theorem 1

Algorithm\( {\text{DP1}} \)’s complexity is\( O\left( {nE} \right) \).

Proof

The recursive formula for \( f\left( {j,e} \right) \) given in (1) is processed by a nested loop for each job \( j, 1 \le j \le n \), and each rejection cost \( e \le E \). The solution is reconstructed by means of backtracking, starting at the last cell in which \( j = n \) and \( e = E \), and ending at the first cell where \( j = e = 0\). Summing up the processing times of both stages, the computational complexity of \( DP1 \) is \( O\left( {nE} \right) + O\left( {n + E} \right) = O\left( {nE} \right) \). □

Example 1

The following illustration is given for clarity.

Let \( m = 4, \;n = 6, E = 54 \), and assume that the jobs are sequenced in SPT order and renumbered.

The processing times are \( p = \left( {13, 14, 17, 26, 27, 45} \right) \).

The job-dependent rejection costs are \( e = \left( {18, 22, 14, 10, 9, 38} \right) \).

The solution attained from running \( {\text{DP}}1 \) is accepting the first, second, and sixth jobs, having \( \sum \nolimits_{ j \in A} C_{j} = 328 \), while rejecting the third, fourth, and fifth jobs with \( \sum \nolimits_{{j \in \bar{A}}} e_{j} = 33 \le 35 = E. \)


Numerical study To evaluate our proposed solution in practice, we ran \( {\text{DP1}} \) on several numerical, randomly generated, instances. As the running times are uninfluenced by the number of machines, we restricted the illustrations to four machines only. However, being the number of jobs the main parameter of the running time, we considered an increasing size of the set of input jobs: \( n = 500, \;1000, \;1500 \) and \( 2000 \) jobs. The processing times of all jobs and their corresponding rejection costs were uniformly generated in the range of \( \left[ {1, 50} \right] \). To avoid trivial instances, i.e., solutions where the majority of the jobs are either accepted or rejected, we generated the values of \( E \) in three different intervals. These intervals guaranty challenging instances with approximately equal numbers of accepted and rejected jobs, as expected in real-life circumstances. As the maximum rejection cost in this setting is restricted to \( \bar{e} = 50 \), the total rejection upper bound cost, \( E \), was generated uniformly in the intervals \( \left[ {0.02, 0.03} \right]n\bar{e},\left[ {0.050, 0.055} \right]n\bar{e} \), and \( \left[ {0.08, 0.10} \right]n\bar{e} \), simulating rejection of approximately 20%, 30%, and 40% jobs, respectively. Twenty random instances were created for each pair of \( n \) and \( E \) and then fed to the proposed algorithm.

C ++ executed on an Intel (R) Core ™ i7-8650U CPU @ 1.90 GHz 16.0 GB RAM platform. Table 1 presents the average- and worst-case running times in milliseconds. The number of jobs, \( n \), is given in the first column, and the intervals controlling the maximal rejection cost, \( E \), are given in the second column. The third and fourth columns present the average and worst-case running times, respectively. Although it is not unexpected, it is noteworthy to observe that the running times increase as the values of \( n \) and \( E \) increase. This phenomenon is due to the tabulation approach, which is standard practice in solving DP algorithms. In this approach, all sub-problems are solved and stored in memory. In the particular case of DP1, the size of used memory is \( n \times E \) (See Theorem 1). This characteristic is true for all the numerical studies presented throughout this study. The results indicate that DP1 is extremely efficient and can solve large-sized problems. In particular, the worst-case running time for instances of 2000 jobs and 40% of rejected jobs did not exceed 138 milliseconds (ms).

Table 1 Average- and worst-case running times of DP1 algorithm for Problem P1
Full size table

4 Problem \( P2: F_{m} /p_{ij} = p_{j} , {\text{rej}}, \sum \nolimits_{{ j \in \bar{A}}} e_{j} \le E/T_{{\max}} \)

The second problem dealt within this paper is minimizing the maximum tardiness, limited by an upper bound on the cost of all rejected jobs, and improve the latest results reported in scheduling theory. Shabtay and Oron (2016) suggest utilizing their \( O\left( {n^{2} PE} \right) \) time, Pareto optimal solution, to solve P2. In the following, we prove that P2 can be solved in \( O\left( {nPE} \right) \).

First, we prove that, although idle time between consecutive jobs may exist, similarly to \( 1/T_{{\max}} \), also \( F_{\text{m}} /p_{ij} = p_{j} /T_{{\max}} \) can be optimally solved by sequencing the jobs in Earliest Due-Date first (EDD) order.

Property 1

There exists an optimal schedule for \( F_{\text{m}} /p_{ij} = p_{j} /T_{{\max}} \) in which the jobs are sequenced in EDD order.

Proof

Let schedule \( \pi_{1} \) be an optimal schedule which is not sequenced in EDD order. Therefore, there exist a pair of consecutive jobs in \( \pi_{1} \) that are scheduled in reverse due-date order. Let \( k \) and \( l \) denote the first pair of jobs that violates the EDD order and are scheduled at positions \( i \) and \( i + 1 \), respectively. Recall that \( d_{k} \) and \( d_{l} \) denote the due-dates of jobs \( k \) and \( l \), respectively.

We differentiate between several cases depending on the values of \( p_{l} \) and \( p_{k} \).

Case 1 \( {\hbox{max} }_{1 \le j \le i - 1} \left\{ {p_{j} } \right\} \ge p_{k} ,p_{l} . \)

Due to the dominance of the largest job on the completion times of jobs \( k \) and \( l \), there is no idle time between the jobs in schedule \( \pi_{1} \).

Let \( t \) be the starting time of job \( k \) on machine \( m \) in the optimal schedule \( \pi_{1} \). The contribution cost of jobs \( k \) and \( l \) in \( \pi_{1} \) is

$$ Z_{{\pi_{1} }} \left( {k,l} \right) = \hbox{max} \left\{ {t + p_{k} - d_{k} , t + p_{k} + p_{l} - d_{l} } \right\}. $$

Construct a schedule \( \pi_{2} \) by a standard pair-wise interchange of jobs \( k \) and \( l \) and similar to schedule \( \pi_{1} \), there is no idle time between these jobs:

$$ Z_{{\pi_{2} }} \left( {k,l} \right) = \hbox{max} \left\{ {t + p_{l} - d_{l} , t + p_{l} + p_{k} - d_{k} } \right\}. $$

We prove that \( Z_{{\pi_{1} }} \left( {k,l} \right) \ge Z_{{\pi_{2} }} \left( {k,l} \right) \) by showing that:

$$ t + p_{k} + p_{l} - d_{l} \ge \hbox{max} \left\{ {t + p_{l} - d_{l} , t + p_{l} + p_{k} - d_{k} } \right\}. $$

The latter is true due to the following inequalities:

  1. i.

    \( t + p_{k} + p_{l} - d_{l} \ge t + p_{l} - d_{l} \);

  2. ii.

    \( t + p_{k} + p_{l} - d_{l} \ge t + p_{l} + p_{k} - d_{k} \), since, \( p_{k} , d_{l} \) and \( d_{k} \) are all positive, and from our assumption that \( d_{k} \ge d_{l} \).

Case 2

\( {\hbox{max} }_{1 \le j \le i - 1} \left\{ {p_{j} } \right\} < p_{l} < p_{k} \).

Since \( p_{l} < p_{k} \), there is no idle time between the jobs in schedule \( \pi_{1} \).

Let \( t \) be the starting time of job \( k \) on machine 1 in schedule \( \pi_{1} \), and thus, the cost contribution of jobs \( k \) and \( l \) in \( \pi_{1} \) is:

$$ Z_{{\pi_{1} }} \left( {k,l} \right) = \hbox{max} \left\{ {t + m \times p_{k} - d_{k} , t + m \times p_{k} + p_{l} - d_{l} } \right\}. $$

Obtain a schedule \( \pi_{2} \) by swapping jobs \( k \) and \( l \). Since \( p_{l} < p_{k} \), there is an idle time between the jobs in schedule \( \pi_{2} \).

$$ Z_{{\pi_{2} }} \left( {k,l} \right) = \hbox{max} \left\{ {t + m \times p_{l} - d_{l} , t + p_{l} + m \times p_{k} - d_{k} } \right\}. $$

We prove that \( Z_{{\pi_{1} }} \left( {k,l} \right) \ge Z_{{\pi_{2} }} \left( {k,l} \right) \) by showing that:

$$ t + m \times p_{k} + p_{l} - d_{l} \ge \hbox{max} \left\{ {t + m \times p_{l} - d_{l} , t + p_{l} + m \times p_{k} - d_{k} } \right\}. $$

The latter is true due to:

  1. i.

    (\( i \)) \( t + m \times p_{k} + p_{l} - d_{l} \ge t + m \times p_{l} - d_{l} \), as \( p_{k} > p_{l} \);

  2. ii.

    (\( ii \)) \( t + m \times p_{k} + p_{l} - d_{l} \ge t + p_{l} + m \times p_{k} - d_{k} \), as \( d_{l} \le d_{k} \).

Case 3

\( {\hbox{max} }_{1 \le j \le i - 1} \left\{ {p_{j} } \right\} < p_{k} < p_{l} \).

Since \( p_{k} < p_{l} \) there is an idle time between the jobs in schedule \( \pi_{1} \).

Let \( t \) be the starting time of job \( k \) on machine 1 in schedule \( \pi_{1} \), and thus, the cost contribution of jobs \( k \) and \( l \) in \( \pi_{1} \) is:

$$ Z_{{\pi_{1} }} \left( {k,l} \right) = \hbox{max} \left\{ {t + m \times p_{k} - d_{k} , t + p_{k} + m \times p_{l} - d_{l} } \right\}. $$

Obtain a schedule \( \pi_{2} \) by interchanging jobs \( k \) and \( l \). Since \( p_{l} > p_{k} \), there is no idle time between the jobs, and the cost contribution of jobs \( k \) and \( l \) in \( \pi_{2} \) is:

$$ Z_{{\pi_{2} }} \left( {k,l} \right) = \hbox{max} \left\{ {t + m \times p_{l} - d_{l} , t + m \times p_{l} + p_{k} - d_{k} } \right\}. $$

We prove that \( Z_{{\pi_{1} }} \left( {k,l} \right) \ge Z_{{\pi_{2} }} \left( {k,l} \right) \) by showing that:

$$ t + p_{k} + m \times p_{l} - d_{l} \ge \hbox{max} \left\{ {t + m \times p_{l} - d_{l} , t + m \times p_{l} + p_{k} - d_{k} } \right\}. $$

The latter is true due to:

  1. i.

    (\( i \)) \( t + p_{k} + m \times p_{l} - d_{l} \ge t + m \times p_{l} - d_{l} \);

  2. ii.

    (\( ii \)) \( t + p_{k} + m \times p_{l} - d_{l} \ge t + m \times p_{l} + p_{k} - d_{k} \).

The remaining cases, i.e., Case 4: \( p_{l} < {\hbox{max} }_{1 \le j \le i - 1} \left\{ {p_{j} } \right\} < p_{k} \) and Case 5: \( p_{k} < {\hbox{max} }_{1 \le j \le i - 1} \left\{ {p_{j} } \right\} < p_{l} \) are similar to Case 2 and Case 3, respectively, and are thus omitted.

It follows that in all cases, \( \pi_{2} \) contradicts the optimality of \( \pi_{1} \), which completes the proof. □

To facilitate the DP, we use a variable \( \left( {p_{{max}} } \right)_{j} \), that holds the largest processing time of a subset \( \left( {1, \ldots ,j} \right) \) that achieves the minimal tardiness with maximum rejection cost \( e \). The variable \( \left( {p_{{max}}} \right)_{j} \) is defined as follows:

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

Let \( f\left( {j,t,e} \right) \) denote the minimal tardiness for the partial schedule of jobs \( 1, \ldots ,j \) with total processing time, \( t \), and maximum rejection cost, \( e \). Likewise to \( {\text{DP1}} \) at each iteration of the DP, the scheduling cost of jobs 1 to \( j \) having an upper bound \( e \left( {0 \le e \le E} \right) \) on the rejection cost is computed, based on the processing times and costs of jobs 1 to \( j - 1 \), with an upper bound rejection cost of either \( e \) or \( e - e_{j} \), depending on whether it is possible to reject job \( j \) (i.e., its rejection cost does not exceed the current rejection cost limit \( e \)), and whether the resulting minimum tardiness cost can only be improved by this rejection. Intuitively, variable \( t \) is used to track the total time of the processed jobs in the examined schedule.

The completion time of job \( j \) (on machine \( m \)) in the partial set \( \left( {1, \ldots ,j} \right) \), with total processing time, \( t \), is given as \( C_{j} = \left( {m - 1} \right)\left( {p_{{max}} } \right)_{j} + t \).

Next, we present the formal DP by its recursion formula.

Dynamic programming algorithm DP2

$$\begin{aligned} f\left( {j,t,e} \right) = \left\{ \begin{array}{llll} \hbox{min} \left( {\begin{array}{lll} {{ \hbox{max} }\left( {\begin{array}{lll} {f\left( {j - 1,t - p_{j} , e} \right), } \\ {\hbox{max} \left\{ {0,C_{j} - d} \right\} } \\ \end{array} } \right)} \\ {f\left( {j - 1,t,e - e_{j} } \right) } \\ \end{array} ,} \right) ,&\quad p_{j} \le t \ \ {\text{and}}\ \ e_{j} \le e \hfill \\ { \hbox{max} }\left( {\begin{array}{llll} {f\left( {j - 1,t - p_{j} , e} \right), } \\ {\hbox{max} \left\{ {0, C_{j} - d} \right\} } \\ \end{array} } \right) ,&\quad p_{j} \le t \ \ {\text{and}} \ \ e_{j} > e \hfill \\ f\left( {j - 1,t,e - e_{j} } \right) ,&\quad p_{j} > t \ \ {\text{and}} \ \ e_{j} \le e \hfill \\ \infty , &\quad p_{j} \ \ {\text{and}} \ \ e_{j} > e. \hfill \\ \end{array} \right.\end{aligned} $$
(2)

The first condition of the recursion reflects the option to accept or reject job \( j \). The second condition refers only to the option of processing job \( j \) as \( e_{j} \) exceeds the current rejection cost limit \( e \), implying that job \( j \) must be accepted. The third condition refers only to the option of rejecting job \( j \), as \( t \) is smaller than \( p_{j} \). The last line addresses invalid cases implying a cost of \( \infty \).

The boundary conditions are:

$$ \begin{aligned} f\left( {0,0,e} \right) = 0, \quad 0 \le e \le E \hfill \\ f\left( {0,t,e} \right) = \infty , \quad 0 < t \le P. \hfill \\ \end{aligned} $$

The optimal solution is given by \( {\hbox{min} }_{0 \le t \le P, 0 \le e \le E} \left\{ {f\left( {n,t,e} \right)} \right\} \)

Theorem 2

The computational complexity of\( DP2 \)is\( O\left( {nPE} \right) \).

Proof

Using the recursive function in (2), the DP is calculated for every job \( j, 1 \le j \le n \), for every \( t, 1 \le t \le P \), and every rejection cost \( e \le U \), resulting in an \( O\left( {nPE} \right) \) processing time. Reconstructing the solution is done by backtracking, finding the minimum cost, \( f\left( {n,t,e} \right), \) in \( O\left( {PE} \right) \) time, and starting at the found minimum and ending at \( f\left( {0,0,0} \right) \), for an addition of \( O\left( {n + P + U} \right) \) operations. We conclude that the total processing time is \( O\left( {nPE} \right) \). □

Example 2

Consider the following instance of the problem, \( m = 4, n = 6,E = 27 \), and jobs with due-dates \( d = \left( {38, 57, 76, 90, 118, 123} \right) \), sequenced in EDD order, and renumbered.

The processing times are \( p = \left( {18, 34, 18, 17, 8, 44} \right) \).

The job-dependent rejection costs are \( e = \left( {3, 31, 8, 31, 25, 46} \right) \).

Executing DP2, we obtain that in an optimal solution, the set of accepted jobs is \( A = \left( {2, 4, 5, 6} \right) \). The tardiness of the jobs is \( T_{2} = 79, T_{4} = 63, T_{5} = 43, T_{6} = 112 \), implying that \( T_{{max}} = 112 \).

The set of rejected jobs is \( \bar{A} = \left( {1, 3} \right) \) and \( \sum \nolimits_{{j \in \bar{A}}} e_{j} = 11 \le 27 = E \).

Numerical study We performed numerical experiments to measure the running times of \( DP2 \). For \( m = 4 \), we generated random instances having \( n = 25, 50, 75,100 \) and \( 125 \) jobs. The job-processing times and the job-rejection costs were generated uniformly in the interval \( \left[ {1, 50} \right] \). For each instance, the maximal makespan was calculated: \( \overline{{C_{max} }} = \left( {m - 1} \right){\hbox{max} }_{1 \le j \le n} \left\{ {p_{j} } \right\} + \sum \nolimits_{j = 1}^{n} p_{j} \). The job due-dates were generated uniformly in the interval \( \left[ {0.10, 0. 50} \right]\overline{{C_{max} }} \). Similar to Sect. 3, \( \bar{e} = 50 \), and the total rejection upper bound cost, \( E \), was generated uniformly in the intervals \( \left[ {0.005, 0.010} \right]n\bar{e},\left[ {0.015, 0.020} \right]n\bar{e} \) and \( \left[ {0.025, 0.030} \right]n\bar{e} \), reflecting rejection of approximately 10%, 15%, and 20% jobs, respectively. The rest of the scheme is identical to that given in Sect. 3. The results are presented in Table 2 and demonstrate the efficiency of DP2 to solve real-life instances. We note that the worst-case running time for problems of 125 jobs and 20% rejection rate did not exceed 0.646 seconds (s).

Table 2 Average- and worst-case running times of DP2 algorithm for Problem P2
Full size table

5 Problem \( P3:F_{\text{m}} /p_{ij} = p_{j} , d_{j} = d,{\text{rej}},\sum \nolimits_{{ j \in \bar{A}}} e_{j} \le E/ \sum \nolimits_{ j \in A} T_{j} \)

To the best of our knowledge, the problem, \( F_{m} /p_{ij} = p_{j} , d_{j} = d/\sum T_{j} \), was not addressed in scheduling theory to date. Recall that the SPT rule is optimal for \( 1/d_{j} = d/\sum T_{j} \). We start by proving that the SPT order is optimal for \( Fm/p_{ij} = p_{j} , d_{j} = d/\sum T_{j} \) as well.

Property 2

There exists an optimal schedule for \( Fm/p_{ij} = p_{j} , d_{j} = d/\sum T_{j} \) in which the jobs are sequenced in SPT order.

Proof

By a pair-wise interchange argument.

Consider an optimal schedule \( \pi_{1} \), where the tardy jobs are not SPT. As above, let \( k \) (at position \( i \)) and \( l \) (at position \(i + 1\)) denote the first pair of consecutive jobs that violates the SPT order, that is \( p_{l} < p_{k} \). Let \( T_{j} \left( {\pi_{1} } \right) \) and \( P_{i - 1} \left( {\pi_{1} } \right) \) denote the tardiness value of job \( j \) and the total processing time of jobs at positions \( 1, \ldots ,i - 1 \), i.e., \( P_{i - 1} = \sum \nolimits_{j = 1}^{i - 1} p_{j} \), in schedule \( \pi_{1} \):

$$ \begin{aligned} T_{k} \left( {\pi_{1} } \right) + T_{l} \left( {\pi_{1} } \right) & = C_{k} - d + C_{l} - d \\ & = \left[ {\left( {P_{i - 1} \left( {\pi_{1} } \right) + p_{k} + \left( {m - 1} \right)\hbox{max} \left\{ {\mathop {\hbox{max} }\limits_{1 \le j \le i - 1} \left\{ {p_{j} } \right\},p_{k} } \right\}} \right) - d} \right] \\ &\qquad + \left[ {\left( {P_{i - 1} \left( {\pi_{1} } \right) + p_{k} + p_{l} + \left( {m - 1} \right)\mathop {\hbox{max} }\limits_{1 \le j \le i + 1} \left\{ {p_{j} } \right\}} \right) - d} \right]. \\ \end{aligned} $$

Obtain a schedule \( \pi_{2} \) by a standard pair-wise interchange of jobs \( k \) and \( l \).

It follows that:

$$ \begin{aligned} & T_{k} \left( {\pi_{1} } \right) + T_{l} \left( {\pi_{1} } \right) - \left( {T_{l} \left( {\pi_{2} } \right) + T_{k} \left( {\pi_{2} } \right)} \right) \\ & \quad = p_{k} - p_{l} + \left( {m - 1} \right)\left[ {\hbox{max} \left\{ {\mathop {\hbox{max} }\limits_{1 \le j \le i - 1} \left\{ {p_{j} } \right\},p_{k} } \right\} - \hbox{max} \left\{ {\mathop {\hbox{max} }\limits_{1 \le j \le i - 1} \left\{ {p_{j} } \right\},p_{l} } \right\}} \right] > 0. \\ \end{aligned} $$

We conclude that \( \pi_{2} \) is optimal as well, which completes the proof. □

We conclude from Property 2 that \( \left( {p_{max} } \right)_{j} = p_{j} \).

Let \( f\left( {j,t,e} \right) \) denote the minimal total tardiness for the partial schedule of jobs \( 1, \ldots ,j \), having total processing time \( t \) and maximum rejection cost \( e \).

The dynamic programming for \( f\left( {j,t,e} \right) \) is as follows:

Dynamic programming algorithm DP3:

$$\begin{aligned} & f\left( {j,t,e} \right) = \hfill \\ & \left\{ \begin{array}{lllll} \hbox{min} \left( {\begin{array}{llll} {f\left( {j - 1,t - p_{j} , e} \right) + \hbox{max} \left\{ {0, \left( {m - 1} \right)p_{j} + t - d} \right\}} \\ {f\left( {j - 1,t,e - e_{j} } \right) } \\ \end{array},} \right) , &\quad p_{j} \le t \ \ {\text{and}} \ \ e_{j} \le e \hfill \\ f\left( {j - 1,t - p_{j} , e} \right) + \hbox{max} \left\{ {0, \left( {m - 1} \right)p_{j} + t - d} \right\} , &\quad p_{j} \le t \ \ {\text{and}} \ \ e_{j} > e \hfill \\ f\left( {j - 1,t,e - e_{j} } \right) , &\quad p_{j} > t \ \ {\text{and}} \ \ e_{j} \le e \hfill \\ \infty , &\quad p_{j} > t \ \ {\text{and}} \ \ e_{j} > e. \hfill \\ \end{array} \right. \hfill \\ \end{aligned} $$

The first line of the recursion reflects the option to accept or reject job \( j \). The second line refers to the option of production of job \( j \) only and the third line refers to the option of rejection of job \( j \) only. The last line addresses unacceptable cases implying a cost of \( \infty \).

The boundary conditions are:

$$ \begin{aligned} f\left( {0,0,e} \right) = 0, 0 \le e \le E \hfill \\ f\left( {0,t,e} \right) = \infty , 0 < t \le P. \hfill \\ \end{aligned} $$

The optimal solution is given by \( {\hbox{min} }_{0 \le t \le P, 0 \le e \le E} \left\{ {f\left( {n,t,e} \right)} \right\} \)

Theorem 3

The computational complexity of\( DP3 \)is\( O\left( {nPE} \right) \).

(The proof is similar to that given for DP2 in Sect. 4.)

Example 3

Consider the following instance of the problem, \( m = 4,n = 6, E = 28, d = 16 \), and the jobs are sequenced in SPT order and renumbered.

The processing times are \( p = \left( {10, 10, 21, 37, 39, 43} \right) \).

The job-dependent rejection costs are \( e = \left( {32, 8, 23, 32, 18, 48} \right) \).

Applying \( DP3 \), the set of accepted jobs is \( A = \left( {1, 3, 4, 6} \right) \).

The tardiness of the accepted jobs is \( T_{1} = 24, T_{3} = 78, T_{4} = 163, T_{6} = 224 \), achieving \( \sum \nolimits_{ j \in A} T_{j} = 489 \).

The set of rejected jobs is \( \bar{A} = \left( {2, 5} \right) \) and \( \sum \nolimits_{{j \in \bar{A}}} e_{j} = 26 \le 28 = E \).

Numerical study We adapted the arrangement depicted in Sect. 4, except that the common due-date was generated uniformly in the interval \( \left[ {0.10, 0. 50} \right]\overline{{C_{{max}} }} \). The results presented in Table 3 reflect the ability of \( DP3 \) to solve real-life instances, especially as the worst-case running time for problems of 125 jobs and 20% rejection rate did not exceed 0.481 s.

Table 3 Average- and worst-case running times of DP3 algorithm for Problem P3
Full size table

6 Problem \( P4:F_{\text{m}} /p_{ij} = p_{j} , d_{j} = d,{\text{rej}}, \sum \nolimits_{{ j \in \bar{A}}} e_{j} \le E/ \sum \nolimits_{ j \in A} w_{j} U_{j} \)

It is well known that the classical problem \( 1/d_{j} = d/\sum w_{j} U_{j} \) is equivalent to the knapsack problem. Solving \( 1/d_{j} = d/\sum w_{j} U_{j} \), similarly to knapsack, does not require an initial sequencing of the jobs prior to executing the DP. Unlike the single machine setting, in the PFS setting, the scheduler has to consider the inherent idle times between consecutive jobs and, subsequently, keep track of the longest job in the subset of accepted jobs, \( \left( {p_{{max}} } \right)_{j} \). To simplify the DP and avoid excessive variables, we start by sequencing the jobs in accordance to the SPT rule. From Property 2 in Sect. 5, this step guarantees that \( \left( {p_{max} } \right)_{j} = p_{j} \). Let \( f\left( {j,t,e} \right) \) denote the minimal total weighted number of tardy jobs for the partial schedule of jobs \( 1, \ldots ,j \), having processing time \( t \) and maximum rejection cost \( e \). At each iteration of the DP, the scheduling cost of jobs 1 to \( j \), having an upper bound \( e \left( {0 \le e \le E} \right) \) on the rejection cost is computed, based on the processing costs of jobs 1 to \( j - 1 \), with an upper bound rejection cost of either \( e \) or \( e - e_{j} \).

From the above, the tardiness unit penalty of job \( j \) can be determined by the following updated definition:

$$ U_{j} = \left\{ {\begin{array}{lll} {1, T_{j} = t + \left( {m - 1} \right)p_{j} - d > 0} \\ {0, otherwise} \\ \end{array} } \right.. $$

Dynamic programming algorithm DP4:

$$\begin{aligned} f\left( {j,t,e} \right) = \left\{ \begin{array}{llll} \hbox{min} \left( {\begin{array}{lll} {f\left( {j - 1,t - p_{j} , e} \right) + w_{j} U_{j } ,} \\ {f\left( {j - 1,t,e - e_{j} } \right) } \\ \end{array} } \right) , &\quad p_{j} \le t \ \ {\text{and}} \ \ e_{j} \le e \hfill \\ f\left( {j - 1,t - p_{j} , e} \right) + w_{j} U_{j} , &\quad p_{j} \le t \ \ {\text{and }}\ \ e_{j} > e \hfill \\ f\left( {j - 1,t,e - e_{j} } \right) , &\quad p_{j} > t \ \ {\text{and}} \ \ e_{j} \le e \hfill \\ \infty , &\quad p_{j} > t \ \ {\text{and}} \ \ e_{j} > e \hfill \\ \end{array} \right..\end{aligned} $$

As for DP3, the first condition of the recursion reflects the option to accept or reject job \( j \). The second condition refers to the option of acceptation only, whereas the third condition refers to the option of rejection only. The last line addresses illegal cases implying a cost of \( \infty \).

The boundary conditions are:

$$ \begin{aligned} f\left( {0,0,e} \right) = 0, \quad 0 \le e \le E \hfill \\ f\left( {0,t,e} \right) = \infty , \quad 0 < t \le P. \hfill \\ \end{aligned} $$

The optimal solution is given by \( \mathop {\hbox{min} }\nolimits_{0 \le t \le P, 0 \le e \le E} \left\{ {f\left( {n,t,e} \right)} \right\}. \)

Theorem 4

The computational complexity of \( DP4 \) is \( O\left( {nPE} \right) \).

(The proof is similar to that given for DP2 in Sect. 4.)

Example 4

Consider the following instance of the problem, \( m = 4,n = 6, E = 33, d = 22 \) and the jobs are sequenced in SPT order and renumbered.

The processing times are \( p = \left( {31, 31, 37, 40, 44, 45} \right) \).

The job-dependent rejection costs are \( e = \left( {42, 43, 21, 25, 31, 6} \right) \).

The job-dependent weights are \( w = \left( {20, 7, 10, 11, 24, 20} \right) \).

Executing \( DP4 \), we obtain that in an optimal solution, the set of accepted jobs is \( A = \left( {1, 2, 3, 5} \right) \), obtaining total weighted number of tardy jobs of \( \sum \nolimits_{ j \in A} w_{j} U_{j} = 61 \).

The set of rejected jobs is \( \bar{A} = \left( {4, 6} \right) \) and \( \sum \nolimits_{{j \in \bar{A}}} e_{j} = 31 \le 33 = E \).


Numerical study We adapted the scheme presented in Sect. 5, with the addition of job-dependent weights that were generated uniformly in the interval \( \left[ {1, 25} \right] \). The results presented in Table 4 validate the efficiency of \( DP4 \) to solve real-life instances. Specifically, the worst-case running time for problems of 125 and 20% rejection rate jobs did not exceed 0.468 s.

Table 4 Average- and worst-case running times of DP4 algorithm for Problem P4
Full size table

7 Conclusions

In this study, we combined the method of job rejection and the setting of proportionate flowshop, and focused on minimizing regular performance measures, subject to the constraint that the total rejection cost cannot exceed a given upper bound. In particular, we considered the problems of total completion time, maximum tardiness, total tardiness, and total weighted number of tardy jobs. For each problem, we introduced an efficient pseudo-polynomial dynamic programming solution algorithm. We also conducted extensive numerical studies that demonstrate the DPs ability to solve real-life instances. Challenging future objective functions in the setting of proportionate flowshop with rejection, include, among others, makespan with release dates, total weighted tardiness with a common due-date, and total tardiness. These problems will probably necessitate a different approach, such as applying advanced metaheuristic techniques.