Exact algorithms and approximation schemes for proportionate flow shop scheduling with step-deteriorating processing times

We study two scheduling problems in a proportionate flow shop environment, where job processing times are machine independent. In contrast to classical proportionate flow shop models, we assume (in both problems) that processing times are step-deteriorating. Accordingly, each job \(J_{j}\) has a normal processing time, \(a_{j}\), if it starts to be processed in the shop no later than its deteriorating date, \(\delta _{j}\). Otherwise, the job’s processing time increases by \(b_{j}\) (the job’s deterioration penalty). Our aim is to find a job schedule that minimizes either the makespan or the total load. These two problems are known to be \(\mathcal{N}\mathcal{P}\)-hard for the special case of a single machine, even when all jobs have the same deteriorating date. In this paper, we derive several positive results in relation to the two problems. We first show that the two problems can be represented in a unified way. We then prove that the unified problem is only ordinary \( \mathcal{N}\mathcal{P}\)-hard by providing a pseudo-polynomial time algorithm for its solution. We also show that the pseudo-polynomial time algorithm can be converted into a fully polynomial time approximation scheme (FPTAS). Finally, we analyze the parameterized complexity of the problem with respect to the number of different deteriorating dates in the instance, \(v_{\delta }\) . We show that although the problem is \(\mathcal{N}\mathcal{P}\)-hard when \(v_{\delta }=1\), it is fixed parameterized tractable (FPT) for the combined parameters (i) \((\nu _{\delta },\nu _{a})\) and (ii) \((\nu _{\delta },\nu _{b})\), where \(\nu _{a}\) is the number of different normal processing times in the instance, and \(\nu _{b}\) is the number of different deterioration penalties in the instance.

Authors and Affiliations

1. Department of Industrial Engineering and Management, Ben-Gurion University of the Negev, Beer-Sheva, Israel

   Dvir Shabtay

2. The Department of Economics and Business Administration, Ariel University, Ariel, Israel

   Baruch Mor

Corresponding author

Correspondence to Dvir Shabtay.

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Appendix 1: Numerical example for Algorithm 1

Below, we illustrate the technical implementation of Algorithm 1 on a numerical example that includes five jobs with the job parameters as given in Table 1. In addition, we set \(\alpha =2\) and \(h=4\).

• [Initialization]:

  • The \(l_{j}\) values for \( j=1,\ldots ,5\) appears in Table 2, from which it can also be seen that \(A_{\Sigma }=30\).

We set \(\mathcal {L}_{0}(4)\)\(=\{[Z_{h}(0,\emptyset )=\alpha l_{h}+A_{\Sigma }=50,a_{\Sigma }=0,\mathcal {E}(0)=\emptyset ]\},\) \( \mathcal {L}_{l}\)\(=\emptyset \) for \(l=1,\ldots ,n\), and \(j=1\).

• [Feasibility Check]:

  • There is no job \(J_{j}\in J\) with \( a_{j}>l_{h}=l_{4}=10\).

• [Sorting]:

  • The jobs are already numbered in an EEDD order.

[First Iteration of Construction and Elimination \( (j=1)\)]:

• From state \([Z_{4}(0,\emptyset )=50,a_{\Sigma }=0,\mathcal {E} (0)=\emptyset ]\in \mathcal {L}_{0}(4):\)

  • Since \(a_{\Sigma }=0<\delta _{1}=6\) and \(j=1\ne h=4,\) we construct state \([50,5,\{J_{1}\}]\) in \(\mathcal {L}_{1}(4)\).

  • Since \(l_{1}=8\le l_{4}=10,\) we include state \([53,0,\emptyset ]\) in \( \mathcal {L}_{1}(4).\)

• Since each of the states in \(\mathcal {L}_{1}(4)\) has a different \( a_{\Sigma }\) value, none of them is eliminated. Concluding iteration 1, we have

  $$\begin{aligned} \mathcal {L}_{1}(4)=\{[50,5,\{J_{1}\}],[53,0,\emptyset ]\}. \end{aligned}$$

[Second Iteration of Constructionand Elimination \((j=2)\)]:

• From state \([50,5,\{J_{1}\}]\in \mathcal {L}_{1}(4)\):

  • Since \(a_{\Sigma }=5<\delta _{2}=10\) and \(2\ne 4,\) we construct state \([50,8,\{J_{1},J_{2}\}]\) in \(\mathcal {L}_{2}(4)\).

  • Since \(l_{2}=8\le l_{4}=10,\) we include state \([55,5,\{J_{1}\}]\) in \( \mathcal {L}_{2}(4).\)

• From state \([53,0,\emptyset ]\in \mathcal {L}_{1}(4)\):

  • Since \(a_{\Sigma }=0<\delta _{2}=10\) and \(2\ne 4,\) we construct state \([53,3,\{J_{2}\}]\) in \(\mathcal {L}_{2}(4)\).

  • Since \(l_{2}=8\le l_{4}=10,\) we include state \([58,0,\emptyset ]\) in \( \mathcal {L}_{2}(4).\)

  • Since each of the states in \(\mathcal {L}_{2}(4)\) has a different \( a_{\Sigma }\) value, none of them is eliminated. Concluding iteration 2, we have

    $$\begin{aligned}{} & {} \mathcal {L}_{2}(4)=\{[50,8,\{J_{1},J_{2}\}],[55,5,\{J_{1}\}],\\{} & {} \quad [53,3,\{J_{2} \}],[58,0,\emptyset ]\}. \end{aligned}$$

