Plane Thermoelastic Waves in Infinite Half-Space Caused
Operational Research in Engineering Sciences: Theory and Applications
Vol. 4, Issue 3, 2021, pp. 142-175
ISSN: 2620-1607
eISSN: 2620-1747
DOI: https://doi.org/10.31181/oresta111221142c
* Corresponding author.
cetinkaya@cankaya.edu.tr (F. C. Çetinkaya), mehmet.duman@neu.edu.tr (M. Duman)
SCHEDULING WITH LOT STREAMING IN A TWO-
MACHINE RE-ENTRANT FLOW SHOP
Ferda Can Çetinkaya 1*, Mehmet Duman 2
1 Department of Industrial Engineering, Çankaya University, Ankara, Turkey
2 NERITA, Near East University, TRNC, Mersin 10, Turkey
Received: 16 August 2021
Accepted: 24 November 2021
First online: 11 December 2021
Research paper
Abstract: Lot streaming is splitting a job-lot of identical items into several sublots
(portions of a lot) that can be moved to the next machines upon completion so that
operations on successive machines can be overlapped; hence, the overall performance
of a multi-stage manufacturing environment can be improved. In this study, we
consider a scheduling problem with lot streaming in a two-machine re-entrant flow
shop in which each job-lot is processed first on Machine 1, then goes to Machine 2 for
its second operation before it returns to the primary machine (either Machine 1 or
Machine 2) for the third operation. For the two cases of the primary machine, both
single-job and multi-job cases are studied independently. Optimal and near-optimal
solution procedures are developed. Our objective is to minimize the makespan, which is
the maximum completion time of the sublots and job lots in the single-job and multi-
job cases, respectively. We prove that the single-job problem is optimally solved in
polynomial-time regardless of whether the third operation is performed on Machine 1
or Machine 2. The multi-job problem is also optimally solvable in polynomial time
when the third operation is performed on Machine 2. However, we prove that the
multi-job problem is NP-hard when the third operation is performed on Machine 1. A
global lower bound on the makespan and a simple heuristic algorithm are developed.
Our computational experiment results reveal that our proposed heuristic algorithm
provides optimal or near-optimal solutions in a very short time.
Key words: scheduling, lot streaming, two-machine, re-entrant flow shop, makespan.
1. Introduction
Manufacturing systems vary from a simple one-stage environment to more
complex environments, such as a general job shop system, where jobs have different
routings through multiple stages. Since the well-known efficient scheduling
algorithm for the basic two-machine flow shop system, in which the flow of each job
Scheduling with lot streaming in a two-machine re-entrant flow shop
143
is the same, was proposed by Johnson (1954), scheduling problems in different and
more complicated manufacturing environments have been extensively studied. The
re-entrant flow shop, which is a relatively new flow shop manufacturing
environment, has drawn researchers’ attention. In the re-entrant flow shop, a job has
to re-visit some of the machines since the number of operations for each job is more
than the number of machines (Lev & Adiri, 1984). We observe re-entrant Re-entrant
flow shops can be observed mainly in textile and high-tech industries, such as
printing printed circuit boards, wafer fabrications, and signal processing.
In all of the studies in the literature for the re-entrant flow shops and most of the
scheduling studies for the other multi-stage manufacturing systems, it is assumed
that jobs are indivisible entities. Thus, an operation of a job-lot (i.e., a process batch)
consisting of identical units must be finished before it this job lot is transferred to the
next machine. However, in many industrial applications, a job lot can be split into
several sublots (i.e., transfer batches), which are the partial batches of the process
batch. Transfer of the processed sublots to downstream machines without waiting
for the completion of the whole job-lot on a machine gives an opportunity of allows
the operations overlapping to overlap. The process of simultaneously splitting a job-
lot into sublots and scheduling those sublots by overlapping their operations is
known as lot streaming, which was first mentioned as a scheduling technique by
Reither (1966).
In this paper, we consider a scheduling problem with lot streaming in a two-
machine re-entrant flow shop where each job-lot is processed first on Machine 1,
then goes to Machine 2 for its second operation before it returns to the primary
machine (either Machine 1 or Machine 2) for the third operation. We first focus on
the single-job problem where a job-lot is spilt split into a given number of consistent
or variable sublots. Consistent sublots case is the case where the size of each sublot
does not change over the machines. However, the sublot sizes may change vary over
the machines when variable sublots are used. Next, we extend the problem to the
multi-job case in which the size of sublots and the schedule of multiple sublots and
job lots need to be determined simultaneously. Our objective is to minimize the
makespan, equivalent to the time to complete the last sublot in the single-job case,
whereas it is the time to complete the last job lot in the multi-job case. Makespan
aims to increase the utilization of the machines in the shop. To the best of our
knowledge, our study is the only one that applies lot streaming for single- and multi-
job cases in the re-entrant flow shops.
The organization of the remaining parts is as follows. The following section
presents a literature review on lot streaming problems, especially those in two- and
three-machine manufacturing shops. In Section 3, the single-job problem is studied,
and the optimal schedules with consistent and variable sublots are developed.
Section 4 considers the multi-job lot streaming problem and gives an exact algorithm
that determines the optimal consistent-sublot sizes and job schedules when the
primary machine is Machine 2. Next, the multi-job lot streaming problem, in which
the primary machine is Machine 1, is proved to be strongly NP-hard, and a
polynomial-time solvable case of the problem is provided. Moreover, a heuristic
algorithm is provided for the multi-job problem where the primary machine is
Machine 1, and its effectiveness is computationally tested. Finally, our brief
conclusions and some issues for future research are summarized in Section 5.
Çetinkaya & Duman /Oper. Res. Eng. Sci. Theor. Appl. 4 (3) (2021) 142-175
144
2. Literature review
Although lot steaming is known and used in practice, there were no analytical
studies in the literature of scheduling problems until the late ‘80s. Since then, lot
streaming has attracted significant interest from researchers dealing with scheduling
problems.
Based on the number of job lots, the studies in the literature can be divided into
two categories. One category is called the single-job lot problem and deals with the
sublot-sizing problem in which the sublot sizes are determined when there is a single
job lot. The other category is called multi-job problem and deals with the sublot-
sizing and job-sequencing subproblems simultaneously. Here, we limit our
literature review to the lot streaming studies for the single- and multi-job lot cases in
two- and three-machine manufacturing shops only to expose the proper place of our
study in the literature.
The study by Baker (1988) is the first one considering the lot streaming
technique for a single-job problem in two- or three-machine flow shops to minimize
the makespan. For the two-machine case, he provided a linear programming model
and determined the sublot sizes optimally. He also determined the optimal sublot
sizes for the three-machine case where the job-lot is split into two sublots only. Potts
& Baker (1989) proved that optimal sublots are consistent in the two-machine flow
shop and illustrated that the consistent sublots are not always optimal for the flow
shops with three and more machines. Glass et al. (1994) developed an algorithm that
determines the optimal consistent-sublot sizes for the three-machine flow shop to
minimize the makespan. This study was extended to the cases with sequence-
independent detached and attached setups by Chen & Steiner (1997) and Chen &
Steiner (1998), respectively. In the attached setup case of a machine, the first sublot
belonging to a job lot should be available before setting up this machine. However, in
the detached setup case, no need to wait for the arrival of the job lot. In both cases,
no setup is necessary between successive sublots of the same job lot. In both cases,
no setup is necessary between successive sublots of the same job lot. On the other
hand, variable sublots case of the single job-lot problem was first examined by
Trietsch (1989). The optimal solution with variable sublots in the three-machine
flow shop was proposed by Trietsch & Baker (1993). Alfieri et al. (2012) and Alfieri
et al. (2021) proposed exact, and heuristic solution approaches based on dynamic
programming for a single-job problem to minimize the makespan and total flow time,
respectively, in a two-machine flow shop with attached setup times.
Vickson & Alfredson (1992) considered the concept of lot streaming for
scheduling multiple job lots in flow shops. They demonstrated that a modified
Johnson’s algorithm with unit-sized sublots solves the two-machine makespan
minimization problem when the number of sublots in each jot-lot is unlimited and
proved that sublots in each job-lot should be processed successively without the
intermingling of different job lots. Vickson & Alfredson’s study was extended by
Çetinkaya & Kayalıgil (1992) to develop a unified algorithm that treats sequence-
independent attached and detached setups. Çetinkaya (1994) considered the
scheduling of multiple job lots in a two-machine flow shop with attached setup and
removal times on the machines and proved that the optimal schedule of the job lots
to minimize the makespan is obtained by determining the equal or unequal sublots
sizes of each job-lot independently and sequencing the job lots by a modified
Scheduling with lot streaming in a two-machine re-entrant flow shop
145
Johnson’s algorithm. Vickson (1995) provided an optimal solution for the multi-job
problem in a two-machine flow shop with sequence-independent attached or
detached setups and transfer times from the first machine to the second one. Pranzo
(2004) extended Çetinkaya’s study by considering limited buffers between machines.
Glass & Possani (2011) considered the two-machine flow shop problem with
attached setup and transportation times to minimize the makespan of the multiple
job lots. Their study showed that sublot-sizing and job-sequencing problems are
solved independently, as in Çetinkaya (1994) and Vickson (1995), and provided an
algorithm solvable in polynomial time. Baker (1995) considered the multi-job
problem with equal-sized sublots and setup times in a two-machine flow shop and
proposed an algorithm using the time-lag approach. Yang & Chern (2000) extended
Baker’s study to where detached setup times, transportation times, and removal
times exist. Sriskandarajah & Wagneur (1999) investigated the multi-job problem in
a two-machine flow shop with no-wait constraint. Çetinkaya (2005) considered a
two-machine flow shop with a single agent transferring a completed item from
Machine 1 to Machine 2. Machine 1 is blocked while the transport agent is in
transferring and returning. He provided an algorithm that determines the optimal
schedule for the case with unit-sized sublots.
From the early 2000s, researchers began to consider flow shops with more than
three machines (stages). Several metaheuristic algorithms, such as genetic
algorithms (Yoon & Ventura, 2002; Marimuthu et al., 2008; Martin, 2009; Defersha &
Chen, 2010), discrete particle swarm optimization algorithm (Tseng & Liao, 2008),
threshold accepting and ant-colony optimization algorithms (Marimuthu et al.,
2009), discrete artificial bee colony algorithm (Pan et al., 2011), and migrating birds
optimization algorithm (Devendra et al., 2014; Meng et al., 2018) have been
proposed to solve the multi-job lot streaming problem by considering its different
aspects.
All the studies mentioned above for the multi-job scheduling with lot streaming in
the flow shops with more than three machines assume that sublots in each job lot
should be processed successively for each operation on each machine. i.e., the
intermingling of the job lots is not allowed, and the schedules are permutation
schedules where the sequence of job lots on all machines is the same. However, a
more realistic case is when intermingling of the job lots and non-permutation
schedules are allowed. Feldmann & Biskup (2008) investigated the permutation
flowshop scheduling problem with lot streaming and intermingling and developed a
mixed-integer programming model. Rossit et al. (2016) investigated this non-
permutation flowshop scheduling problem with lot streaming. They proposed a
mathematical model to minimize the makespan of the multiple job lots that are not
allowed to be intermingled.
Besides the studies mentioned above, lot streaming studies for other two- and
three-machine manufacturing shops are scarce. There are studies considering open
shops (Şen & Benli, 1999), hybrid flow shops (Kim et al., 1997; Zhang et al., 2003;
Zhang et al., 2005; Liu, 2008; Defersha, 2011; Defersha & Chen, 2012a; Naderi &
Yazdani, 2015; Cheng et al., 2016; Zhang et al., 2017; Wang et al., 2019; Li et al.,
2020), and mixed shops (Çetinkaya & Duman, 2010), job shops (Buscher & Shen,
2009; Defersha & Chen, 2012b), and assembly shops (Sarin et al., 2011; Yao & Sarin,
2014; Nejati et al., 2016; Cheng & Sarin, 2020).
Çetinkaya & Duman /Oper. Res. Eng. Sci. Theor. Appl. 4 (3) (2021) 142-175
146
The comprehensive surveys by Chang & Chiu (2005), Sarin & Jaiprakash (2007),
Gomez-Gasquet et al. (2013), and Cheng et al. (2013), and Salazar-Moya & Garcia
(2021) are also available for lot streaming problems with job lots having more than
one operation in multiple machines environments.
As we can see from the lot streaming literature and to the best of our knowledge,
there is no previous study dealing with lot streaming for single- and multi-job cases
in the re-entrant flow shops. The main contributions of our study can be summarized
as follows:
• This study is the first one in the scheduling literature dealing with lot
streaming in the re-entrant flow shops.
• Our study proves that the single-job problem is polynomial-time solvable
regardless of whether the third operation is performed on Machine 1 or
Machine 2 and develops optimal schedules with closed formulae for the
optimal consistent and variable sublot sizes.
• Our study also proves that the multi-job problem is polynomial-time solvable
when the third operation is performed on Machine 2 and develops optimal
schedules with closed formulae for the optimal sublot sizes. However, the
multi-job problem is NP-hard when the third operation is performed on
Machine 1.
• A global lower bound on the makespan and a simple heuristic algorithm
providing optimal or near-optimal schedules have been developed.
3. Single-job case
Our single-job problem in the two-machine re-entrant flow shop is explained as
follows: A job-lot of U identical items has three operations to be performed. Each
operation k )3,2,1( =k requires kp time units of processing. There are two
machines 1M (Machine 1) and 2M (Machine 2) operating independently. The first
and second operations of the job-lot are performed on 1M and 2M , respectively. A
primary machine ( 1M or 2M ) is re-visited by each item of the job lot for its third
operation; hence the shop is a re-entrant flow shop. The job-lot is split into s sublots,
and kix , is the size of the i th sublot that completes its k th operation. Sublots of a
job-lot can be immediately transferred from one machine to another for their next
operation without waiting to complete other sublots. The goal is to determine the
size and schedule of all sublots to minimize the makespan, which is the time to
complete the third operation of the sublot processed as the last.
The assumptions made for the single-job problem are summarized here:
• The sublots of a job lot are processed without any interruption on every
machine. i.e., pre-emption is not allowed.
• Each machine is ready at the beginning, say time zero, of the planning
horizon. i.e., machines are not batching machines.
• At any time, only one item of a job lot can be processed by a machine.
• An unlimited storage space exists between the machines.
• An idle time on a machine may occur between processing sublots.
Scheduling with lot streaming in a two-machine re-entrant flow shop
147
• Transfer times from one machine to another are negligibly so short and thus
ignored.
• Setup times before processing the job-lot on a machine are negligibly so
short and thus ignored.
• The number of sublots is known in advance and fixed from one machine to
another.
• Processing times are known and deterministic.
3.1. Machine 2 is the primary machine
We first consider that 2M is the primary machine where the third operation is
performed. We investigate the problem for cases with consistent and variable
sublots.
3.1.1. Consistent sublots
When the lot streaming is applied, sometimes there might be no advantage to
change the size of the sublots after they have completed their processing on a
machine. In this situation, it is reasonable to let the sublot sizes be constant
(consistent) over all pairs of operations, i.e., iki xx =, for 1, 2,..., ; 1, 2, 3i s k= = where
Ux
si i
= 1 . Sublot availability assumption is used when sublots are consistent.
i.e., a sublot can be processed at the next machine if all items in this sublot are
completed on the current machine.
We start our analysis with the following lemma.
Lemma 1. For the single-job problem where 2M is the primary machine, it is sufficient
to consider schedules of sublots where the last two operations of the sublots are
processed consecutively on 2M .
Proof. Consider any schedule of the consistent sublots. Suppose that there is a pair
of sublots u and v , where the second operation of sublot v is immediately
processed before the third operation of sublot u on 2M . Then interchanging the
positions of sublots u and v on 2M is feasible and does not increase makespan. On
machine 2M , when all sublots, which are immediately processed before sublot u ,
are pair-wise interchanged with the second operation of sublot u , then it is possible
to consecutively process the second and the third operations of sublot u on 2M .
Similarly, it is possible to schedule consecutively the second and the third operations
of all sublots on 2M .
From Lemma 1, the single-job problem can be illustrated by a network, as shown
in Figure 1. Let 1 2( , ,..., )sx x x x= denote the sublot sizes, and ( , )k i be a node for the
pair with operation k ( 1, 2, 3)k = and sublot i ( 1,..., )i s= where k ip x is the
processing time of the k th operation of sublot i . The vertical arc from node (1, )i to
node (2, )i indicates that sublot i cannot be processed on 2M unless it is completed
on 1M . The horizontal arc from node (1, )i to node (1, 1)i + indicates that 1M can
Çetinkaya & Duman /Oper. Res. Eng. Sci. Theor. Appl. 4 (3) (2021) 142-175
148
start to process sublot 1i+ upon the completion of sublot i on 1M . Similarly, the
horizontal arc from (2, )i to (3, )i represents that the third operation of sublot i
can be started when its second operation is completed on 2M .
Figure 1. Network representation for the case where 2M is the primary machine
Here, the goal is to determine the sublot sizes minimizing the critical path
(longest path) length from node (1, 1) to (3, )s , in which the sum of the processing
times of the nodes on the critical path gives the length of the critical path.
The following theorem gives the optimal sublot sizes for the single-job problem
where 2M is the primary machine.
Theorem 1. For the single-job problem where 2M is the primary machine, the optimal
consistent-sublot sizes are 2 1
1
/(1 ... )
s
x U
−
= + + + + , 1
1
xx
i
i
−
= for si ,...,2=
where ( ) 132 / ppp += , 1 ii sU x = , and the associated optimal makespan is
( )2 1max 1 1 2 3 1 2 31( ) /(1 ... ) ( )
s s
ii
C p x p p x p p p U
−
=
= + + = + + + + + + .
Proof. See the Appendix A. ■
Theorem 1 proves that the single-job problem where 2M is the primary machine
is equivalent to the single-job problem in the basic two-machine flow shop with
processing times 1p and 32 pp + on 1M and 2M , respectively. From Theorem 1, it is
clear that the optimal consistent-sublot sizes can be determined in ( )O s time.
Example 1. In this numerical example, we illustrate Theorem 1, in which the
consistent sublots are optimal. Suppose that we have a job lot of 70 identical items
that will be split into three sublots, and the processing times for its three operations
are 2, 3, and 1 time-units, respectively. Then, from Theorem 1, we determine that the
sublot sizes are found to be 10, 20, and 40 units for the first, second, and third
sublots, respectively. That is,
2 1 3 1
1
/(1 ... ) 70/(1 2 2 ) 10
s
x U
− −
= + + + + = + + = , 2x =
1
12 (2)(10) 20x = = , and
2
3 1
2 (4)(10) 40x x= = = , where 2 3 1( ) / (3 1) / 2p p p = + = +
2= . The optimal makespan is max 1 1 2 3( ) (2)(10) (3 1)(70) 300C p x p p U= + + = + + = , as
illustrated in Figure 2.
3.1.2. Variable sublots
In some cases, there might be some advantages to change the size of the sublots
after they have completed their processing on a machine. Thus, variable sublots are
11xp
12xp
21xp
22xp
Sxp2
Sxp3
13xp
23xp
Sxp1
1M
2M
31xp
32xp
Scheduling with lot streaming in a two-machine re-entrant flow shop
149
preferred to the consistent sublots, using the item availability assumption where an
individual item in a sublot can be processed at the next machine when this item is
completed on the current machine.
Figure 2. Optimal schedule of the sublots in Example 1
Remark 1. There is no need to investigate the optimal solution for the single-job
problem having variable sublots in the two-machine re-entrant flow shop where 2M is
the primary machine. The solution of the single-job problem having consistent sublots is
also optimal for the single-job problem having variable sublots since only one set of
sublot transfers from 1M to 2M is needed when the second and third operations are
performed on 2M .
3.2. Machine 1 is the primary machine
We now consider that 1M is the primary machine where the third operation is
performed. We again investigate the problem for cases with consistent and variable
sublots.
3.2.1. Consistent sublots
Similar to the analysis given by Wang et al. (1997) for the basic two-machine re-
entrant flow shop makespan minimization problem without lot streaming, we
present the following lemma and theorem for finding the optimal solution to our
problem having consistent sublots when 1M is the primary machine. We first give the
following definitions.
Definition 1. A schedule is called a compact schedule if the first operations of all
sublots are scheduled successively on 1M and then followed by the third operations of
all sublots.
Definition 2. A schedule is called a permutation schedule if all sublots are processed
in the same order on both machines.
Lemma 2. For the single-job problem where 1M is the primary machine, it is sufficient
to consider only compact and permutation schedules of the sublots.
Proof. Consider any feasible schedule with consistent sublots. We first show that
can be transformed into a compact schedule on 1M without worsening the
makespan. Suppose we have a pair of two sublots, u and v , where the last (third)
operation of sublot u immediately precedes the first operation of sublot v on 1M ,
i.e., 1,3, vu OO . Then interchanging their positions does not worsen the makespan.
60 50 300 260
140
140 120
60
2
20
20
2M
1M 1 2 3
1 1 2 3 3
Çetinkaya & Duman /Oper. Res. Eng. Sci. Theor. Appl. 4 (3) (2021) 142-175
150
When all sublots, which immediately follow sublot u , are pair-wise interchanged
with sublot u , we assume that all first operations of the sublots are scheduled first
on 1M . If any, we may eliminate the idle time between the first operations of any
pair of successive sublots by moving the start time of the second sublot in the pair to
the left. This movement does not affect the feasibility and does not change the
makespan. Now, assume that an idle time exists between the last operations of any
pair of successive sublots. Then we can eliminate it by moving all sublots except the
last to the right. Again, this movement does not affect the feasibility and does not
change the makespan. This shows that the first and the last operations of the job-lot
are performed continuously without idle time between the sublots on 1M . Now,
consider any optimal schedule , which is compact on 1M but in which the
processing order of the sublots on the first pair ),( 21 MM of machines is different.
Let sublots u and v be the first pair of sublots such that 2,1, vu OO and ,2 ,2 v uO Op .
Let sublots u and v be the last pair of sublots such that 1,1, vu OO and 2,2, uv OO .
Interchanging the order of 2,uO and 2,vO is possible and maintains compactness on
1M , and the makespan remains unchanged. This indicates that an optimal schedule,
which is compact and the processing order of the sublots on the last pair ),( 12 MM of
machines is the same, exists.
Theorem 2. Let maxC and maxC denote the optimal makespan values of the single-job
problem having consistent sublots in the two-machine re-entrant flow shop where 1M
is the primary machine and the single-job problem having consistent sublots in the
basic three-machine flow shop, respectively. If
max 1 31
( )
s
ii
C p p x
=
+ = 1 3( )p p U+
then maxmax CC = ; otherwise, UppC )( 31max += .
Proof. The single-job problem where 1M is the primary machine can be represented
by a network, as illustrated in Figure 3. Let ),...,,( 21 sxxxx = denote the sublot sizes
and ),( ik be a node for the pair with operation k )3,2,1( =k and sublot i ),...,1( si = ,
having a weight of ikxp that represents the sublot processing time. The vertical arc
from node ) ,1( i to node ) ,2( i indicates that sublot i can be processed on 2M upon
its completion on 1M . The horizontal arc from node ) ,1( i to node )1 ,1( +i indicates
that 1M can start to process sublot 1i+ upon the completion of sublot i on 1M .
Similarly, the vertical arc from ) ,2( i to ) ,3( i represents that the third operation of a
sublot can be started when the second operation is completed on 2M . In view of
Lemma 2, we observe that the precedence constraint of arc between ) ,1( s and )1 ,3(
becomes redundant if UppC )( 31max + . Thus, an idle time on 1M exists between
the first operation of the last sublot and the third operation of the first sublot.
However, if the arc between ) ,1( s and )1 ,3( is removed from the network )(xN , the
new network then represents the lot streaming problem in the three-machine flow
shop. Therefore, it is clear that max max 1 3max , ( )= +C C p p U . It is obvious that
max max
=C C when
max 1 3
( ) +C p p U . Thus in this case, the lot streaming problems in
Scheduling with lot streaming in a two-machine re-entrant flow shop
151
the basic three-machine flow shop and the two-machine re-entrant flow shop are
equivalent. However,
max 1 3
( )= +C p p U when
max 1 3
( )C p p U + . ■
As a result of Theorem 2, an optimal solution to the single-job problem where 1M
is the primary machine can be constructed by the optimal solution proposed by Glass
et al. (1994) for the single-job problem having consistent sublots in the basic three-
machine flow shop, as in the following corollary.
Figure 3. Network representation for the case where 1M is the primary machine
Corollary 2. When the makespan is minimized, the optimal consistent-sublot sizes for
the single-job problem in the basic three-machine flow shop are also optimal for the
single-job problem having consistent sublots in the two-machine re-entrant flow shop
where 1M is the primary machine, and they are as follows:
(i) If 31
2
2 ppp , then the optimal sublot sizes are:
/
)1/()1(
31
31
1
=
−−
=
ppifsU
ppifU
x
s
, 1
1
xx
i
i
−
= for si 2 where
2 3 1 2( )/( )p p p p = + + .
(ii) If 31
2
2 ppp , then there exists a crossover sublot h , which can be determined by a
search algorithm in )(log sO time, for which the optimal sublot sizes are:
=
=
−+−−
−−+−
−−−+−−
=
+−
+−
3221
3221
3221
1
1
,
,
,
})1/()1/{(
)}1/()1(1/{
}1)1/()1()1/()1/{(
ppppif
ppppif
ppppif
hsU
hU
U
x
h
hs
hsh
h
,
h
ih
i xx
−
= for 11 − hi , h
hi
i xx
−
= for sih where 21 / pp= and
23 / pp= .
Example 2. Assume that we have a job lot of 70 identical items that will be split into
three sublots, and the processing times for its three operations are 1, 4, and 2 time-
units, respectively. This case corresponds to the second case in Corollary 2 since
2
2
p =
2
1 3
(4) 16 (1)(2) 2p p= = = . The size of the crossover sublot h is determined
11xp 21xp 11 −Sxp Sxp1 1M
12xp 22xp Sxp2 2M 12 −Sxp
13xp 23xp 13 −Sxp Sxp3 1M
Çetinkaya & Duman /Oper. Res. Eng. Sci. Theor. Appl. 4 (3) (2021) 142-175
152
by
1
/{( 1) /( 1) ( 1) /( 1) 1}
h s h
h
x U
− +
= − − + − − − where 4/1/ 21 == pp and 3p =
2
/ 1/ 2p = since
1 2 3
1 4 2p p p= = = .
When 1=h ,
1 1 3 1 1
1
1 1 (1/ 4) 1 (1/ 2) 1
/ 1 70 / 1
1 1 (1/ 4) 1 (1/ 2) 1
h s h
x U
− + − + − − − −
= + − = + − = − − − −
70
40
1.75
= , 20)40()2/1(
1
1
12
2 ===
−
xx , 10)40()2/1(
2
1
13
3 ===
−
xx , and 340max =C .
When 2=h ,
1 2 3 2 1
2
1 1 (1/ 4) 1 (1/ 2) 1
/ 1 70 / 1
1 1 (1/ 4) 1 (1/ 2) 1
h s h
x U
− + − + − − − −
= + − = + − = − − − −
70
40
1.75
= , 10)40()4/1(
1
1
12
1 ===
−
xx , 20)40()2/1(
1
1
23
3 ===
−
xx , and 330max =C
(See Figure 4a).
When 3=h ,
1 3 3 3 1
3
1 1 (1/ 4) 1 (1/ 2) 1
/ 1 70 / 1
1 1 (1/ 4) 1 (1/ 2) 1
h s h
x U
− + − + − − − −
= + − = + − − − − −
53.33 , 33.3)33.53()4/1(
2
1
13
1 ===
−
xx , 33.13)33.53()4/1(
1
1
23
2 ===
−
xx , and
390max =C .
It is clear that the optimal sublots are achieved when 2=h , and their sizes are
101 =x , 401 =x , and 203 =x . Note that the optimal makespan is 330maxmax == CC
since
max 1 3
330 ( ) (1 2)(70) 210 = + = + =C p p U , and the optimal schedule is obtained
by carrying the third operations of the sublots in the three-machine flow shop
problem to 1M , as illustrated in Figure 4b.
Figure 4. Optimal schedules with consistent sublots for the single-job problem in
Example 2: (a) Three-machine flow shop; (b) Two-machine re-entrant flow shop.
10 50 70
50 70 210 290 330
10 50 210 290
10 50 70 190 210 290 330
1M
2M
1 2 3
1
1 2 3
2 3
10 50 210 290
2M
1M
3M
3
1 2 3
(a)
(b)
2 1
1 2 3
Scheduling with lot streaming in a two-machine re-entrant flow shop
153
3.2.2. Variable sublots
As a result of Theorem 2, an optimal solution to the single-job problem having
variable sublots where 1M is the primary machine can be constructed by the optimal
solution proposed by Trietsch & Baker (1993) for the single-job problem with
variable sublots in the basic three-machine flow shop, as in the following corollary.
Corollary 3. When the makespan is minimized, the optimal variable-sublot sizes in the
single-job problem in the basic three-machine flow shop are also optimal for the single-
job problem having the variable sublots in the two-machine re-entrant flow shop where
1M is the primary machine, and they are as follows:
(i) If 31
2
2 ppp , then the consistent sublots are optimal, and they are: 1 ( 1)/x U = −
( 1)s − , 1
1
xx
i
i
−
= for si 2 where )/()( 2132 pppp ++= .
(ii) If 31
2
2 ppp , then the variable sublots are optimal,
• the optimal sublot sizes between 1M and 2M are: )1/()1(1 −−=
s
Ux ,
1
1
xx
i
i
−
= for si 2 where 12 / pp= , and
• the optimal sublot sizes between 2M and 1M are: )1/()1(1 −−=
s
Ux ,
1
1
xx
i
i
−
= for si 2 where 23 / pp= .
From Corollary 3, it is clear that the optimal variable-sublot sizes can be
determined in ( )O s time.
Example 3. In this numerical example, we illustrate the second case of Corollary 3, in
which the variable sublots are optimal since 31
2
2 ppp . Assume that we have a job
lot of 15 identical items that will be split into two sublots, and the processing times
for its three operations are 1, 2, and 1 time-units, respectively. From Corollary 2, the
sublot sizes between 1M and 2M are found to be 5)12/()12(15
2
1 =−−=x and
10)5)(2(
1
2 ==x where 21/2/ 12 === pp and ).1)(1(4)2( 31
22
2 === ppp (See
Figure 5a). Similarly, the sublot sizes between 2M and 1M are calculated as
2
1
15((1/ 2) 1) /((1/ 2) 1) 10x = − − = and 5)10)()2/1((
1
2 ==x since 2/1/ 23 == pp .
Thus, the optimal makespan of the problem having variable sublots in the basic
three-machine flow shop is 40, and the optimal schedule of the problem in the two-
machine re-entrant flow shop is obtained by carrying the third operations of the
sublots in the optimal schedule of the problem in the three-machine flow shop to
1M , as illustrated in Figure 5b.
4. Multi-job case
In this section, we extend our problem presented to the multi-job case. The multi-
job problem is explained as follows: There is a job-lot set njjJ ,...,2,1== where
each job-lot has jU identical items of type j . Let kjp , be the processing time for
Çetinkaya & Duman /Oper. Res. Eng. Sci. Theor. Appl. 4 (3) (2021) 142-175
154
k th ( )3,2,1=k operation of job-lot j . There are two machines 1M and 2M . Each
job-lot is processed first on 1M , on 2M for its second operation before returning to
the primary machine ( 1M or 2M ) for the third operation. Suppose that job-lot j is
split into js sublots, then our goal is to determine the sublot sizes for each job-lot
and the schedule of all sublots and job lots to minimize the makespan.
Figure 5. Optimal schedules with variable sublots for the single-job problem in Example
3: (a) Three-machine flow shop; (b) Two-machine re-entrant flow shop.
For the multi-job problem, we consider all assumptions made for the single-job
problem. Furthermore, we do not allow the intermingling of different job lots. That
is, once a sublot of a job-lot is started on a machine, all other job lots should wait
until all of the remaining sublots of that job-lot are completed on the same machine.
Note that intermingling the sublots belonging to different job lots may further reduce
the makespan, but we focus on the no-intermingling case in our study. Intermingling
can be considered in a future study as future research, as we point out in Section 5.
As in the case of the single-job problem, we investigate two cases associated with
the primary machine.
4.1. Machine 2 is the primary machine
The following lemma gives the basic structure of the job-sequence for the multi-
job problem where 2M is the primary machine.
25
(a)
(b)
35
5 25
40 15 5
35
25
2M
1M 1 2
1 2
1 2
1 2
35
5 25
40
15 5
35
2M
1M 1 2
1 2
1 2
1 2
Scheduling with lot streaming in a two-machine re-entrant flow shop
155
Lemma 3. For an optimal solution of the multi-job problem where 2M is the primary
machine, it is sufficient to consider the job-sequence in which the last two operations of
each sublot belonging to a job-lot are processed successively on 2M .
Proof. Omitted since it is similar to the proof of Lemma 1. ■
The multi-job problem where 2M is the primary machine can be decomposed
into two sub-problems: (a) the job-sequencing and (b) the sublot-sizing.
4.1.1. Job-sequencing sub-problem
The multi-job problem reduces to the determination of the optimal sequence of
job lots when the sublot-sizing sub-problem for each job-lot has already been solved.
That is, the job-sequencing sub-problem needs to be solved. Suppose that each job-
lot j is independently split into sublots by Corollary 2 or Corollary 3. Let
jRI = time lag between the start of the first operation on 1M and the latest start
time of the second operation on 2M for job-lot j . i.e., the latest delay time,
simply called run-in-delay for job-lot j on 2M without affecting the
completion time of job-lot j (called as run-in delay for Operation 2).
jRO = time lag between the completion times of the first and the second operations
for job-lot j (called as run-out delay for Operation 2).
jIR = time lag between the latest start of the second operation on 2M and the
latest start time of the third operation on 1M for job-lot j . i.e., the latest
delay time, simply called run-in-delay for job-lot j on 1M without affecting
the completion time of job-lot j (called as run-in delay for Operation 3).
jOR = time lag between the completion times of the second and the third
operations for job-lot j (called as run-out delay for Operation 3).
The following theorem provides the optimal solution to the job-sequencing sub-
problem.
Theorem 3. Given the solution of the sublot-sizing sub-problem, job-lot v precedes
job-lot z in an optimal job-sequence if vzzv RORIRORI ,min,min , where jRI =
1
1 ,1 , ,2 ,3 ,1 1
min ( )
j
i i
i s j j r j j j rr r
p x p p x
−
= =
− + , and ,2 ,3 ,1( )j j j j j jRO RI p p p U= + + − for
any job-lot j .
Proof. See the Appendix B. ■
4.1.2. Sublot-sizing sub-problem
The sublot-sizing sub-problem needs to be solved for each job-lot when the job-
sequencing sub-problem has already been solved. The following theorem provides
the optimal solution to the sublot-sizing sub-problem.
Çetinkaya & Duman /Oper. Res. Eng. Sci. Theor. Appl. 4 (3) (2021) 142-175
156
Theorem 4. Given the solution of the job-sequencing sub-problem, the optimal sublot
sizes in a job-lot processed in position j of the job-sequence
are
2
,1
/(1 = + +
j j
x U
1
... )
−
+ +
s j
, 1,
1
, j
i
ij xx
−
= for jsi ,...,2= where
1,3,2, /)( jjj ppp += .
Proof. See the Appendix C. ■
From Theorems 3 and 4, we have the following result.
Corollary 4. Solving the sublot-sizing sub-problem using Theorem 4 and then solving
the job-sequencing sub-problem using Theorem 3 provides the optimal solution to the
multi-job problem where 2M is the primary machine.
Based on Corollary 4, we propose the following exact-solution algorithm with a
computational complexity of )log( nnO to solve the multi-job problem where 2M is
the primary machine and n is the total number of job lots.
Algorithm 1.
Step 1: [Sublot-sizing] Calculate the size for each sublot of the job-lot in the set
1, 2,...,J j j n= = as
12
,1 / (1 ... )
j
s
j jx U
−
= + + + + and 1, ,1
i
j i jx x
−
=
for 2,..., ji s= where ,2 ,3 ,1( ) /j j jp p p = + .
Step 2: [Job-sequencing]
(a) Set
12
,1 /(1 ... )
j
s
j j jRI p U
−
= + + + + and ,2 ,3(j j j jRO RI p p= + + −
,1)j jp U .
(b) To obtain the job-sequence 1, 2,..., = =j j n , consider all jobs in
the job-lot set J and apply Johnson’s Algorithm with processing times
on 1M and 2M replaced by jRI and jRO , respectively.
(ii) Calculate the associated makespan as
( )
1
max 1 ,2 ,31 1 1
max ( )
w w n
w n j j j j jj j j
C RI RO p p U
−
= = =
= − + +
4.2. Machine 1 is the primary machine
This section considers the multi-job problem where 1M is the primary machine.
Unfortunately, this problem is more complicated than the multi-job problem where
2M is the primary machine discussed in Section 4.1.
Theorem 5. The multi-job problem where 1M is the primary machine is NP-hard in
the strong sense.
Proof. Suppose that each job-lot has one sublot only. This special case of our multi-
job problem is equivalent to the multi-job problem without lot streaming in the basic
two-machine re-entrant flow shop where 1M is the primary machine. It has been
Scheduling with lot streaming in a two-machine re-entrant flow shop
157
proven by Wang et al. (1997) that this special case is NP-hard in the strong sense.
Thus, our multi-job problem where 1M is the primary machine is also strongly NP-
hard. ■
The following lemma restricts our search to the compact and permutation
schedules of the job lots for the optimal schedule of the multi-job problem where 1M
is the primary machine.
Lemma 4. For an optimal solution of the multi-job problem where 1M is the primary
machine, it is sufficient to consider only compact and permutation schedules of the job
lots.
Proof. Omitted since it is similar to the proof of Lemma 2. ■
4.2.1. A Polynomial-time solvable case
Since the multi-job problem where 1M is the primary machine has been shown to
be NP-hard in Theorem 5, an optimal algorithm solving the problem in polynomial-
time is impossible. Therefore, we first examine a polynomial-time solvable case of
the problem that corresponds to the case, in which the sublots of all job lots are
independently determined by Corollaries 2 or 3 and the idle time between the first
and the third operations of all jobs on 1M is zero.
Let jI be the idle time on 1M between the first and the third operations of job-lot
j when it is independently split into sublots by Corollaries 2 or 3. The following
theorem provides the optimal schedule for this special case.
Theorem 6. If 0=jI for every job-lot j , then arbitrarily sequencing all jobs as
illustrated in Figure 6 is an optimal schedule for the multi-job problem where 1M is the
primary machine.
Proof. If 0=jI for every job-lot j , there will be no idle time between the first and
the third operations of job-lot j on 1M when job lots are arbitrarily sequenced.
Then, the time to complete all operations of job-lot j becomes
,1 ,3
( )
j j j j
T p p U= +
,1 ,3
( )
j j j j
I p p U+ = + when it is independently split into sublots, and
max 1
n
jj
C T
=
= =
,1 ,31
( )
n
j j jj
p p U
=
+ becomes the optimal makespan.
Figure 6. Optimal schedule obtained by Theorem 6
nT 2T 1T
1M
2M
1 1 2 2 n n
1 2 n
Çetinkaya & Duman /Oper. Res. Eng. Sci. Theor. Appl. 4 (3) (2021) 142-175
158
4.2.2. Proposed heuristic algorithm
For a given job-sequence , we define the job-lot d such that
,11 ,2 ,21 − =
n
j jd dj
C p U C where 2,dC is the time to complete the second
operation of job-lot d , and
(2,2 ,21 11,..,( ) max = + === − = −
n j
d j d ij d ij n
C C p U RI
) ( )
1
,21 1
−
= =
+
j n
ji ji j
RO p U where )(2 C is the completion time of all job lots in
sequence on 2M , and 1 ,2 ,2 ,2d d d dC C p U − = − . Here job-lot d that will be
used to develop the proposed algorithm is called a partition job-lot and is the first
job whose second operation finishes later than the completion of all first operations
on 1M (see Figure 7). From the definition of the job-lot d , it is clear that no idle
time exists between job lots following job-lot d on 2M . Thus, permutation
sequence is partitioned into three subsequences: | 1,...,BJ j j= = 1d − ,
djjJD == | , and ndjjJA ,...,,1| +== .
We propose the following heuristic algorithm with a computational complexity of
)log( nnO to solve the multi-job problem where 1M is the primary machine.
Figure 7. Partition job-lot in position d of the job-sequence
Algorithm 2.
Step 1: For each job lot j ,
(a) If sublots are considered as consistent, then use the sublot sizes in
Corollary 2; otherwise (variable sublots), use the sublot sizes in
Corollary 3.
(b) Compute the makespan jT , and idle time on 1M as ,1(j j jI T p= − +
,3
)
j j
p U .
Step 2: Divide the job-lot set J into two sets: 0|1 == jIjJ and
2
| 0
j
J j I= .
Step 3: If =
2
J , then any arbitrary sequence of job lots is optimal, and the optimal
makespan is ,)(
1 3,1,
*
max j
n
j jj
UppC = += stop; otherwise, go to Step 4.
)(max C
)(2 C
1M
2M
2,dC 2,1−dC
)(1 C
BJ DJ AJ
BJ DJ AJ
BJ AJ DJ
Scheduling with lot streaming in a two-machine re-entrant flow shop
159
Step 4: Compute the run-in delays ( jRI and jIR ) and run-out delays ( jRO and
jOR ). Schedule all job lots njjJ ,...,1| == by applying Johnson’s
Algorithm with processing times on 1M and 2M replaced by jRI and jRO
to obtain the job-sequence njj ,...,1| == .
Step 5: In the job-sequence , determine the partition job-lot d such that
,11 ,2 ,21
− =
n
j jd dj
C p U C where
( )
1
,2 1 11,..,
max
−
= ==
= − +
j j
d i ii ij n
C RI RO
( ),21 =
d
jjj
p U , and dddd UpCC 2,2,2,1 −=− .
Step 6: Compute the associated makespan )(max C as:
1
max ,1 ,31 1 11,..,
( ) max , max
n d j
j j j j ij j ij n
C p U p U RI
−
= = ==
= + −
1 1 1
,21 1 ,..,
max
j d j j
i j j i ii j i d i dj d n
RO p U RI RO
− − −
= = = ==
+ + −
,3
n
j jj d
p U
=
+
Step 7: If j
n
j jj
UppC )()(
1 3,1,max = += , then the job-sequence is optimal, stop;
otherwise, go to Step 8.
Step 8: Consider the job lots in ndjjJJ AD ,...,| == , and apply Johnson’s
Algorithm with processing times on 1M and 2M replaced by jIR and jOR
to obtain the partial job-sequence 1,...,1| +−== dnjj .
Step 9: Set the final sequence of job lots as ,= where 1,...,1| −== djj
followed by 1,...,1| +−== dnjj . The associated makespan is
1 1
max ,1 ,31 1 1 11,..,
( ) max , max
n d j j
j j j j ij j i ij n
C p U p U RI
− −
= = = ==
= + −
1 1
,21 ,..,
max
d j j
i j j i ij i d i dj d n
RO p U RI RO
− −
= = ==
+ + − +
,3
n
j jj d
p U
=
4.2.2. Lower bounds on the makespan
We now develop four lower bounds on the makespan, and then we take the
maximum of these lower bounds as a global lower bound, which will be used to test
Algorithm 2.
Lower bound 1. This lower bound is obtained by assuming that there will be no idle
time between the first and the third operations of each job lot on 1M . Thus, the
natural lower bound is
Çetinkaya & Duman /Oper. Res. Eng. Sci. Theor. Appl. 4 (3) (2021) 142-175
160
= +=
n
j jjj
UppLB
1 3,1,1
)( , (1)
which is equivalent to the total processing time of all job lots on 1M .
Lower bound 2. We derive the second lower bound as
( ) ( )j
nj
j
n
j jjnj
ORUpRILB ++=
===
,..,11
2,
,..,1
2 minmin (2)
by assuming that the job lot with the minimum run-in delay for Operation 2 is
processed as the first job-lot in the job-sequence, 2M operates continuously without
any idle time between job lots, and the job lot with the minimum run-out delay for
Operation 3 is processed as the last job lot in the job-sequence.
Lower bound 3. To derive our third lower bound, we assume that all job lots do not
wait for their operations to be performed on 2M . For a sequence , we can
establish the third lower bound as
( ) ( )j
nj
n
ji ii
j
i i
j
i inj
ORUpRILB +
++=
==
−
===
,..,1
2,
1
1
2,1
1,..,1
3 min max (3)
where i is the job-lot in position i of the job-sequence , and
2,1
i
is the
overlapping time for job lot i when both 1M and 2M are busy (i.e., operating
continuously without idle time between sublots), as illustrated in Figure 8.
Figure 8. Run-in and run-out delays
We can rewrite (3) as
1
3 ,2 ,21 1 1,..,1,..,
max ( ) min
j j n
ji i i i i ii i i j j nj n
LB RI p U RO p U RO
−
= = = ==
= + − + +
1 1
,2 ,21 1 1 1,..,1,..,
max min
j j j n
ji i i i i ii i i i j j nj n
RI p U RO p U RO
− −
= = = = ==
= + − + +
1
,21 1 1 1,..,1,..,
max min
j j n
ji i i ii i j j nj n
RI RO p U RO
−
= = = ==
= − + + (4)
Note that the last two terms in (4) are constant and independent from the
sequence, and the first term,
==
j
i inj
RI
1,..,1
max
−
−
=
1
1
j
i i
RO , gives the total idle time
3,2
i
)iRO
iOR
2,1
i
iRI
iIR
31 MM
1M
2M
Scheduling with lot streaming in a two-machine re-entrant flow shop
161
on 2M before completing the second operations of all job lots. The first term equals
Johnson’s expression in which the processing times on 1M and 2M are replaced by
the run-in and run-out delays, respectively. Thus, the job-sequence is obtained by
job-lot k preceding job-lot l if min , min ,k l k lRI RO RO RI .
Therefore, we obtain the third lower bound as
( )( ) j
nj
ORRORIJACLB +=
= ,..,1
*
max3 min, (5)
where ( )( )RORIJAC ,*max is the makespan obtained by Johnson’s Algorithm (JA) with
processing times on 1M and 2M replaced by jRI and jRO , respectively.
Lower bound 4. For any job-sequence , we can establish the fourth lower bound
as
1 2,3
4 ,31 11,.., 1,..,
min max
j j n
j i i iii i i jj n j n
LB RI RI p U
−
= = == =
= + + + (6)
where
3,2
i
is the overlapping time of the second and third operations for job lot
)(i as shown in Figure 8.
Equation (6) can be rewritten as
1
4 ,3 ,31 11,.., 1,..,
min max ( )
j j n
j i i i i i ii i i jj n j n
LB RI RI p U RO p U
−
= = == =
= + + − +
1
,31 1 11,.., 1,..,
min max
j j n
j i i i ii i ij n j n
RI RI RO p U
−
= = == =
= + − + (7)
Note that the second term in (7),
1
1 11,..,
max
j j
i ii ij n
RI RO
−
= ==
− , is minimized
by job-lot k preceding job lot l in the job-sequence if
min , min ,k l k lRI RO RO RI . Therefore, we obtain the fourth lower bound as
( )( )ORIRJACRILB j
nj
+=
=
,min
*
max
,..,1
4 (8)
where ( )( )ORIRJAC ,*max is the makespan obtained by Johnson’s Algorithm with
processing times on 1M and 2M replaced by jIR and jOR , respectively.
The global lower bound GLB becomes the maximum of the lower bounds
developed above. i.e., 1,...,4maxi iGLB LB== .
Example 4. As an illustration of the proposed algorithm and the global lower bound,
we consider the five-job problem in Table 1.
Çetinkaya & Duman /Oper. Res. Eng. Sci. Theor. Appl. 4 (3) (2021) 142-175
162
Table 1. Processing times, number of sublots, and lot sizes
j
1,j
p
2,j
p
3,j
p
j
s
j
U
1 3 2 3 4 40
2 1 2 2 3 30
3 1 2 7 2 20
4 1 4 2 3 70
5 2 2 1 3 35
When all job lots are independently split into their number of consistent sublots,
the sublot sizes and jT and jI values are obtained, as illustrated in Table 2.
Table 2. Sublot sizes with jT and jI values
j
1,j
x
2,j
x
3,j
x
4,j
x
j
T
j
I
1 10 10 10 10 240 0
2 6 12 12 - 90 0
3 5 15 - - 160 0
4 10 40 20 - 330 120
5 14 14 7 - 105 0
Job-lot set J is decomposed into two job-lot sets, 5 ,3 ,2 ,11 =J and 42 =J . We
continue with Step 4 of Algorithm 2 since the job-lot set
2
J is not empty. The run-in
and run-out delays for each job lot are obtained as shown in Table 3.
Table 3. Run-in and run-out delays
j
j
RI
j
RO
j
IR
j
OR
1 30 20 20 30
2 6 24 12 24
3 5 105 10 105
4 10 220 180 40
5 28 28 42 7
The application of Johnson’s Algorithm with processing times on 1M and 2M
replaced by jRI and jRO ; respectively, gives the job-sequence 1 ,5 ,4 ,2 ,3= . The
partition job-lot is job 2, and it is in the second position (i.e., 2=d ) of the sequence
. The associated makespan )(max C for the sequence is computed as 805. The
global lower bound becomes 805,,,max 4321 == LBLBLBLBGLB where
1 ,1 ,31
( ) (3 3)(40) (1 7)(20) (1 2)(70) (2 1)(35) 805
n
j j jj
LB p p U
=
= + = + + + + + + + = ,
( ) ( ) 2 ,211,.., 1,..,min min min 30, 6, 5,10, 28 ((2)(40) (2)(30)== = = + + = + +
n
j j j jjj n j n
LB RI p U RO
(4)(70) (2)(35) min 30, 24,105, 40, 7 542+ + + = ,
( )( ) ( ) ( ) * *3 max max
1,..,
, min 4 2 3 1 5 min 30, 24,105, 40, 7
=
= + = − − − − +
j
j n
LB C JA RI RO RO C
Scheduling with lot streaming in a two-machine re-entrant flow shop
163
535 7 542= + = ,
( )( ) ( )* *4 max max
1,..,
min , min 30, 6, 5,10, 28 3 1 4 2 5
=
= + = + − − − −
j
j n
LB RI C JA RI RO C
5 560 565= + = .
The job-sequence 1 ,5 ,4 ,2 ,3= is optimal since the associated makespan equals
the natural lower bound 1LB . Thus, we stop.
4.2.3. Computational experiments and results
The efficiency measure of Algorithm 2 is the computational time required to solve
the problem. However, its computational time is not measured provided since it is
relatively very short, less than a few seconds. On the other hand, to test the
effectiveness of Algorithm 2, we generate the parameters for our problem instances
as follows:
n : number of job lots , 5,10,15, 20, 25,50, 75,100n .
,j k
p : k th operation’s processing time for job lot j is randomly generated form from
a discrete uniform distribution over 1, 10, including the lower and upper
limits.
j
s : number of sublots for any job lot j is randomly generated form from a discrete
uniform distribution over 2, 10.
j
U : lot size for any job lot j is randomly generated form from a discrete uniform
distribution over 2, 50.
For each possible number of job lots from 5 to 100, we first generate 100 problem
instances in which the. The processing times for all operations are randomly
distributed without any dominance of a specific operation, and a total of 800
problem instances are tested. The following statistics are collected:
Z
NT = number of times percent deviation is zero (i.e., the heuristic makespan
equals the global lower bound).
]1,0(NT = number of times the percent deviation is greater than zero but less than or
equal to 1 (i.e., GLBC
H
01.1max ).
AVE = average percent deviation.
MAX = maximum percent deviation.
From the results of our experiments, we observed that Algorithm 2 finds the
optimum makespan (i.e., the heuristic makespan equals the global lower bound) for
all 800 test problems when all processing times are randomly generated without any
dominance of a specific operation. That is, 800
Z
NT = .
However, to evaluate the effectiveness of Algorithm 2 when the same operation
for all job lots is dominant, we repeated our computational experiments with three
data sets. The first data set, D1, assumes that the maximum processing time is on the
first operation for all job lots, i.e., 3,2,1, ,max jjj ppp for j . Similarly, the second
Çetinkaya & Duman /Oper. Res. Eng. Sci. Theor. Appl. 4 (3) (2021) 142-175
164
and third data sets D2 and D3 correspond to the cases where ,2 ,1 ,3max ,j j jp p p
and ,3 ,1 ,2max ,j j jp p p for j , respectively.
In each of the data sets, we assume that the processing time of the dominant
operation for each job-lot is randomly generated form from a discrete uniform
distribution over 6, 10, and the processing times of the other operations are
randomly generated form from a discrete uniform distribution over 1, 5. Our
experiments with data sets D2 and D3 show that the global lower bound equals the
heuristic makespan in all 800 problem instances tested when either the first or third
operation is dominant. This result means that the global lower bound is effective
when the first or third operation is dominant. However, the same argument is not
valid for the case, where the second operation is dominant, since the global lower
bound equals the heuristic makespan in 336 problem instances out of 800, as
illustrated in Table 4.
From Table 4, it is clear that the heuristic makespan deviates 1 percent from the
global lower bound in 790 problem instances out of 800 for the case where the
second operation is dominant. In the remaining ten problem instances when 5n = ,
the average and maximum deviations from the global lower bound are 0.352 percent
and 2.055 percent, respectively. It should also be noticed that the average and
maximum deviations decrease as the number of jobs increases.
Table 4. Performance of Algorithm 2 when the second operation is dominant
n NPIS ZNT ]1,0(NT AVE MAX
5 100 45 45 0.352 2.055
10 100 30 70 0.136 0.656
15 100 40 60 0.076 0.569
20 100 37 63 0.050 0.231
25 100 36 64 0.036 0.116
50 100 37 63 0.014 0.044
75 100 58 42 0.006 0.026
100
100 53 47 0.005 0.021
Given the results of our computational experiments, we conclude that Algorithm
2 is quite effective in solving the multi-job problem where Machine 1 is the primary
machine.
5. Conclusions and future research
In this study, we considered a problem in a two-machine re-entrant flow shop in
which lot streaming is used for scheduling the single-job and multi-job cases
separately. When Machine 1 or Machine 2 is the primary machine on which the third
operation is performed, we proved that the single-job problem is polynomial-time
solvable. We have also proved that the multi-job problem can be solved optimally
when the third operation is performed on Machine 2. However, we have also proved
that the multi-job problem is NP-hard when Machine 1 is the primary machine,
machine so that we have developed a simple heuristic algorithm. To examine the
effectiveness of our algorithm, we have developed a global lower bound on the
Scheduling with lot streaming in a two-machine re-entrant flow shop
165
makespan. The results of our computational experiments imply that our heuristic
algorithm is quite effective in solving the multi-job problem optimally in reasonably
short computational times.
Our study has some limiting assumptions for the problem under study. As in most
studies in the lot streaming literature, we assume that the number of sublots of each
job lot is known in advance. However, a more realistic case is when the problem’s
solution has to give its value along with the sublot sizes.
In our study, as in almost all of the previous studies in the literature, we assume
that sublots in each job lot should be processed successively for each operation on
each machine. i.e., we do not allow the intermingling of the job lots for the multi-job
case. We may or may not obtain a better schedule by relaxing this assumption, but it
is worth investigating.
Furthermore, in our study, sublot sizes may not be integral, so rounding them to
the nearest integer numbers without violating the job-lot size may be needed.
However, this approach may not provide the optimal makespan. Thus, this issue is
also worthy of investigating.
Through our study for two machine and re-entrant flowshops, we hope that
researchers working on scheduling problems will be aware that there is no study
other than ours for scheduling with lot streaming in re-entrant manufacturing
systems. Our study will open a new direction in the literature of scheduling with lot
streaming since it is the only study that applies lot streaming for single- and multi-
job cases in the re-entrant flow shops. We hope that our work will form a basis for
developing algorithms to solve the scheduling problems in more complex re-entrant
manufacturing systems where lot streaming is allowed.
There are several research extensions of this study that are open for future
investigation:
• The assumption of knowing the number of sublots in advance could be
relaxed, and investigating the problem under consideration without this assumption
could be a future study issue.
• The sublot sizes obtained for the no-setup case studied in this paper may not
be valid for the setup case The so that problem under consideration can be extended
to a case where an issue with attached or detached setup is made before processing a
job-lot.
• Our study assumes that sublots in each job-lot should be processed
successively for each operation on each machine. i.e., we do not allow the
intermingling of the job lots for the multi-job case. Relaxing this the no-intermingling
assumption could be another future research issue.
• Our study could also be extended to the flow shops with more than two
stages, having one machine at each stage, and a job lot may visit some stages more
than once. and hybrid flow shops, which are the flow shops in which at least one of
the stages has more than one machine, could also be studied.
• Different measures of performance rather than makespan could also be
considered. For instance, the total completion time of sublots and job lots in the
Çetinkaya & Duman /Oper. Res. Eng. Sci. Theor. Appl. 4 (3) (2021) 142-175
166
single- and multi-job cases, respectively, could be a more relevant performance
measure than makespan if the inventory holding costs are minimized.
Appendix A.
Proof of Theorem 1. As illustrated in the network representation given in Figure 1,
a lower bound on the makespan
max
C , which is based on the first sublot, is given as
the first sublot’s processing time on 1M plus the total processing time of all sublots
on 2M , i.e., max 1 1 1 2 3 1 2( )( ... )sC LB p x p p x x x = + + + + + . Similarly, the total
processing time of sublots 1 and 2 plus the total processing time of sublots 2 through
s gives another lower bound, i.e.,
max 2 1 1 2 2 3 2 3
( ) ( )( ... )
s
C LB p x x p p x x x = + + + + + + .
Similarly, we can write
max 1 2 31
( )
i s
i k kk k i
C LB p x p p x
= =
= + + for each sublot
si ,...,2= . It follows that max 1 2 311
1
max max ( )
i s
i k kk k ii s
i s
C LB p x p p x
= =
= + + . Thus,
the linear programming model below can formulate the single-job problem where
2M is the primary machine.
( P ) Minimize maxC (A.1)
Subject to max 1 2 31 ( )
i s
k kk k i
C p x p p x
= =
+ + for si ,...,2= (A.2)
1
s
ii
x U
=
= (A.3)
max 0C (A.4)
0ix for si ,...,2= (A.5)
Assuming that each of the inequalities in (A.2) is satisfied as equality, i.e., all
sublots are critical to determining the makespan maxC ; we can obtain a feasible
solution to problem P . In such a case, both 1M and 2M operate without idle time
from one sublot to another, and the adjacent pair of sublots must satisfy the
following relationship:
1
1 2 3 1 2 31 1 1
( ) ( )
i s i s
k k k kk k i k k i
p x p p x p x p p x
−
= = = = −
+ + = + + for si ,...,2= (A.6)
or equivalently,
( )1 2 3 1/i ix x p p p−= + for si ,...,2= (A.7)
The idle time on 2M is only before the first sublot, and it equals 11xp . Then
solving the set of simultaneous equations (A.3) and (A.7) yields
)...1/(
12
1
−
++++=
s
Ux , (A.8)
1
1
xx
i
i
−
= for si ,...,2= (A.9)
where ( ) 132 / ppp += .
Scheduling with lot streaming in a two-machine re-entrant flow shop
167
Using (A.2), (A.3), (A.8) and (A.9), the makespan is obtained as
2 1
max 1 1 2 3 1 2 31
( ) ( / (1 ... ) ( ))
s s
ii
C p x p p x p p p U
−
=
= + + = + ++ + + + + . (A.10)
We have shown that the solution given by the theorem is feasible. Note that this
solution is the solution for the single-job lot streaming problem in the two-machine
flow shop with processing times
1
p and
2 3
p p+ on 1M and 2M , respectively.
Now, to prove the optimality of this feasible solution, the problem P may be re-
written as
( P ) Maximize maxC− (A.11)
Subject to
max 1 2 31
( ) 0
i s
k kk k i
C p x p p x
= =
− + + + for si ,...,2= (A.12)
1
s
ii
x U
=
= (A.4)
max 0C , 0ix for si ,...,2= (A.5)
The dual of ( P ) is constructed as
( D ) Minimize 0 U y (A.13)
Subject to
1 2 3 01 1
( ) 0
s i
k kk k
p y p p y y
= =
+ + − for si ,...,2= (A.14)
1
1
s
ii
y
=
− − (A.15)
0
i
y for si ,...,2= (A.16)
0
y unrestricted in sign (A.17)
We can find a feasible solution to problem D by assuming that all constraints
defined in the dual problem D are satisfied as equalities. It follows that a feasible
solution to problem D is achieved when
1
1 2 3 1 2 31 1 1 1
( ) ( )
s i s i
k k k kk k k i k
p y p p y p y p p y
−
= = = − =
+ + = + + for 2,...,i s= (A.18)
or equivalently,
1 1 2 3
/ ( )
i i
y y p p p
−
= + for 2,...,i s= . (A.19)
Solving the set of equations in (A.18) and
1
1
ii s
y
= simultaneously yields
1 2 1
1
(1 / (1 ... ))
s s
y
− −
= + ++ + + , (A.20)
1
1
i
i
y y
−
= for 2,...,i s= , (A.21)
2 1
0 1 2 3
/ (1 ... ) ( )
s
y p p p
−
= + + + + + + + (A.22)
where ( ) 132 / ppp += .
Çetinkaya & Duman /Oper. Res. Eng. Sci. Theor. Appl. 4 (3) (2021) 142-175
168
The objective function of the dual problem 1D is obtained as
2 1
0 1 2 3
( /(1 ... ) ( ))
s
U y p p p U
−
= + + + + + + . (A.23)
From equations (A.10) and (A.23), it is clear that the problem P and its dual D
have the same objective function values. Thus, from the duality theory, it follows that
equations (A.8)-(A.10) and (A.20)-(A.22) are the optimal solutions to the primal and
dual problems, respectively. Therefore, we can conclude that the sublot sizes given in
the theorem statement are optimal for the single-job problem where 2M is the
primary machine on which the third operation is performed. ■
Appendix B.
Proof of Theorem 3. For a job sequence , let
[j] = job lot sequenced in the j th position of the sequence ,
jU = lot size of job lot [j],
j
s = number of sublots of job lot [j],
i = index for sublots ( 1,..., ji s= ),
,j ix = size of the i th sublot in job lot [j],
k = index for machines ( 1, 2, 3k = ),
,j kp = item (unit) processing time for the k th operation of job lot [j],
, ,j i kC = completion time of the k th operation for the i th sublot of job lot [j],
jRI = time lag between the start of the first operation on 1M and the latest start
time of the second operation on 2M for job lot [j],
jRO = time lag between the completion times of the first and the third operations
for job lot [j].
The completion time of the first operation for the i th sublot of job lot [j] is given
by
1, ,1 , ,1 ,1 ,1j
i
j i j s j j rr
C C p x
− =
= + for 1, 2,..., ji s= (B.1)
where 00 , ,1
0
s
C = . From equation (B.1), the completion time for the first operation
of job lot [j], which is the completion time of the last sublot in this job on 1M , is
obtained as
1 1, ,1 1 ), ,1 ,1 , 1 , ,1 ,11
j
j j j
s
j s j s j j i j s j ji
C C p x C p U
− −
− −=
= + = + . (B.2)
The completion time of the third operation for the first sublot of job lot [j] on 2M
is expressed as
1,1,3 ,1,1 1 , ,3 ,2 ,1 ,3 ,1max , jj j j s j j j jC C C p x p x−−= + +
Scheduling with lot streaming in a two-machine re-entrant flow shop
169
1,1,1 1 , ,3 ,2 ,3 ,1max , ( )jj j s j j jC C p p x−−= + + . (B.3)
Substituting ,1,1jC value from (B.2) into (B.3) yields
1 1,1,3 1 , ,1 ,1 ,1 1 , ,3 ,2 ,3 ,1max , ( )j jj j s j j j s j j jC C p x C p p x− −− −= + + + . (B.4)
Similarly, we may obtain the completion time of the third operation for the
second sublot of job lot [j] on 2M as
1 1
1
,2,3 1 , ,1 ,1 , ,2 ,3 , 1 , ,31 11 2
max max ( ) ,
j j
i i
j j s j j r j j j r j sr ri
C C p x p p x C
− −
−
− −= =
= + − +
2
,2 ,3 ,1
( )
j j j ii
p p x
=
+ + (B.5)
Repeating the process yields the completion time for the last operation of job lot
[j], which is the completion time of the last sublot of this job lot on 2M ,
1
1
, ,3 1 , ,1 ,1 , ,2 ,3 ,1 11
max max ( ) ,
j j
j
i i
j s j s j j r j j j rr ri s
C C p x p p x
−
−
− = =
= + − +
1
1 , ,3 ,2 ,3 ,1
( )j
j
s
j s j j j ii
C p p x
−
− =
+ +
1
1
1 , ,1 ,1 , ,2 ,3 ,1 11
max max ( ) ,
j
j
i i
j s j j r j j j rr ri s
C p x p p x
−
−
− = =
= + − +
11 , ,3 ,2 ,3( )jj s j j jC p p U−− + + (B.6)
By successive application of (B.6) using (B.2), the time to complete the last job lot
processed on 2M , , ,3nn s
C , is obtained as follows:
1
max, ,3 ,2 ,31 1 11
max ( )
n
w w n
n s j j j j jj j jw n
C C RI RO p p U
−
= = =
= = − + + (B.7)
where
1
,1 , ,2 ,3 ,1 11
max ( )
j
i i
j j j r j j j rr ri s
RI p x p p x
−
= =
= − + , (B.8)
1
,1 , ,2 ,3 , ,2 ,3 ,11 11
max ( ) ( )
j
i i
j j j r j j j r j j j j jr ri s
RO p x p p x p p U p U
−
= =
= − + + + −
,2 ,3( )j j j j jRI p p p U= + + − (B.9)
Note that the second part, ,2 ,31 ( )
n
j j jj
p p U
=
+ , in (B.7) giving the makespan
value is a constant so that it is enough to minimize the first part,
1
1 11
max
w w
j jj jw n
RI RO
−
= =
− , which is equivalent to the total idle time on 2M . Note
that the first part is similar to Johnson’s expression, where the processing times on
1M and 2M are replaced by the run-in and run-out delays, respectively. Therefore,
Çetinkaya & Duman /Oper. Res. Eng. Sci. Theor. Appl. 4 (3) (2021) 142-175
170
job v precedes job z in an optimal schedule of job lots when min , minv zRI RO
,z vRI RO . ■
Appendix C.
Proof of Theorem 4. It is clear that the minimizing the first term in (B.7),
1
,1 , ,2 ,3 ,1 11
max ( )
j
i i
j j r j j j rr ri s
p x p p x
−
= =
− + , minimizes the makespan for a
given sequence of job lots. In other words, sublot sizes minimizing the makespan for
any arbitrary sequence (hence the optimal sequence) are identical to those sublot
sizes which are determined by solving the sublot-sizing problem for each job lot
separately. Therefore, the following linear programming model should be solved for
every job lot in position [j]:
Minimize jZ (C.1)
Subject to
1
,1 , ,2 ,3 ,1 1
( )
i i
j j j r j j j rr r
Z p x p p x
−
= =
− + for 1, 2,..., ji s= (C.2)
,1
j
s
j i ji
x U
=
= (C.3)
, 0j ix for 1, 2,..., ji s= . (C.4)
The optimal solution to this model is trivial due to its special structure. The
minimum value of the objective function jZ is achieved when ,1 ,1j j jZ p x= and
the constraints in (C.2) are satisfied as equalities. Thus, the sublot sizes must be
1
, , 1 ,2 ,3 ,1 ,1 ,2 ,3 ,1
( ) / (( ) / )
i
j i j i j j j j j j j
x x p p p x p p p
−
−
= + = + for 2,..., ji s= . (C.5)
Substituting (C.5) into (C.3) yields
12
,1
/ (1 ... )
j
s
j j
x U
−
= + + + + , (C.6)
1
, ,1
i
j i j
x x
−
= for 2,..., ji s= (C.7)
where ,2 ,3 ,1( ) /j j jp p p = + .
Note that (C.6) and (C.7) are the same expressions as given in Section 3 for the
single-job problem, and substituting (C.6) and (C.7) into (B.8) and (B.9) yields
1
,1 , ,2 ,3 , ,1 ,11 11
max ( )
j
i i
j j j r j j j r j jr ri s
RI p x p p x p x
−
= =
= − + =
12
,1
/ (1 ... )
j
s
j j
p U
−
= + + + + , (C.8)
,2 ,3( )j j j j j jRO RI p p p U= + + − . (C.9)
Scheduling with lot streaming in a two-machine re-entrant flow shop
171
Acknowledgements: We would like to thank the editor and anonymous referees for
their valuable comments and suggestions that helped us to improve the quality and
presentation of this paper.
References
Alfieri, A., Glass, C. A., & van de Velde, S. L. (2012). Lot streaming in a two-machine
flow shop with attached setup times. IIE Transactions, 44(8), 695–710.
https://doi.org/10.1080/0740817X.2011.649384
Alfieri, A., Zhou, S., Scatamacchia, R., & van de Velde, S. L. (2021). Dynamic
programming algorithms and Lagrangian lower bounds for a discrete lot streaming
problem in a two-machine flow shop. 4OR, 19(2), 265–288.
https://doi.org/10.1007/s10288-020-00449-8
Baker, K. R. (1988). Lot streaming to reduce cycle time in a flow shop, Working
Paper, The Amos Tuck School of Business Administration, Dartmouth College,
Hanover, NH, USA.
Baker, K. R. (1995). Lot streaming in the two-stage flow shop with setup times.
Annals of Operations Research, 57(1), 1–11. https://doi.org/10.1007/BF02099687
Buscher, U. & Shen, L. (2009). An integrated tabu search algorithm for the lot
streaming problem in job shops. European Journal of Operational Research, 199(2),
385–399. https://doi.org/10.1016/j.ejor.2008.11.046
Çetinkaya, F. C. (1994). Lot streaming in a two-stage flow shop with set-up,
processing and removal times separated. Journal of Operational Research Society,
45(12), 1445–1455. https://doi.org/10.1057/jors.1994.221
Çetinkaya, F. C. (2005). Unit sized transfer batch scheduling in an automated two-
machine flow-line cell with one transport agent. International Journal of Advanced
Manufacturing Technology, 29(1–2), 178–183. https://doi.org/10.1007/s00170-
004-2493-9
Çetinkaya, F. C., & Kayalıgil, M. S. (1992). Unit sized transfer batch scheduling with
setup times. Computers & Industrial Engineering, 22(2), 177–183.
https://doi.org/10.1016/0360-8352(92)90045-L
Çetinkaya, F. C., & Duman, M. (2010). Lot streaming in a two-machine mixed shop.
International Journal of Advanced Manufacturing Technology, 49(9–12), 1161–1173.
https://doi.org/10.1007/s00170-009-2473-1
Chang, J. H., & Chiu, H. N. (2005). A comprehensive review of lot streaming.
International Journal of Production Research, 43(8), 1515–1536.
https://doi.org/10.1080/00207540412331325396
Chen, J., & Steiner, G. (1997). Lot streaming with detached setups in three-machine
flow shops. European Journal of Operational Research, 96(3), 591–611.
https://doi.org/10.1016/S0377-2217(96)00091-4
Chen, J., & Steiner, G. (1998). Lot streaming with attached setups in three-machine
flow shops. IIE Transactions, 30(11), 1075–1084.
https://doi.org/10.1023/A:1007563814941
Çetinkaya & Duman /Oper. Res. Eng. Sci. Theor. Appl. 4 (3) (2021) 142-175
172
Cheng, M., Mukherjee, N. J., & Sarin, S. C. (2013). A review of lot streaming.
International Journal of Production Research, 51(23–24), 7023–7046.
https://doi.org/10.1080/00207543.2013.774506
Cheng, M., & Sarin, S. C. (2020). Lot streaming in a two-stage assembly system.
Annual Reviews in Control, 50(23–24), 303–316.
https://doi.org/10.1016/j.arcontrol.2020.08.004
Cheng, M., Sarin, S.C., & Singh, S. (2016). Two-stage, single-lot, lot streaming problem
for a 1+2 hybrid flow shop. Journal of Global Optimization, 66(2), 263–290.
https://doi.org/10.1007/s10898-015-0298-z
Davendra, D., Senkerik, R., Zelinka, I., Pluhacek, M., & Bialic-Davendra, M. (2014).
Utilising the chaos-induced discrete self organising migrating algorithm to solve the
lot-streaming flowshop scheduling problem with setup time. Soft Computing, 18(4),
669–681. https://doi.org/10.1007/s00500-014-1219-7
Defersha, F. M., & Chen, M. (2010). A hybrid genetic algorithm for flowshop lot
streaming with setups and variable sublots. International Journal of Production
Research, 48(6), 1705–1726. https://doi.org/10.1080/00207543.2011.574952
Defersha, F. M. (2011). A comprehensive mathematical model for hybrid flexible
flowshop lot streaming problem. International Journal of Industrial Engineering
Computations, 2(2), 283–294. https://doi.org/ 10.5267/j.ijiec.2010.07.006
Defersha, F. M., & Chen, M. (2012a). Mathematical model and parallel genetic
algorithm for hybrid flexible flowshop lot streaming problem. The International
Journal of Advanced Manufacturing Technology, 62(1–4), 249–265.
https://doi.org/10.1007/s00170-011-3798-0
Defersha, F. M., & Chen, M. (2012b). Jobshop lot streaming with routing flexibility,
sequence-dependent setups, machine release dates and lag time. International
Journal of Production Research, 50(2), 2331–2352.
https://doi.org/10.1080/00207543.2011.574952
Feldmann, M., & Biskup, D. (2008). Lot streaming in a multiple product permutation
flow shop with intermingling. International Journal of Production Research, 46(1),
197–216. https://doi.org/10.1080/00207540600930065
Glass, C. A., Possani, E. (2011). Lot streaming multiple jobs in a flow shop.
International Journal of Production Research, 49(9), 2669–2681.
https://doi.org/10.1080/00207543.2010.532935
Gomez-Gasquet, P., Segura-Andres, R., & Andres-Romano, C. (2013). A review of lot
streaming in a flow shop environment with makespan criteria. Journal of Industrial
Engineering and Management, 6(3), 761–770. http://dx.doi.org/10.3926/jiem.553
Johnson, S. M. (1954). Optimal two and three-stage production schedules with setup
times included. Naval Research Logistics Quarterly, 1(1), 61–68.
https://doi.org/10.1002/nav.3800010110
Kim, J. S., Kang, S. H., & Lee, S. M. (1997). Transfer batch scheduling for a two-stage
flowshop with identical parallel machines at each stage. Omega-International Journal
of Management Science, 25(5), 547–555. https://doi.org/10.1016/S0305-
0483(97)00015-7
Lev, V., & Adiri, I. (1984). V-shop scheduling. European Journal of Operational
Research, 18(1), 51–56. https://doi.org/10.1016/0377-2217(84)90260-1
Scheduling with lot streaming in a two-machine re-entrant flow shop
173
Li, J. Q., Tao, X. R., Jia, B. X., Han, Y. Y., Liu, C., Duan, P. Zheng, Z. X., & Sanga, H. Y.
(2020). Efficient multi-objective algorithm for the lot-streaming hybrid flowshop
with variable sub-lots. Swarm and Evolutionary Computation, 5, Article 100600.
https://doi.org/10.1016/j.swevo.2019.100600
Liu, J. (2008). Single-job lot streaming in m-1 two-stage hybrid flowshops. European
Journal of Operational Research, 187(3), 1171–1183.
https://doi.org/10.1016/j.ejor.2006.06.066
Marimuthu, S., Ponnambalam, S. G., Jawahar, N. (2008). Evolutionary algorithms for
scheduling m-machine flow shop with lot streaming. Robotics and Computer-
Integrated Manufacturing, 24(1), 125–139.
https://doi.org/10.1016/j.rcim.2006.06.007
Marimuthu, S., Ponnambalam, S. G., Jawahar, N. (2009). Threshold accepting and Ant-
colony optimization algorithms for scheduling m-machine flow shops with lot
streaming. Journal of Materials Processing Technology, 209(2), 1026–1041.
https://doi.org/10.1016/j.jmatprotec.2008.03.013
Martin, C. H. (2009). A hybrid genetic algorithm/mathematical programming
approach to the multi-family flowshop scheduling problem with lot streaming.
Omega, 37(1), 126–137. https://doi.org/10.1016/j.omega.2006.11.002
Meng, T., Pan, Q. K., Li, J. Q., & Sang, H. Y. (2018). An improved migrating birds
optimization for an integrated lot-streaming flow shop scheduling problem. Swarm
and Evolutionary Computation, 38, 64–78.
https://doi.org/10.1016/j.swevo.2017.06.003
Naderi, B, & Yazdani, M. (2015). Modelling and Scheduling Lot Streaming Flexible
Flow Lines. Journal of Optimization in Industrial Engineering, 8(18), 61–69.
http://www.qjie.ir/article_221.html
Nejati, M., Mahdavi, I., Hassanzadeh, R., & Mahdavi-Amiri, N. (2016). Lot streaming in
a two-stage assembly hybrid flow shop scheduling problem with a work shift
constraint. Journal of Industrial and Production Engineering, 33(7), 459–471.
https://doi.org/10.1080/21681015.2015.1126653
Pan, Q. K., Tasgetiren, M. F., Suganthan, P. N., & Chua, T. J. (2011). A discrete artificial
bee colony algorithm for the lot-streaming flow shop scheduling problem.
Information sciences, 181(12), 2455–2468.
https://doi.org/10.1016/j.ins.2009.12.025
Potts, C. N., & Baker, K. R. (1989). Flow shop scheduling with lot streaming.
Operations Research Letters, 8(6), 297–303. https://doi.org/10.1016/0167-
6377(89)90013-8
Pranzo, M. (2004). Batch scheduling in a two-machine flow shop with limited buffer
and sequence independent setup times and removal times. European Journal of
Operational Research, 153(3), 581–592. https://doi.org/10.1016/S0377-
2217(03)00264-9
Reither, S. (1966). A system for managing job shop production. Journal of Business,
39(3), 371–393.
Rossit, D., Tohmé, F., Frutos, M., Bard, J & Broz, D. (2016). A non-permutation
flowshop scheduling problem with lot streaming: A Mathematical model.
Çetinkaya & Duman /Oper. Res. Eng. Sci. Theor. Appl. 4 (3) (2021) 142-175
174
International Journal of Industrial Engineering Computations, 7(3), 507–516.
https://doi.org/ 10.5267/j.ijiec.2015.11.004
Salazar-Moya, A., & Garcia, M. V. (2021). Lot Streaming in Different Types of
Production Processes: A PRISMA Systematic Review. Designs, 5(4), 67.
https://doi.org/10.3390/designs5040067
Sarin, S. C., & Jaiprakash, P. (2007). Flow shop lot streaming. Springer.
http://dx.doi.org/10.1007/978-0-387-47688-9
Sarin, S. C., Yao, L., & Trietsch, D. (2011). Single-batch lot streaming in a two-stage
assembly system. International Journal of Planning and Scheduling, 1(1–2), 90–108.
https://doi.org/10.1504/IJPS.2011.044604
Sriskandarajah, C., & Wagneur, E. (1999). Lot streaming and scheduling multiple
products in two-machine no-wait flow shops. IIE Transactions, 31(8), 695–707.
https://doi.org/10.1023/A:1007643210135
Şen, A., & Benli, Ö. S. (1999). Lot streaming in open shops. Operations Research
Letters, 23(3–5), 135–142. https://doi.org/10.1016/S0167-6377(98)00026-1
Trietsch, D. (1989). Polynomial transfer lot sizing techniques for batch processing on
consecutive machines. Working Paper, Naval Postgraduate School, Monterey,
California, USA. https://core.ac.uk/download/pdf/36722285.pdf
Trietsch, D., & Baker, K. R. (1993). Basic techniques for lot streaming. Operations
Research, 41(6), 1065–1076. https://doi.org/10.1287/opre.41.6.1065
Tseng, C. T., & Liao, C. J. (2008). A discrete particle swarm optimization for lot-
streaming flowshop scheduling problem. European Journal of Operational Research,
191(2), 360–373. https://doi.org/10.1016/j.ejor.2007.08.030
Vickson, R. G. (1995). Optimal lot streaming for multiple products in a two-machine
flow shop. European Journal of Operational Research, 85(3), 556–575.
https://doi.org/10.1016/0377-2217(93)E0366-6
Vickson, R. G., & Alfredson, B. E. (1992). Two-and three-machine flow shop
scheduling problems with equal sized transfer batches. International Journal of
Production Research, 30(7), 1551–1574.
https://doi.org/10.1080/00207549208948107
Wang, M., Sethi. S. P., & Van De Velde, S. L. (1997). Minimizing makespan in a class of
re-entrant shops. Operations Research, 45(5), 702–712.
https://doi.org/10.1287/opre.45.5.702
Wang, S., (1997). Minimizing makespan in a class of re-entrant shops. Operations
Research, 45(5), 702–712. https://doi.org/10.1287/opre.45.5.702
Wang, S., Kurz, M., Mason, S. J., & Rashidi, E. (2019). Two-stage hybrid flow shop
batching and lot streaming with variable sublots and sequence-dependent setups.
International Journal of Production Research, 57(22), 6893–6907.
https://doi.org/10.1080/00207543.2019.1571251
Yang, D. L., & Chern, M. S. (2000). Two-machine flowshop group scheduling problem.
Computers & Operations Research, 27(10), 975–985.
https://doi.org/10.1016/S0305-0548(99)00070-2
Yao, L., & Sarin, S. C. (2014). Multiple-lot, lot streaming in a two-stage assembly
system. Essays in production, project planning and scheduling (pp. 357–388).
Springer. https://doi.org/10.1007/978-1-4614-9056-2_15
Scheduling with lot streaming in a two-machine re-entrant flow shop
175
Yoon, S. H., & Ventura, J. A. (2002). An application of genetic algorithms to lot-
streaming flow shop scheduling. IIE Transactions, 34(9), 779–787.
https://doi.org/10.1080/07408170208928911
Zhang, B., Pan, Q. K., Gao, L., Zhang, X. L., Sang, H. Y., & Li, J. Q. (2017). An effective
modified migrating birds optimization for hybrid flowshop scheduling problem with
lot streaming. Applied Soft Computing, 52, 14–27.
https://doi.org/10.1016/j.asoc.2016.12.021
Zhang, W., Liu, J., & Linn, R. J. (2003). Model and heuristics for lot streaming of one
job in m-1 hybrid flowshops. International Journal of Operations and Quantitative
Management, 9(1), 49–64. http://www.ijoqm.org/v9no1.asp
Zhang, W., Yin, C., Liu, J., & Linn, R. J. (2005). Multi-job lot streaming to minimize the
mean completion time in m–1 hybrid flowhops. International Journal of Production
Economics, 96(2), 189–200. https://doi.org/10.1016/j.ijpe.2004.04.005
© 2021 by the authors. Submitted for possible open access publication under the
terms and conditions of the Creative Commons Attribution (CC BY)
license (http://creativecommons.org/licenses/by/4.0/).