Order allocation in a multi-supplier environment: review of the literature since 2007

A review of lot streaming in a flow shop environment
with makespan criteria

Pedro Gómez-Gasquet, Rubén Segura-Andrés, Carlos Andrés-Romano

Centro de Investigación de Gestión e Ingeniería de la Producción, Universitat Politècnica de València (Spain)

Received: September 2012

Accepted: March 2013

Gómez-Gasquet, P., Segura-Andrés, R., & Andrés-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



Purpose: This paper reviews current literature and contributes a set of findings that capture the current state-of-the-art of the topic of lot streaming in a flow-shop.

Design/methodology/approach: A literature review to capture, classify and summarize the main body of knowledge on lot streaming in a flow-shop with makespan criteria and, translate this into a form that is readily accessible to researchers and practitioners in the more mainstream production scheduling community.

Findings: The existing knowledge base is somewhat fragmented. This is a relatively unexplored topic within mainstream operations management research and one which could provide rich opportunities for further exploration.

Originality/value: This paper sets out to review current literature, from an advanced production scheduling perspective, and contributes a set of findings that capture the current state-of-the-art of this topic.

Keywords: flow shop, lot streaming, makespan, review, solution methods


1. Introduction

In the last sixty years thousands of papers have dealt with different scheduling issues related to flow shops configurations, and many others in its different variations. Most of these works have always been considered hypothesis, where jobs were not split. At the end of last century, and consolidated in the last decade, there arose a great interest in considering scenarios where the lots could be divided, that is what we call lot streaming. It seems clear that if it is possible, lot streaming minimize Cmax. However, the difficulty in the resolution with this approach has, so far, prevented it can be considered a consolidated approach.

In the following section notation and structure of the problem will be presented, section 1.3 will review the two-machine cases, that are the basis to understand different approaches and to address more complex problems, such as those reviewed in section 1.4. And finally, section 1.5 discusses the techniques used to obtain the different solutions.

2. Notation

This paper is focus on flow shop problems where the number of stages and machines are the same; no multiple resources are available in any stage. All the reviewed flow shop lot streaming (FSLS) papers are presented on tables. These tables follow a modified notation of one previously published (Sarin & Jaiprakash, 2007): {No. of machines}/{no. of jobs}/{sublot type}/{idling}/{sublot sizes}/{setup, special features}

As we only deal with flow shop problems, we only specify the number of ma-chines on it (2, 3 or N). Number of jobs may be single job (1) or multiple jobs (N). Sublot types may refer to equal (E), consistent (C) and variable (V). Intermittent idling (II) or no-idling (NI) will be also specified. Real numbers will be expressed in continuous values (CV) and integer sublots in discrete values (DV). For setup times, if no setup time is considered (No-ST), if it is considered (ST) or if it is sequence dependent (SDST). Special features include conditions such as no-wait condition (No-wait), when it is considered removal times (RemT) or transportation times (TransT) or even when interleaving is allowed (Interleaving). Makespan is considered implicitly in all cases reviewed.

3. Lot Streaming in two-stage flow shop