[Third Iteration of Construction and Elimination \( (j=3)\)]:

• From state \([50,8,\{J_{1},J_{2}\}]\in \mathcal {L}_{2}(4)\):

  • Since \(a_{\Sigma }=8>\delta _{3}=7,\) we cannot include \(J_{3}\) in the set of early jobs.

  • Since \(l_{3}=10\le l_{4}=10,\) we include state \([52,8,\{J_{1},J_{2} \}] \) in \(\mathcal {L}_{3}(4).\)

• From state \([55,5,\{J_{1}\}]\in \mathcal {L}_{2}(4)\):

  • Since \(a_{\Sigma }=5<\delta _{3}=7\) and \(3\ne 4,\) we construct state \( [55,13,\{J_{1},J_{3}\}]\) in \(\mathcal {L}_{3}(4)\).

  • Since \(l_{3}=10\le l_{4}=10,\) we include state \([57,5,\{J_{1}\}]\) in \( \mathcal {L}_{3}(4).\)

• From state \([53,3,\{J_{2}\}]\in \mathcal {L}_{2}(4)\):

  • Since \(a_{\Sigma }=3<\delta _{3}=7\) and \(3\ne 4,\) we construct state \( [53,11,\{J_{2},J_{3}\}]\) in \(\mathcal {L}_{3}(4)\).

  • Since \(l_{3}=10\le l_{4}=10,\) we include state \([55,3,\{J_{2}\}]\) in \( \mathcal {L}_{3}(4).\)

• From state \([58,0,\emptyset ]\in \mathcal {L}_{2}(4)\):

  • Since \(a_{\Sigma }=0<\delta _{3}=7\) and \(3\ne 4,\) we construct state \( [58,8,\{J_{3}\}]\) in \(\mathcal {L}_{3}(4)\).

  • Since \(l_{3}=10\le l_{4}=10,\) we include state \([60,0,\emptyset ]\) in \(\mathcal {L}_{3}(4).\)

• In Elimination, we eliminate \([58,8,\{J_{3}\}]\) , as it is dominated by \([52,8,\{J_{1},J_{2}\}]\). Concluding iteration 3, we have

  $$\begin{aligned} \mathcal {L}_{3}(4)= & {} \{[52,8,\{J_{1},J_{2}\}],[55,13,\{J_{1},J_{3}\}],\\{} & {} \quad [57,5,\{J_{1}\}],[53,11, \{J_{2},J_{3}\}], \\{} & {} [55,3,\{J_{2}\}],[60,0,\emptyset ]\}. \end{aligned}$$

[Forth Iteration of Construction and Elimination \( (j=4)\)]:

• As \(j=h=4\), we have to include \(J_{4}\) in \(\mathcal {T}\). Accordingly, we construct in \(\mathcal {L}_{4}(4)\):

  • state \([57,8,\{J_{1},J_{2}\}]\) out of state \([52,8,\{J_{1},J_{2}\}]\in \mathcal {L}_{3}(4)\);

  • state \([60,13,\{J_{1},J_{3}\}]\) out of state \([55,13,\{J_{1},J_{3}\}] \in \mathcal {L}_{3}(4)\);

  • state \([62,5,\{J_{1}\}]\) out of state \([57,5,\{J_{1}\}]\in \mathcal {L} _{3}(4)\);

  • state \([58,11,\{J_{2},J_{3}\}]\) out of state \([53,11,\{J_{2},J_{3}\}] \in \mathcal {L}_{3}(4)\);

  • state \([60,3,\{J_{2}\}]\) out of state \([55,3,\{J_{2}\}]\in \mathcal {L} _{3}(4)\); and

  • state \([65,0,\emptyset ]\) out of state \([60,0,\emptyset ]\in \mathcal {L }_{3}(4)\).

• Concluding iteration 4 (there is no elimination of states), we have

  $$\begin{aligned} \mathcal {L}_{4}(4)= & {} \{[57,8,\{J_{1},J_{2}\}],[60,13,\{J_{1},J_{3}\}],\\{} & {} [62,5,\{J_{1}\}],[58,11, \{J_{2},J_{3}\}], \\{} & {} [60,3,\{J_{2}\}],[65,0,\emptyset ]\}. \end{aligned}$$

[Fifth Iteration of Construction and Elimination \( (j=5)\)]:

• As \(l_{5}=14>l_{4}=10\), we cannot include \(J_{5}\) in \(\mathcal {T}\). Moreover, we include jobs in \(\mathcal {E}\) only from states in \(\mathcal {L} _{4}(4)\) with \(a_{\Sigma }\le \delta _{5}=11.\) Accordingly, we include in \( \mathcal {L}_{5}(4)\):

  • state \([57,17,\{J_{1},J_{2},J_{5}\}]\) out of state \( [57,8,\{J_{1},J_{2}\}]\in \mathcal {L}_{4}(4)\);

  • state \([62,14,\{J_{1},J_{5}\}]\) out of state \([62,5,\{J_{1}\}]\in \mathcal {L}_{4}(4)\);

  • state \([58,20,\{J_{2},J_{3},J_{5}\}]\) out of state \( [58,11,\{J_{2},J_{3}\}]\in \mathcal {L}_{4}(4)\);

  • state \([60,12,\{J_{2},J_{5}\}\}]\) out of state \([60,3,\{J_{2}\}]\in \mathcal {L}_{4}(4)\); and

  • state \([65,9,\{J_{5}\}]\) out of state \([65,0,\emptyset ]\in \mathcal {L} _{4}(4)\).

• Concluding iteration 5 (there is no elimination of states), we have

  $$\begin{aligned} \mathcal {L}_{5}(4)= & {} \{[57,17,\{J_{1},J_{2},J_{5}\}],[62,14,\{J_{1},J_{5}\}],\\{} & {} \quad [58,20, \{J_{2},J_{3},J_{5}\}], \\{} & {} [60,12,\{J_{2},J_{5}\}\}],[65,9,\{J_{5}\}]\}. \end{aligned}$$

[Result:

]: The optimal state is \( [57,17,\{J_{1},J_{2},J_{5}\}]\). Therefore, \(\mathcal {E}_{4}^{*}=\{J_{1},J_{2},J_{5}\}\), \(\mathcal {T}_{4}^{*}=\{J_{3},J_{4}\}\), and the optimal permutation schedule is either \(\{J_{1},J_{2},J_{5},J_{3},J_{4}\}\) or \(\{J_{1},J_{2},J_{5},J_{4},J_{3}\}\).

Appendix 2: Illustration of the formulation \({\Lambda } ^{\prime }{(h)}\)

We illustrate the proposed formulation via a numerical example that includes \(n=6\) jobs, with \(\alpha =2\) and \(h=3\). The job parameters are given in Table 3.

The parameter at hand, k, is the number of sets with a unique combination of deteriorating date and normal processing time, and \(\mathcal {J}_{i}\) (\( i=1,\ldots ,k\)) is the set of all jobs in \(\mathcal {S}\) that have the same values of deteriorating date and normal processing time. In our example, \( k=3,\) and

We re-index and sort the jobs in each \(\mathcal {J}_{i}= \{J_{i1},\ldots ,J_{in_{i}}\}\) (\(n_{i}=\vert \mathcal {J}_{i} \vert \)) such that \(b_{i1}\ge b_{i2}\ge \cdots \ge b_{in_{i}}\) for \(i=1,\ldots ,k\). We also let \(a_{i}\) and \(\delta _{i}\) be the common normal processing time and deteriorating date of all jobs in \(\mathcal {J}_{i}\); i.e., \( a_{i}=a_{i1}=a_{i2}=\cdots =a_{in_{i}}\) and \(\delta _{i}=\delta _{i1}=\delta _{i2}=\cdots =\delta _{in_{i}}\). Accordingly, after the re-indexing and sorting operations, the instance is as shown in Table 4.

Based on (26), we have

We next derive the formulation \(\Lambda ^{\prime }(h)\) corresponding to this example. According to (27), we include the following set of constraints

According to (28), we include the following set of constraints:

According to (31), we include the following set of constraints:

Based on (30), the objective value of the h-auxiliary problem as a function of the decision variables is given by

Appendix 3: Illustration of the ILP formulation \({\Pi (h)}\)

We illustrate the proposed MILP formulation \(\Pi (h)\) via numerical example that includes \(n=10\) jobs, with \(\alpha =2\) and \(h=7\). The job parameters are as given in Table 5.

We begin by calculating the \(l_{j}\) values for \(j=1,\ldots ,10\). The results appear in Table 6. It follows that

and that

The notation, \(\mathcal {S}_{i}\) is used to represent the set of jobs in \( \mathcal {S}\) that all have the same values of deteriorating date and deterioration penalty. In our example, we have

In addition, \(\mathcal {R}_{j}\) for \(j=1,\ldots ,m\) is the set of jobs in \( \mathcal {J}^{\prime }\) that have the same normal processing time and deteriorating date, \(a_{j}\) and \(\delta _{j}\), respectively:

Therefore, \(m=6\). The non-empty sets \(\mathcal{S}\mathcal{R}_{ij}\) are:

and the non-empty \(\mathcal{L}\mathcal{R}_{j}\) sets are:

To varify that the corresponding instance of the h-auxilary problem has a feasible solution, we have to check the set of conditions in (34). The condition in (34) is redundant for \(l=1,\ldots ,4\), as \(\mathcal{L}\mathcal{R} _{l}=\emptyset \). For \(l=5\), we need to verify that

and for \(l=6\) we need to verify that

As both conditions holds, we have a feasible solution for the corresponding h-auxilary problem. Now, based on (38), the objective is to minimize

According to (35), the first set of constraints is

According to (36), the second set of constraints is

According to (37), the third set of constraints is

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions