Two-stage, single-lot, lot streaming problem for a \(1+2\) hybrid flow shop

In this paper, we address a single-lot, lot streaming problem for a two-stage hybrid flow shop, which consists of one machine at Stage 1 and two parallel (identical) machines at Stage 2. The objective is to minimize makespan. The lot is to be split into sublots each of which is processed first on the machine at Stage 1, and then, on one of the machines at Stage 2. A sublot-attached removal time is incurred after processing each sublot at Stage 1. First, we assume the number of sublots for the lot to be known a priori and develop closed-form expressions to obtain optimal, continuous sublot sizes for this case. Then, we consider determination of an optimal number of sublots in addition to their sizes. We develop an upper bound on the number of sublots, \(N_{\text {pos}}\), and use an algorithm of \(O(N_{\text {pos}})\) complexity in conjunction with the closed-form expressions for sublot sizes to obtain an optimal solution. We also address the problem of determining number of sublots and integer sublot sizes, and propose a heuristic method for its solution that relies on some key results from the continuous case of the problem. The results of our numerical experimentation reveal the efficacy of the proposed method to obtain near-optimal integer sublot sizes and makespan values that are within 2.35 % of the true optimum for the testbed of data used, each obtained within a few seconds of CPU time.

1. In order not to distract the reader, we present the proof of Proposition 2 and those of Corollaries 2 and 3, in “Appendix 1”.

2. A sublot is said to be critical if it does not have to wait for processing on a machine at any stage during its flow through the system.

Authors and Affiliations

1. School of Urban Rail Transportation, Soochow University, Suzhou, 215137, China

   Ming Cheng

2. Grado Department of Industrial and Systems Engineering, Virginia Tech, Blacksburg, VA, 24061, USA

   Subhash C. Sarin & Sanchit Singh

Corresponding author

Correspondence to Subhash C. Sarin.

Appendix 1

Proposition 2

For a given number of sublots, n, and presence of a sublot-attached removal time at Stage 1 for each sublot, the optimal continuous sublot sizes can be obtained by the following expressions, if the sizes of all the sublots are greater than zero.

Proof

We prove the result by induction.

Clearly, for \(n=1\), \(s_{1}^{\prime *}=U\). When \(n=2\), the solution obtained by using the above equations is: \(s_{1}^{\prime *}=\frac{pU-t}{2p+1}\), \(s_{2}^{\prime *}=\frac{(p+1)U+t}{2p+1}\), with makespan,

Suppose the solution is not optimal. Let the optimal solution be obtained for \(\hat{s}_{1}^{\prime }=\frac{pU-t}{2p+1}-x\) and \(\hat{s}_{2}^{\prime }=\frac{(p+1)U+t}{2p+1}+x,\; x\ne 0\). We have makespan,

If \(x>0\), \(M_C^{\prime }=\frac{\left( p+1\right) ^{2}U+3pt+2t}{2p+1}+\left( p+1\right) x>M_C\), and if \(x<0\), \(M_C^{\prime }=\frac{\left( p+1\right) ^{2}U+3pt+2t}{2p+1}-px>M_C\). Therefore, \(s_{1}^{\prime *}=\frac{pU-t}{2p+1}\), \(s_{2}^{\prime *}=\frac{(p+1)U+t}{2p+1}\) is the optimal solution when \(n=2\).

Now suppose the sublot sizes given by (32)–(34) are optimal for number of sublots, \(n=2,\ldots ,k\). We want to show that it holds true for \(n=k+1\) as well. But first, we make the following observation, given that the sublot sizes obtained by using (32)–(34) are optimal for \(n=2,\ldots ,k\):

If we change the lot size by \(x\), but keep the number of sublots \(n\), \(n=1,\ldots ,k\), to be the same, then the optimal sublot sizes obtained using (32)–(34), increase or decrease in accordance with the sign of \(x\). This essentially follows from the fact that sublot sizes \({s_i}^{\prime }, \forall i=1\ldots ,n\), are directly proportional to \(x\). Consider the following:

• For the case when \(p\ne 2\), \(s_1^{\prime }\) is given by (22). Note that, \(A\) is positive, and both \(A\) and \(B\) do not depend upon the size of the lot; they only depend on \(n\). Therefore, \(s_1^{\prime }\) changes by \(\frac{x}{A}\). When \(p=2\), \(s_1^{\prime }\) is given by (26). Let \(A^{\prime }\) be the denominator of the expression in (26). Note that \(A^{\prime }\) is positive. By the same argument as above, \(s_1^{\prime }\) changes by \(\frac{x}{A^{\prime }}\).

• \(s_2^{\prime }\) is given by (32), whether or not \(p=2\). Therefore, for \(p\ne 2\), \(s_2^{\prime }\) changes by \(\frac{x}{A}(1+\frac{1}{p})\), and for \(p=2\), by \(\frac{x}{A^{\prime }}(1+\frac{1}{p})\).

• \(s_i^{\prime }, \forall i=3,\ldots ,n\), are given by (33), whether or not \(p=2\), and are directly proportional to the sizes of the previous two sublots, which via recursive argument are directly proportional to \(x\).

Next, we prove the induction step by contradiction. We use the symbol “ \(\hat{}\) ” over the standard notations used so far to represent parameters and variables for the claimed optimal schedule with \(k+1\) sublots. If \(s_{k+1}^{\prime }=\frac{s_{k}^{\prime }+s_{k-1}^{\prime }}{p}+\frac{2t}{p}\) is not optimal, let \(\hat{s}_{k+1}^{\prime }=s_{k+1}^{\prime }+x\), \(\left( x\ne 0\right) \) be optimal. We have the following two cases:

Case 1 \(x<0\). (see Fig. 4) Once we have fixed the size of sublot \(k+1\), the leftover lot size is \(U-\hat{s}_{k+1}^{\prime }\), which we denote by \(\hat{U}_k\). The optimal makespan for a lot of size \(U\) available at time \(T=0\), and split into \(k+1\) sublots is the same as the optimal makespan value for a lot of size \(\hat{U}_k\), to be split into \(k\) sublots and available at time \(T=s_{k+1}^{\prime }+x+t\) (having fixed the size of sublot \(k+1\) as \(\hat{s}_{k+1}^{\prime }\)). The solution to the latter can be obtained based on the induction step, i.e., \(\hat{s}_{i}^{\prime },\forall i=k\ldots ,1\) are given by Proposition 2 (with \(U\) replaced by \(\hat{U}_k\)), provided there is no overlap at Stage 2 machines between sublot \(k+1\) (already fixed in size), and a subsequent sublot, obtained using Proposition 2. Let \({\delta }_1\) be the gap between the completion time of sublot \(k+1\) and the start time of sublot \(k-1\) at Stage 2 (see Fig. 4ii). We show that \({\delta }_1>0\). We have,

Since \(x<0\), we have, \(\hat{U}_k>{U}_k\), and based on the above observation, we have, \(\hat{s}_{i}^{\prime }>s_{i}^{\prime },\forall i=k\ldots ,1\). Hence,

Next, we show that the change in makespan value, \(\delta _{M}\) (shown in Fig. 4ii), is positive. Since the completion time of all the sublots at Stage 1 is the same being equal to \(U+kt\) for both the cases (see Fig. 4i, ii), a change in the makespan value is given by the differences in the size of sublot 1. We have,

Case 2 \(x>0\). Apart from fixing the size of sublot \(k+1\), we also fix the size of sublot \(k\) as \(\hat{s}_{k}^{\prime }={s}_{k}^{\prime }-y\). Depending upon the value of \(y\), we have two sub-cases.

Proof of Proposition 2, Case 1: a schedule where \(\hat{s}_{k+1}^{\prime }=s_{k+1}^{\prime }+x,x<0\)

Full size image

Case 2.1 \(x>0, y\le x\). Note that the makespan is composed of the idle time and total processing times on the machines at Stage 2. However, the latter is constant for all the schedules on the machines at Stage 2. Hence, we only need to show that the total idle time on the machines at Stage 2 for the claimed optimal schedule in this sub-case (Fig. 5ii) has increased compared with that for the schedule with \(k+1\) sublots obtained entirely by Proposition 2 (Fig. 5i). Let \(\hat{I}_{1}^{\prime }\) and \(\hat{I}_{2}^{\prime }\) be the total idle times encountered on machines 1 and 2, respectively, at Stage 2 for the schedule in Fig. 5ii, and \({I}_{1}^{\prime }\) and \({I}_{2}^{\prime }\) be the same for the schedule in Fig. 5i. We have,

Proof of Proposition 2, Case 2: A schedule where \(\hat{s}_{k+1}^{\prime }=s_{k+1}^{\prime }+x,x>0\)

Full size image

Case 2.2 \(x>0, y>x\). Once we have fixed the sizes of sublots \(k+1\) and \(k\), the leftover lot size is \(\hat{U}_{k-1}=U-\hat{s}_{k+1}^{\prime }-\hat{s}_{k}^{\prime }=U-{s}_{k+1}^{\prime }-{s}_{k}^{\prime }+(y-x)>{U}_{k-1}\) (Fig. 5iii). This is available at \(T=s_{k+1}^{\prime }+s_{k}^{\prime }+x-y+2t\), and needs to be split into \(k-1\) sublots so as to minimize makespan and avoid any overlap with the already scheduled sublots \(k+1\) and \(k\) at Stage 2. Therefore, obtaining the remaining \(k-1\) sublots as specified by Proposition 2 (with \(U=\hat{U}_{k-1}\)) may not be feasible as it may create an overlap. However, the makespan resulting from such a possibly infeasible schedule (Fig. 5iv) will provide a lower bound on the claimed optimal schedule in Fig. 5iii. Hence, it is sufficient to show that the makespan for the schedule in Fig. 5iv is greater than that in Fig.5i. We denote the difference by \(\delta _{M}\) and show here that it is positive, i.e.,

\(\square \)

Corollary 2

The completion times of the last sublots on the machines at Stage 2 are the same if \(n\ge 2\).

Proof

We consider the following two cases.

1. Number of sublots is even.

The completion time of the last sublot on machine 1 at Stage 2,

The completion time of the last sublot on machine 2 at Stage 2,

Therefore,

\(\square \)

2. Number of sublots is odd.

The completion time of the last sublot on machine 1 at Stage 2,

The completion time of the last sublot on machine 2 at Stage 2,

Therefore,

\(\square \)

Corollary 3

When \(p=1\) and \(t=0\), we have \(s_{2}^{\prime }=2s_{1}^{\prime }\), \(s_{i}^{\prime }=s_{i-1}^{\prime }+s_{i-2}^{\prime }, i=3\ldots ,n\), and \(\sum _{i=1}^{n}s_{i}^{\prime }=U\) by Proposition 2. Obviously, the sizes of the sublots follow the Fibonacci sequence since \(s_{i}^{\prime }=s_{i-1}^{\prime }+s_{i-2}^{\prime }\). And, the optimal sublot sizes are given by:

where

Proof

First, we show that the value of \(s_1^{\prime }\) obtained using expressions (22) and (35) is the same.

When \(p=1\) and \(t=0\), the values of \(A\) and \(B\), given by (23) and (24), repectively, reduce to:

Then, by (22), we have.

Substituting \(i=1\) in (35), we have,

which is the same as above. Next, consider \({s_2}^{\prime }\). Since \(s_{2}^{\prime }=2s_{1}^{\prime }\), we have,

Thus, we have shown expression (35) to hold true for \(k=1,2\). Suppose it is true for \(k=1,\ldots ,i-1\). We want to show that it holds for \(k=i\) as well. We have,

\(\square \)

Appendix 2

Determination of A and B when \({\varvec{p\ne 2}}\)

We have \(s_{1}^{\prime }\) given by:

In order to calculate \(A\), let \(y_{i}\) be the coefficient of \(s_{i}^{\prime }\), i.e., \(y_{1}=1\), \(y_{2}=1+\frac{1}{p}\), and \(y_{i}=\frac{y_{i-1}+y_{i-2}}{p},\,\forall i=3,\ldots ,n\). Let \(\sigma _{i}=\sum _{k=1}^{i}y_{k}\), i.e., \(\sigma _{1}=y_{1}=1\), \(\sigma _{2}=y_{1}+y_{2}=1+1+\frac{1}{p}=2+\frac{1}{p}\). We have,

Therefore, \(\sigma _{i}\) follows a recurrence relation, but with a constant 2. In order to eliminate the constant, we define a new variable,

Furthermore, to solve for \(a\), we have,

Substituting \(a\) into the expression for \(\beta _{i}\), we have \(\beta _{1}=\sigma _{1}+a=1+\frac{2p}{2-p}\), \(\beta _{2}=\sigma _{2}+a=2+\frac{1}{p}+\frac{2p}{2-p}\), and \(\beta _{i}=\frac{\beta _{i-1}+\beta _{i-2}}{p},\,\forall i=3,\ldots ,n\). We can use the following recurrence relation to solve for \(\beta _{i}\) and \(A\) (see Chiang (1984) [2]):

where \(\lambda _{1}\) and \(\lambda _{2}\) are the roots of