The 2/*/E problem, with one or n jobs, it could be regarded as a simple sequence problem of equal sublots, using Johnson’s rule (Johnson, 1954) to find the optimal sequences in the two-machine. As it may be observed on Table 1.1, only three problems have been founded. A single job problem with discrete values but not using setup times (Sen, Topaloglu & Benli, 1998). Other paper proposed an n job problem with continuous values (Vickson & Alfredsson, 1992). Further analytical research was performed over the previous paper and sublot-attached setup times were incorporated into the model (Baker, 1995). Other authors considered setup times on the problem (Cetinkaya & Kayaligil, 1992; Kalir & Sarin, 2003).

For the 2/1/C using consistent sublots, the objective is to simply determine the optimal sublot sizes for all the machines. First paper on the matter with continuous values indicated when it was convenient the use of them (Potts & Baker, 1989). Later on, different forms of the problem existing in the literature were reviewed and some important structural insights were generalized using both, continuous and discrete values (Trietsch & Baker, 1993). Years later, a paper was presented for determining both, number of sublots and sublot sizes for a single job problem, and also for the n job one, considering setup times and a no-wait flowshop (Sriskandarajah & Wagneur, 1999). Previously, an analytical solution was provided using discrete values, to the problem when no setup times were considered (Sen et al., 1998). Other authors used a network representation to analyze the structure of the optimal sublot allocation (Chen & Steiner, 1999). They proposed an efficient solution method based on the structural properties giving discrete results.






Sen et al., 1998


Potts & Baker, 1989


Vickson & Alfredsson, 1992

2/N/C/II/CV/{ST, RemT}

Cetinkaya, 1994


Cetinkaya & Kayaligil, 1992

Baker, 1995

Kalir & Sarin, 2003


Vickson, 1995

2/N/C/II/CV/{ST, No-wait}

Sriskandarajah & Wagneur, 1999


Vickson, 1995

Ganapathy et al., 2004

Marimuthu & Ponnambalam, 2004

Marimuthu et al. 2005


Potts & Baker, 1989

Trietsch & Baker, 1993

2/1/C/II/CV/{ST, No-wait}

Sriskandarajah & Wagneur, 1999


Trietsch & Baker, 1993

2/N/C/II/DV/{ST, RemT}

Cetinkaya, 1994


Sen et al., 1998

Chen & Steiner, 1999

2/N/C/II/DV/{ST, No-wait}

Sriskandarajah & Wagneur, 1999

2/1/C/II/DV/{ST, No-Wait}

Sriskandarajah & Wagneur, 1999

2/N/C/II/DV/{ST, TransT, Interleaving}

Cetinkaya, 2006


Sen et al., 1998

Table 1. Papers of two-stage flow shop

For the 2/N/C/II/CV, we need to simultaneously obtain the best job sequence and the optimal sublot allocation (sublot starting and completion times). All the papers allowed intermittent idling. It was showed that it is not possible to solve the n-job problem simply by applying lot streaming individually to the single-job problem (Potts & Baker, 1989). Several papers independently show that this problem it is decomposed into an easily identifiable sequence of single job problems, using continuous values, even with setup times (Vickson, 1995) and transfer times (Cetinkaya, 1994). Other authors have widely tackled the same problem using discrete values (2/N/C/II/DV) considering setup times (Ganapathy, Marimuthu & Ponnambalam, 2004; Marimuthu & Ponnambalam, 2005; Marimuthu, Ponnambalam & Suresh, 2004). Sublot attached and detached setup times were also considered (Vickson, 1995). It was presented some closed form solutions for continuous sublots and a fast polynominally bounded search algorithm for discrete sublots. Other papers proposed the use of removal times (Cetinkaya, 1994), of no-wait condition (Sriskandarajah & Wagneur, 1999) or even allowing interleaving (Cetinkaya, 2006).

Using variable sublots in a 2/*/V problem, only a paper was founded. Due to the complexity that involves variable sublots, it calculated continuous values and it did not consider setup times (Sen et al., 1998).

4. Lot streaming in m-stage flow shop

For the problems with more than two-machine, papers published on the topic are displayed on the Table 1.2. For the 3/N/E problem, Johnson’s rule was modified to obtain the optimal solution with unit-size sublots and continuous values (Vickson & Alfredsson, 1992). Equal-sized sublots are popular in practice. These were first studied in an m/1/E problem, where setup times were considered (Truscott, 1985). Later on a bottleneck minimal idleness heuristic (BMI) was developed to generate solutions that were very close to the optimum (Kalir & Sarin, 2001). For the m/N/E problem, the BMI model was extended to n jobs but it did not consider setup times on it (Kalir & Sarin, 2001). Other paper used integer programming to determine optimum sublot sizes while enumerating the number of sublots for an n jobs problem using discrete values (Huq, Cutright & Martin, 2004). Other researchers presented five methods including a tabu search (TS), simulated annealing (SA), hybrid genetic algorithm (HGA), ant colony optimization (ACO) and threshold accepting (TA) algorithms involving attached setup times (Marimuthu, Ponnambalam & Jawahar, 2007, 2008, 2009). Idling and no-idling condition was added to the problem (Pan, Wang, Gao & Li, 2011).

Linear and integer programming formulations were presented to determine optimal sublot sizes for one job on a 3-machine flow shop (3/1/C) using both, continuous and discrete values with consistent sublots (Trietsch & Baker, 1993). Years later, no-wait condition was added to the problem (Wagneur, 2001). Other authors extended to the case containing detached (Chen & Steiner, 1997a) and attached (Chen & Steiner, 1998) setup times. For the case of m/1/C/CV, it was extended a previous work (Sriskandarajah & Wagneur, 1999) and it was used genetic algorithm (GA) to solve problems in which fixed and variable numbers of sublots for each product were included (Kumar, Bagchi & Sriskandarajah, 2000).

For the m/1/C/DV, Glass and Potts proved that only dominant machines may appear on a critical path (Glass & Potts, 1998). Years later, a heuristic using discrete sublot sizes and no setup times was proposed (Edis & Ornek, 2009). Most of the papers used different methods to convert continuous into discrete sublot sizes (Chen & Steiner, 1997b, 2003; Glass & Herer, 2006). Multi-objective lot streaming problem (minimizing makespan and mean flow time simultaneously) was investigated (Bukchin & Masin, 2004). They also considered setup times such as (Kumar et al., 2000), who considered no-wait condition like (Chen & Steiner, 2003).






Vickson & Alfredsson, 1992


Buckhin & Masin, 2004


Truscott, 1985

m/1/C/II/DV/{ST, No-wait}

Kumar et al., 2000


Kalir & Sarin, 2001

m/N/C/II/CV/{ST, No-wait}

Kumar et al., 2000


Kalir & Sarin, 2001

m/N/C/II/CV/{ST, Interleaving}

Bukchin et al., 2010


Huq et al., 2004

Marimuthu et al., 2007, 2008, 2009

m/N/C/II/DV/{ST, No-wait}

Kumar et al., 2000

Hall et al., 2003

Kim & Jeong, 2009


Pan et al., 2011

m/N/C/II/DV/{No-ST, Interleaving}

Feldmann & Biskup, 2008


Trietsch & Baker, 1993

m/N/C/II/DV/{ST, Interleaving}

Martin, 2009

3/1/C/II/CV/{No-ST, No-wait}

Wagneur, 2001


Pan et al., 2010a, 2010b


Chen & Steiner, 1997b, 1998


Pan & Ruiz 2012

m/1/C/II/CV/{ST, No-wait}

Kumar et al., 2000


Trietsch & Baker, 1993


Glass & Potts, 1998

Edis & Ornek, 2009


Trietsch & Baker, 1993


Chen & Steiner, 1997

m/1/V/II/DV/{No-ST, No-Wait}

Liu, 2003


Glass & Herer, 2006

m/1/V/NI/DV/{ST, Transp}

Chiu et al., 2004

m/1/C/II/DV/{No-ST, No-Wait}

Chen & Steiner, 2003


Defersha & Chen, 2010

Table 2. Paper of more than 2-stage flow shop

For the problem of m/N/C/CV a heuristic and the use of GA for sequencing the products and for determining the number of sublots were proposed (Kumar et al., 2000). Bukchin extended his previous work in m/1/C to n jobs, but this time allowing interleaving (Bukchin, Masin & Kirshner, 2010). Many researchers studied the no-wait FSLS problems not allowing interleaving but integer sizes (m/N/C/DV) were assumed (Hall, Laporte, Selvarajah & Sriskandarajah, 2003; Kim & Jeong, 2009; Kumar et al., 2000). Other authors allowed the use of inter-leaving among different jobs (such as Bukchin but using discrete values), not considering setup times (Feldmann & Biskup, 2008) or considering them (Martin, 2009). Other authors focused on sequence dependent setup times (Pan, Duan, Liang, Gao & Li, 2010a; Pan, Tasgetiren, Suganthan & Liang, 2010b) and included no-idling condition (Pan & Ruiz, 2012).

For the 3/1/V problem, no setup times were considered in both cases, with consistent and discrete values (Trietsch & Baker, 1993). A heuristic method was pro-posed for the m/1/V problem with no setup times and no-wait condition (Liu, 2003). Later on, other paper considered transportation and setup times (Chiu, Chang & Lee, 2004).

For the m/N/V, only one paper has been founded in which it was considered setup times (Defersha & Chen, 2010).

5. Method used in flow shop lot streaming

In the two previous sections, efforts have focused on analyzing the types of problems addressed and the satisfaction achieved with the proposed solutions. This section introduces a classification of techniques that have been used in the papers reviewed and a brief analysis of them.

Figure 1. Methods used for two-machine and m-machine flow shop

The methods used have been classified in exact and approximate, being the last type divided in meta-heuristics (Evolutionary and Non-evolutionary) and heuristics. As it is shown in Figure 1.1, for the simple case of two-machine, exact methods dominate proposed solutions. From the 62% of the exact solutions proposed, most of them focused on the approach of a MILP model which is then analytically developed hypotheses allowing, in some cases in other dimensions theorems for minimizing Cmax. 11% are heuristics, usually developed from the MILP model analysis, and 23% are traditional meta-heuristics, evolutionary methods only represent 4%. In Figure 1.1 also shows the distribution of techniques employed in the case of more than two machines. As you can see the use of exact methods is reduced to 36%, although they have been used to simplified cases (few jobs). The evolutionary methods achieve a significant 27%, while non-evolutionary meta-heuristic and heuristics techniques make a similar contribution (≈20% both).


This work has been carried out as part of the project “Programación de la Producción con Partición Ajustable de Lotes en entornos de Planificación mixta Pedido/Stock (PP-PAL-PPS)”, ref. GVA/2013/034 funded by Consellería de Educación, Cultura y Deportes de la Generalitat Valenciana.


Baker, K. (1995). Lot streaming in the 2-machine flow-shop with setup times. Annals of Operations Research, 57, 1-11. http://dx.doi.org/10.1007/BF02099687

Bukchin, J., & Masin, M. (2004). Multi-objective lot splitting for a single product m-machine flowshop line. Iie Transactions, 36(2), 191-202. http://dx.doi.org/10.1080/07408170490245487

Bukchin, Y., Masin, M., & Kirshner, R. (2010). Modeling and Analysis of Multiobjective Lot Splitting for N-Product M-Machine Flowshop Lines. Naval Research Logistics, 57(4), 354-366.

Cetinkaya, F. (1994). Lot streaming in a 2-stage flow-shop with set-up, processing and re-moval times separated. Journal of the Operational Research Society, 45(12), 1445-1455.

Cetinkaya, F.C. (2006). 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. http://dx.doi.org/10.1007/s00170-004-2493-9

Cetinkaya, F., & Kayaligil, M. (1992). Unit sized transfer batch scheduling with setup times. Computers & Industrial Engineering, 22(2), 177-183. http://dx.doi.org/10.1016/0360-8352(92)90045-L

Chen, J., & Steiner, G. (1997a). Lot streaming with detached setups in three-machine flow shops. European Journal of Operational Research, 96(3), 591-611. http://dx.doi.org/10.1016/S0377-2217(96)00091-4

Chen, J., & Steiner, G. (1997b). Approximation methods for discrete lot streaming in flow shops. Operations Research Letters, 21(3), 139-145. http://dx.doi.org/10.1016/S0167-6377(97)00039-4

Chen, J., & Steiner, G. (2003). On discrete lot streaming in no-wait flow shops. Iie Transac-tions, 35(2), 91-101. http://dx.doi.org/10.1080/07408170304379

Chen, J.A., & Steiner, G. (1998). Lot streaming with attached setups in three-machine flow shops. Iie Transactions, 30(11), 1075-1084. http://dx.doi.org/10.1080/07408179808966564

Chen, J.A., & Steiner, G. (1999). Discrete lot streaming in two-machine flow shops. Infor, 37(2), 160-173.

Chiu, H., Chang, J., & Lee, C. (2004). Lot streaming models with a limited number of capacitated transporters in multistage batch production systems. Computers & Operations Research, 31(12), 2003-2020. http://dx.doi.org/10.1016/S0305-0548(03)00159-X

Defersha, F.M., & Chen, M. (2010). A hybrid genetic algorithm for flowshop lot streaming with setups and variable sublots. Int. Journal of Production Research, 48(6), 1705-1726. http://dx.doi.org/10.1080/00207540802660544

Edis, R.S., & Ornek, M.A. (2009). A tabu search-based heuristic for single-product lot streaming problems in flow shops. International Journal of Advanced Manufacturing Technology, 43(11-12), 1202-1213. http://dx.doi.org/10.1007/s00170-008-1798-5

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. http://dx.doi.org/10.1080/00207540600930065

Ganapathy, V., Marimuthu, S., & Ponnambalam, S. (2004). Tabu search and simulated an-nealing algorithms for lot-streaming in two-machine flowshop. 2004 Ieee International Conference on Systems, Man & Cybernetics, Vols 1-7, 4221-4225. New York: Ieee.

Glass, C.A., & Herer, Y.T. (2006). On the equivalence of small batch assembly line balancing and lot streaming in a flow shop. International Journal of Production Research, 44(21), 4587‑4606. http://dx.doi.org/10.1080/00207540600607119

Glass, C., & Potts, C. (1998). Structural properties of lot streaming in a flow shop. Mathematics of Operations Research, 23(3), 624-639. http://dx.doi.org/10.1287/moor.23.3.624

Hall, N., Laporte, G., Selvarajah, E., & Sriskandarajah, C. (2003). Scheduling and lot streaming in flowshops with no-wait in process. Journal of Scheduling, 6(4), 339-354. http://dx.doi.org/10.1023/A:1024042209719

Huq, F., Cutright, K., & Martin, C. (2004). Employee scheduling and makespan minimization in a flow shop with multi-processor work stations: a case study. Omega-International Journal of Management Science, 32(2), 121-129. http://dx.doi.org/10.1016/j.omega.2003.09.014

Johnson, S.M. (1954). Optimal two‐ and three‐stage production schedules with setup times included. Naval Research Logistics Quarterly, 1(1), 61-68. http://dx.doi.org/10.1002/nav.3800010110

Kalir, A.A., & Sarin, S.C. (2001). A near-optimal heuristic for the sequencing problem in multiple-batch flow-shops with small equal sublots. Omega, 29(6), 577-584. http://dx.doi.org/10.1016/S0305-0483(01)00046-9

Kalir, A., & Sarin, S. (2003). Constructing near optimal schedules for the flow-shop lot streaming problem with sublot-attached setups. Journal of Combinatorial Optimization, 7(1), 23-44. http://dx.doi.org/10.1023/A:1021942422161

Kim, K., & Jeong, I.-J. (2009). Flow shop scheduling with no-wait flexible lot streaming using an adaptive genetic algorithm. International Journal of Advanced Manufacturing Technology, 44(11-12), 1181-1190. http://dx.doi.org/10.1007/s00170-007-1236-0

Kumar, S., Bagchi, T.P., & Sriskandarajah, C. (2000). Lot streaming and scheduling heuristics for m-machine no-wait flowshops. Computers & Industrial Engineering, 38(1), 149-172. http://dx.doi.org/10.1016/S0360-8352(00)00035-8

Liu, S.C. (2003). A heuristic method for discrete lot streaming with variable sublots in a flow shop. The International Journal of Advanced Manufacturing Technology, 22(9-10), 662-668. http://dx.doi.org/10.1007/s00170-002-1516-7