Therefore,

The values of \(C\) and \(D\) can be obtained by using the values of \(\beta _{1}\) and \(\beta _{2}\). Thus,

Substituting for \(\lambda _{1}\), \(\lambda _{2}\), \(C\) and \(D\) into (37), we have

Therefore,

\(\square \)

In order to determine \(B\), let \(q_{i}\) be the constant term of \(s_{i}^{\prime }\), i.e., \(q_{1}=0\), \(q_{2}=\frac{t}{p}\), and \(q_{i}=\frac{q_{i-1}+q_{i-2}}{p}+\frac{2t}{p},\,\forall i=3,\ldots ,n\). To eliminate the constant term \(\frac{2t}{p},\) we define a variable, \(T_{i}=q_{i}+b\),

Therefore, we have \(T_{1}=q_{1}+b=\frac{2t}{2-p},\) \(T_{2}=q_{2}+b=\frac{t}{p}+\frac{2t}{2-p},\) and \(T_{i}=\frac{T_{i-1}+T_{i-2}}{p},\,\forall i=3,\ldots ,n.\)

Let \(\pi _{i}=\sum _{k=1}^{i}T_{k}\), i.e., \(\pi _{1}=T_{1}=\frac{2t}{2-p}\), \(\pi _{2}=T_{1}+T_{2}=\frac{t}{p}+\frac{4t}{2-p}\). We have,

Therefore, \(\pi _{i}\) follows a recurrence relation, but with a constant \(\frac{4t}{2-p}+\frac{t}{p}-\frac{2t}{p\left( 2-p\right) }\). To eliminate the constant, we define a new variable,

In order to solve for \(c\), we have

Substituting \(c\) into the expression for \(\Omega _{i}\), we have \(\Omega _{1}=\pi _{1}+c=\frac{3t}{2-p}+\frac{4tp-2t}{\left( 2-p\right) ^{2}}\), \(\Omega _{2}=\pi _{2}+c=\frac{t}{p}+\frac{5t}{2-p}+\frac{4tp-2t}{\left( 2-p\right) ^{2}}\), and \(\Omega _{i}=\frac{\Omega _{i-1}+\Omega _{i-2}}{p},\,\forall i=3,\ldots ,n\). We can use the following recurrence relation to solve for \(\Omega _{i}\) and \(B\).

where \(\lambda _{1}\) and \(\lambda _{2}\) are the roots of (38) given by (39) and (40).

The values of \(G\) and \(H\) can be solved for by using the values of \(\Omega _{1}\) and \(\Omega _{2}\). Thus,

Substituting for \(\lambda _{1}\), \(\lambda _{2}\), \(G\) and \(H\) into (41), we have

Therefore,

\(\square \)

Development of closed-form expressions for sublot sizes when \({\varvec{p=2}}\)

Substituting \(p=2\) in Expressions (32)–(34), we have,

Let \(F_{i}=s_{i}^{\prime }+it^{\prime }\), where \(t^{\prime }=-\frac{2}{3}t\). Then, \(F_{1}=s_{1}^{\prime }-\frac{2}{3}t\) and \(F_{2}=s_{2}^{\prime }-\frac{4}{3}t=\frac{3}{2}s_{1}^{\prime }+\frac{t}{2}-\frac{4}{3}t=\frac{3}{2}s_{1}^{\prime }+\frac{5}{6}t\). Since \(s_{i}^{\prime }=\frac{s_{i-1}^{\prime }+s_{i-2}^{\prime }}{2}+t, i=3,\ldots ,n,\) we have

Once again, we can use the following recurrence relation to solve for \(F_{i}\).

where \(\lambda _{1}^{\prime }\) and \(\lambda _{2}^{\prime }\) are the root of

Therefore, \(\lambda _{1}^{\prime }=1\) and \(\lambda _{2}^{\prime }=-\frac{1}{2}\). The value of \(C^{\prime }\) and \(D^{\prime }\) can be obtained by using the values of \(T_{1}\) and \(T_{2}\). Thus,

By substituting the values of \(\lambda _{1}^{\prime }\), \(\lambda _{2}^{\prime }\), \(C^{\prime }\) and \(D^{\prime }\) into (43), we have

Therefore,

By substituting the value of \(s_{2}^{\prime },s_{3}^{\prime },\ldots ,s_{n}^{\prime }\) into (44), we have

Therefore,

When \(s_{1}^{\prime }>0\), the optimal makespan,

Reprints and permissions