Marimuthu, S., & Ponnambalam, S. (2005). Heuristic search algorithms for lot streaming in a two-machine flowshop. International Journal of Advanced Manufacturing Technology, 27(1‑2), 174-180. http://dx.doi.org/10.1007/s00170-004-2127-2

Marimuthu, S., Ponnambalam, S.G., & Jawahar, N. (2007). Tabu Search and Simulated Annealing Algorithms for Scheduling in Flow Shops with Lot Streaming. Proceedings of the Institution of Mechanical Engineers, Part B: Journal of Engineering Manufacture, 221(2), 317‑331. http://dx.doi.org/10.1243/09544054JEM334

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. http://dx.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. http://dx.doi.org/10.1016/j.jmatprotec.2008.03.013

Marimuthu, S., Ponnambalam, S., & Suresh, R. (2004). Evolutionary algorithm and Threshold accepting algorithm for scheduling in two-machine flow shop with lot streaming. New York: Ieee.

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. http://dx.doi.org/10.1016/j.omega.2006.11.002

Pan, Q.-K., Duan, J., Liang, J.J., Gao, K., & Li, J. (2010a). A Novel Discrete Harmony Search Algorithm for Scheduling Lot-streaming Flow Shops. New York: Ieee.

Pan, Q.-K., & Ruiz, R. (2012). An estimation of distribution algorithm for lot-streaming flow shop problems with setup times. Omega, 40(2), 166-180. http://dx.doi.org/10.1016/j.omega.2011.05.002

Pan, Q.-K., Tasgetiren, M.F., Suganthan, P.N., & Liang, Y.-C. (2010b). Solving Lot-streaming Flow Shop Scheduling Problems Using a Discrete Harmony Search Algorithm. New York: Ieee.

Pan, Q.-K., Wang, L., Gao, L., & Li, J. (2011). An effective shuffled frog-leaping algorithm for lot-streaming flow shop scheduling problem RID C-7528-2009. International Journal of Advanced Manufacturing Technology, 52(5-8), 699-713. http://dx.doi.org/10.1007/s00170-010-2775-3

Potts, C.N., & Baker, K.R. (1989). Flow shop scheduling with lot streaming. Operations Research Letters, 8(6), 297-303. http://dx.doi.org/10.1016/0167-6377(89)90013-8

Sarin, S.C., & Jaiprakash, P. (2007). Flow Shop Lot Streaming. Springer. http://dx.doi.org/10.1007/978-0-387-47688-9

Sen, A., Topaloglu, E., & Benli, O. (1998). Optimal streaming of a single job in a two-stage flow shop. European Journal of Operational Research, 110(1), 42-62. http://dx.doi.org/10.1016/S0377-2217(98)00203-3

Sriskandarajah, C., & Wagneur, E. (1999). Lot streaming and scheduling multiple products in two-machine no-wait flowshops. Iie Transactions, 31(8), 695-707. http://dx.doi.org/10.1080/07408179908969869

Trietsch, D., & Baker, K. (1993). Basic Techniques for lot streaming. Operations Research, 41(6), 1065-1076. http://dx.doi.org/10.1287/opre.41.6.1065

Truscott, W. (1985). Scheduling production activities in multi-stage batch manufacturing systems. International Journal of Production Research, 23(2), 315-328. http://dx.doi.org/10.1080/00207548508904710

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. http://dx.doi.org/10.1016/0377-2217(93)E0366-6

Vickson, R.G., & Alfredsson, 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. http://dx.doi.org/10.1080/00207549208948107

Wagneur, E. (2001). Lotstreaming in no-wait flowshops with one machine never idle. New York: Ieee.

Licencia de Creative Commons 

This work is licensed under a Creative Commons Attribution 4.0 International License

Journal of Industrial Engineering and Management, 2008-2019

Online ISSN: 2013-0953; Print ISSN: 2013-8423; Online DL: B-28744-2008

Publisher: OmniaScience