A review of lot streaming in a flow shop environment with makespan criteria <s> Lot streaming in m-stage flow shop <s> The scheduling of production activities has a wide-spread effect on resource productivity and customer service. This paper presents a model for scheduling setups, technological operations, inspections and internal transportation activities in multi-stage batch manufacturing systems. It is shown that the model facilitates the efficient utilization of resources and the timely availability of product. An algorithm for generating detailed production schedules (Gantt charts) from the model is developed. This algorithm, as coded on an IBM Personal Computer, is used to produce sample schedules which demonstrate the potential application of the research for planning and control. <s> BIB001 </s> A review of lot streaming in a flow shop environment with makespan criteria <s> Lot streaming in m-stage flow shop <s> Transfer batches permit the processing of part of a job-lot on downstream machines before completion of the lot on the current machine. This paper studies the effects of transfer batches in two- and three-machine flow shops. It establishes conditions under which each unit of a job can optimally be viewed as a separate transfer batch. Issues of interrupted versus continuous production on downstream machines, and job-splitting (lot-sizing) are discussed. Examples are provided which show that even with a regular measure of performance and no setup times, job-splitting can yield a better solution than is possible without splitting jobs. A modification of Johnson's Algorithm for makespan minimization is derived under suitable conditions in two-machine flow shops and in special three-machine flow shops. An empirical study of transfer batch effects in two-machine flow shops is undertaken for both the makespan and the total flow time criteria under the assumption that jobs are not split. The no-split jobs restric... <s> BIB002 </s> A review of lot streaming in a flow shop environment with makespan criteria <s> Lot streaming in m-stage flow shop <s> We present an overview of basic models and solution algorithms for the lot streaming problem. We include models with continuous and discrete sublot sizes, models with and without intermittent idling of machines, and models with consistent and variable sublots. We also introduce a model with limited transporter capacity. First we present solutions for two machines, then generalize to three machines and, where possible, to several machines. We synthesize previous research and introduce several new results. <s> BIB003 </s> A review of lot streaming in a flow shop environment with makespan criteria <s> Lot streaming in m-stage flow shop <s> Abstract Lot streaming is the process of splitting a job or lot to allow overlapping between successive operations in a multistage production system. This use of transfer lots usually results in a shorter makespan for the corresponding schedule. In this paper, we study the structural properties of schedules which minimize the makespan for a single job with detached setup times in a flow shop. Although the structure of the optimal schedules is more complex than in the case with no setups [9], it is possible to find the optimal solution with s sublots in O (log s ) time for the three-machine case. <s> BIB004 </s> A review of lot streaming in a flow shop environment with makespan criteria <s> Lot streaming in m-stage flow shop <s> Lot streaming is the process of splitting a job or lot to allow overlapping between successive operations in a multistage production system. This use of transfer lots usually results in a shorter makespan for the corresponding schedule. In this paper, we present two quickly obtainable approximations of very good quality for the discrete lot streaming problem in flow shops. <s> BIB005 </s> A review of lot streaming in a flow shop environment with makespan criteria <s> Lot streaming in m-stage flow shop <s> Lot streaming is the process of splitting a job or lot to allow overlapping between successive operations in a multistage production system. This use of transfer lots usually results in a significantly shorter makespan for the schedule. We study the structural properties of schedules which minimize the makespan for a single job with attached setup times in a flow shop. The structure of the optimal schedules is more complex than in the case with no setups or detached setups, as it may follow a much larger variety of patterns. Using the structural insights obtained, however, it is possible to find the optimal solution with s sublots in O(s) time for the three-machine case. <s> BIB006 </s> A review of lot streaming in a flow shop environment with makespan criteria <s> Lot streaming in m-stage flow shop <s> Lot streaming is the process of splitting a given lot or job to allow the overlapping of successive operations in multi-stage production systems, thereby reducing the makespan of the corresponding schedule. This paper considers the problem of finding sublot sizes to minimize the makespan for a single job in an m-machine flow shop. On each machine, the job is to be partitioned into a given number of sublots, and sublot sizes are the same on each machine. We introduce the concept of machine dominance, and propose an algorithm to reduce the problem so that only dominant machines are considered explicitly. After defining a network representation in which it is required to find the shortest critical path length, we identify the structure of critical paths for optimal sublot sizes. Knowledge of this structure considerably reduces the search for an optimal solution, which we illustrate by presenting algorithms for finding optimal sublot sizes. <s> BIB007 </s> A review of lot streaming in a flow shop environment with makespan criteria <s> Lot streaming in m-stage flow shop <s> We consider the problem of minimizing makespan in two-machine no-wait flowshops with multiple products requiring lot streaming. A “product” (or lot) consists of many identical items. Lot streaming (lot sizing) is the process of creating sublots (or transfer batches) to move the completed portion of a production sublot to downstream machines so that operations can be overlapped. The number of sublots for each product is fixed. When the flowshop produces only a single product, we obtain optimal continuous-sized sublots. It is shown that these sublot sizes are also optimal for the problem of simultaneous lot streaming and scheduling of multiple products. The optimal scheduling of products can be accomplished by application of the algorithm due to Gilmore and Gomory [1]. Then, we devise an efficient heuristic for the problem of simultaneous lot streaming (finding optimal integer-sized sublots) and scheduling of multiple products. Computational results indicate that this heuristic can consistently deliver close-to-optimal solutions for the problem. A comparison of this heuristic is also made with a heuristic that first divides items belonging to each product into nearly equal-sized sublots and then constructs a schedule for such sublots. Finally, we extend our solution procedures to a traditional and more general lot streaming model, where the number of sublots for each product is a decision variable. <s> BIB008 </s> A review of lot streaming in a flow shop environment with makespan criteria <s> Lot streaming in m-stage flow shop <s> Abstract The objective of this paper is to minimize makespan in m -machine no-wait flowshops with multiple products requiring lot streaming. A ‘product’ here implies many identical items. ‘Lot streaming’ creates sublots to move the completed portion of a production lot to downstream machines so that machine operations can be overlapped. For the single product case with fixed number of sublots we obtain optimal continuous-sized sublots and then use a heuristic to find integer-sized sublots. For the multi-product continuous-sized sublots case we show that the optimal sequencing of products may be attained by solving a traveling salesman problem. We then construct another heuristic to yield integer-sized sublots. Finally, we evaluate the use of genetic algorithmic meta-heuristics for the interacting decision phases in simultaneous lot streaming and sequencing. We conclude that while GA may deliver makespans comparable in quality to those given by heuristic methods that cleverly exploit problem features particular to lot streaming, GA loses out in computational efficiency. On the other hand, GA can optimize the number of sublots for each product — a task for which neither an analytical nor a heuristic method presently exists. <s> BIB009 </s> A review of lot streaming in a flow shop environment with makespan criteria <s> Lot streaming in m-stage flow shop <s> In this paper, we consider the lot-streaming problem of sequencing a set of batches, to be processed in equal sublots, in a flow-shop, so as to minimize makespan. A new heuristic procedure, called the bottleneck minimal idleness heuristic, is developed. Results of an experimental study are presented. It is shown that the proposed procedure generates solutions that are very close to the optimal solutions, and that the solutions generated are better than those obtained by using the fast insertion heuristic, considered to be a good heuristic for solving the flow-shop scheduling problem, when applied to the problem on hand. <s> BIB010 </s> A review of lot streaming in a flow shop environment with makespan criteria <s> Lot streaming in m-stage flow shop <s> We consider the problem of minimizing makespan in a no-wait flow-shop with an arbitrary number of machines, when one of the machines has to remain always active. A lot consists of many identical items of the same product. Lot streaming (lot sizing) is the process of creating sublots to move the completed portion of a production sublot to downstream machines so that operations will be overlapped. We consider the number of sublots as given. Some general results are proved for the general no-wait flow-shop with an arbitrary number of machines. A closed form formula is then proposed for the case where one machine never remain idle between the processing of two lots. <s> BIB011 </s> A review of lot streaming in a flow shop environment with makespan criteria <s> Lot streaming in m-stage flow shop <s> Lot streaming is the process of splitting a given lot or job to allow the overlapping of successive operations in multi-stage manufacturing systems, thereby reducing the makespan of the corresponding schedule. In this research, we propose a heuristic method for discrete lot streaming with variable sublots. This method consists of two procedures: (1) determining a continuous solution (sublots with real values) for variable lot streaming and (2) deriving a discrete solution by rounding up the continuous solution. One sample description is presented for demonstration purposes. The proposed method is then tested and evaluated via simulation. The results show that the proposed method outperforms other existing heuristic methods such as discrete lot streaming with consistent sublots, and simulated annealing (SA). <s> BIB012 </s> A review of lot streaming in a flow shop environment with makespan criteria <s> Lot streaming in m-stage flow shop <s> Lot streaming is the process of splitting a job or lot to allow overlapping between successive operations in a multistage production system. This use of transfer lots usually results in a substantially shorter makespan for the corresponding schedule. In this paper, we study the discrete lot streaming problem for a single job in no-wait flow shops. We present a new linear programming formulation for the problem. We show that the optimal solutions are the same for the m 2 2 case with or without no-wait constraints. We also present a fast, polynomial-time solution method for this case. For the general case, we prove that any solution which is 'close' to the continuous optimal solution will be a good approximation for the discrete problem. This property allows us to present two quickly obtainable approximations of very good quality. <s> BIB013 </s> A review of lot streaming in a flow shop environment with makespan criteria <s> Lot streaming in m-stage flow shop <s> Lot streaming involves splitting a production lot into a number of sublots, in order to allow the overlapping of successive operations, in multi-machine manufacturing systems. In no-wait flowshop scheduling, sublots are necessarily consistent, that is, they remain the same over all machines. The benefits of lot streaming include reductions in lead times and work-in-process, and increases in machine utilization rates. We study the problem of minimizing the makespan in no-wait flowshops producing multiple products with attached setup times, using lot streaming. Our study of the single product problem resolves an open question from the lot streaming literature. The intractable multiple product problem requires finding the optimal number of sublots, sublot sizes, and a product sequence for each machine. We develop a dynamic programming algorithm to generate all the nondominated schedule profiles for each product that are required to formulate the flowshop problem as a generalized traveling salesman problem. This problem is equivalent to a classical traveling salesman problem with a pseudopolynomial number of cities. We develop and computationally test an efficient heuristic for this problem. Our results indicate that solutions can quickly be found for flowshops with up to 10 machines and 50 products. Moreover, the solutions found by our heuristic provide a substantial improvement over previously published results. <s> BIB014 </s> A review of lot streaming in a flow shop environment with makespan criteria <s> Lot streaming in m-stage flow shop <s> This paper describes the development of a mixed integer linear programming model for a flow shop with multi-processor workstations. The primary objective of the model is to minimize makespan through lot-streaming. A secondary objective is to determine workforce size and schedule. A constant daily workload is assumed. The model is simple enough to be understood and implemented by managers and supervisors using readily available spreadsheet programs. An actual process, at a local insurance company handling a moderate daily level of document and payment processing, is used as a case study. The results of the case study yielded an improvement in the makespan of the current process. The model, shown in this paper to be a useful tool in the document processing industry, is generic enough to be applied to other multi-processor flow shops. <s> BIB015 </s> A review of lot streaming in a flow shop environment with makespan criteria <s> Lot streaming in m-stage flow shop <s> In this paper, the mean flowtime and the makespan objectives are simultaneously investigated in a single product, m-machine, flowshop system. For this purpose, an efficiency frontier approach is applied and an optimal algorithm for generating all efficient solutions is developed. A comprehensive computational experiment is performed for analyzing the tradeoff between the two objectives and evaluating the proposed algorithm performance. The most-balanced-solution, MinMax, is defined and recommended as a desirable alternative for either the flowtime or the makespan optimal solutions. Results show that when the system is optimized for either the mean flowtime or the makespan, a significant loss in the nonoptimized objective value is observed. On the other hand, adopting the MinMax solution obtains a close to optimal solution in both objectives. <s> BIB016 </s> A review of lot streaming in a flow shop environment with makespan criteria <s> Lot streaming in m-stage flow shop <s> Abstract This paper presents a more general mathematical programming model to solve a lot streaming problem in multistage batch production systems in which transportation activities are involved. The purpose of the proposed mathematical programming model is to find the optimal start time, the optimal number of transfer batches, and the optimal allocation of variable transfer batches that minimize the total cost, including the makespan cost and the transportation cost. Two efficient heuristic procedures are developed due to the large amount of computational time required to solve the proposed mathematical programming model. A practical application of the two proposed heuristic methods is demonstrated to show their real-world usefulness. We also recommend the best appropriate heuristic method that can be chosen by a production manager under a certain premise. An experiment consisting of two phases was conducted to further verify the excellent performance of the two proposed heuristic methods. <s> BIB017 </s> A review of lot streaming in a flow shop environment with makespan criteria <s> Lot streaming in m-stage flow shop <s> In this article we compare two apparently dissimilar scheduling problems. The Small Batch Assembly Line Balancing problem is the process of dividing operations over multiple stations so as to produce a series of parts whose processing times are characterized by learning. The Lot Streaming in a Flow Shop problem is the process of splitting a given lot or job to allow overlap of successive operations in multi-stage production systems, thereby reducing the makespan of the corresponding schedule. We show that the two problems are formally equivalent. By exploring the mathematical equivalence of the two problems, a number of unexpected new results have been obtained. <s> BIB018 </s> A review of lot streaming in a flow shop environment with makespan criteria <s> Lot streaming in m-stage flow shop <s> AbstractThis paper addresses the problem of making sequencing and scheduling decisions for n Jobs in m-machine flow shops with a lot sizing constraint. Lot streaming (lot sizing) is the process of creating sublots to move the completed portion of a production sublot to downstream machines. The planning decisions become more complex when lot streaming is allowed. There is scope for efficient metaheuristics for scheduling problems in an m machine flow shop with lot streaming. In recent years, much attention has been given to heuristics and search techniques. This paper proposes two metaheuristics, namely a simulated annealing algorithm (SA) and a tabu search algorithm (TABU), to evolve the optimal sequence for makespan and total flow time criteria in an m-machine flow shop with lot streaming. The algorithms are evaluated by means of comparison with Baker's algorithm for 2m/c cases and the makespan criterion, which proves the capability of both of them. <s> BIB019 </s> A review of lot streaming in a flow shop environment with makespan criteria <s> Lot streaming in m-stage flow shop <s> In this paper we study the multi-product lot streaming problem in a permutation flow shop. The problem involves splitting given order quantities of different products into sublots and determining their optimal sequence. Each sublot has to be processed successively on all machines. The sublots of the particular products are allowed to intermingle, that is sublots of different jobs may be interleaved. A mixed integer programming formulation is presented which enables us to find optimal sublot sizes as well as the optimal sequence simultaneously. With this formulation, small- and medium-sized instances can be solved in a reasonable time. The model is further extended to deal with different settings and objectives. As no lot streaming instances are available in the literature, LSGen, a problem generator, is presented, facilitating valid and reproducible instances. First results concerning the average benefit of lot streaming with multiple products are presented, and are based on a computational study with 160... <s> BIB020 </s> A review of lot streaming in a flow shop environment with makespan criteria <s> Lot streaming in m-stage flow shop <s> This paper presents a hybrid genetic algorithm/mathematical programming heuristic for the n-job, m-machine flowshop problems with lot streaming. The number of sublots for each job and the size of sublots are directly addressed by the heuristic and setups may be sequence-dependent. A new aspect of the problem, the interleaving of sublots from different jobs in the processing sequence, is developed and addressed. Computational results from 12 randomly generated test sets of 24 problems each are presented. <s> BIB021 </s> A review of lot streaming in a flow shop environment with makespan criteria <s> Lot streaming in m-stage flow shop <s> Lot streaming is a technique that splits a production lot consisting of identical items into sublots to improve the performance of a multistage production system by overlapping the sublots on successive machines. In this study, a single-product multistage stochastic flow shop problem with consistent sublot types and discrete sublot sizes is considered, and a heuristic algorithm which is a combination of simulation and tabu search is presented with the objective of minimizing makespan. First, the performance of the proposed heuristic is evaluated against a deterministic model, then it is applied to stochastic flow shops and the results are compared with those of Arena’s OptQuest. The computational results show that the proposed heuristic gives rather efficient results and facilitates the solution of the considered complex stochastic lot streaming problems. <s> BIB022 </s> A review of lot streaming in a flow shop environment with makespan criteria <s> Lot streaming in m-stage flow shop <s> In this paper, we propose a flow shop scheduling problem with no-wait flexible lot streaming. The problem involves the splitting of order quantities of different products into sublots and considers alternative machines with different processing times. Sublots of a particular product are not allowed to intermingle; that is, sublots of different products must be non-preemptive. The objective of the problem is the minimization of the makespan. An adaptive genetic algorithm (GA) is proposed, which is composed of three main steps. The first step is a position-based crossover of products and local-search-based mutation for better offspring. The second step is an iterative hill-climbing algorithm to improve the current generation. The last step is the adaptive regulation of the crossover and mutation rates. Experimental results are presented for various sizes of problems to describe the performance of the proposed algorithm and they show promising outcome compared to traditional GAs. <s> BIB023 </s> A review of lot streaming in a flow shop environment with makespan criteria <s> Lot streaming in m-stage flow shop <s> This paper proposes a novel discrete harmony search (DHS) algorithm to minimize makespan for a lot-streaming flow shop scheduling problem with sequence dependent setup times. Unlike the traditional harmony search (HS) algorithm, the proposed DHS algorithm utilizes job permutations to represent harmonies and applies a job-permutation-based improvisation to generate new harmonies. To enhance the algorithm's searching ability, an effective initialization scheme based on the NEH heuristic is developed to construct an initial harmony memory with certain quality and diversity, and an efficient local search algorithm based on the insert neighborhood structures is fused to stress the local exploitation. Extensive computational simulations and comparisons are provided, which demonstrate the effectiveness of the proposed DHS against the best performing algorithms from the literature. <s> BIB024 </s> A review of lot streaming in a flow shop environment with makespan criteria <s> Lot streaming in m-stage flow shop <s> The harmony search (HS) algorithm is one of the recent evolutionary computation techniques to solve optimization problems. To make it applicable for lot-streaming flow shop problems, a discrete variant of the HS algorithm (DHS) with job permutations representation is proposed. In the proposed DHS algorithm, a new improvisation scheme is designed to generate feasible job sequences. A local search algorithm based on the insert neighborhood structure is fused to stress the further enhancement capability of the algorithm proposed whereas a restart scheme is employed to avoid the stagnation of the evolution. Extensive computational simulations and comparisons are provided, which demonstrate the effectiveness of the proposed DHS against the best performing algorithms from the literature. <s> BIB025 </s> A review of lot streaming in a flow shop environment with makespan criteria <s> Lot streaming in m-stage flow shop <s> Lot streaming is the process of splitting a given lot or job to allow the overlapping of successive operations in flowshops or multi-stage manufacturing systems to reduce manufacturing lead time. Recent literature shows that significant lead time improvement is possible if variable sublots, instead of equal or consistent sublots, are used when production setup time is considered. However, lot streaming problems with variable sublots are difficult to solve to optimality using off-shelf optimisation packages even for problems of small and experimental sizes. Thus, efficient solution procedures are needed for solving such problems for practical applications. In this paper, we develop a mathematical programming model and a hybrid genetic algorithm for solving n-job m-machine lot streaming problems with variable sublots considering setup times. The preliminary computational results are encouraging. <s> BIB026 </s> A review of lot streaming in a flow shop environment with makespan criteria <s> Lot streaming in m-stage flow shop <s> Lot-streaming flow shops have important applications in different industries including textile, plastic, chemical, semiconductor and many others. This paper considers an n-job m-machine lot-streaming flow shop scheduling problem with sequence-dependent setup times under both the idling and no-idling production cases. The objective is to minimize the maximum completion time or makespan. To solve this important practical problem, a novel estimation of distribution algorithm (EDA) is proposed with a job permutation based representation. In the proposed EDA, an efficient initialization scheme based on the NEH heuristic is presented to construct an initial population with a certain level of quality and diversity. An estimation of a probabilistic model is constructed to direct the algorithm search towards good solutions by taking into account both job permutation and similar blocks of jobs. A simple but effective local search is added to enhance the intensification capability. A diversity controlling mechanism is applied to maintain the diversity of the population. In addition, a speed-up method is presented to reduce the computational effort needed for the local search technique and the NEH-based heuristics. A comparative evaluation is carried out with the best performing algorithms from the literature. The results show that the proposed EDA is very effective in comparison after comprehensive computational and statistical analyses. <s> BIB027
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 BIB002 . Equal-sized sublots are popular in practice. These were first studied in an m/1/E problem, where setup times were considered BIB001 . Later on a bottleneck minimal idleness heuristic (BMI) was developed to generate solutions that were very close to the optimum BIB010 . For the m/N/E problem, the BMI model was extended to n jobs but it did not consider setup times on it BIB010 . Other paper used integer programming to determine optimum sublot sizes while enumerating the number of sublots for an n jobs problem using discrete values BIB015 . 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 BIB019 BIB021 ). Idling and no-idling condition was added to the problem  . 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 BIB003 . Years later, no-wait condition was added to the problem BIB011 . Other authors extended to the case containing detached BIB004 ) and attached BIB006 setup times. For the case of m/1/C/CV, it was extended a previous work BIB008 and it was used genetic algorithm (GA) to solve problems in which fixed and variable numbers of sublots for each product were included BIB009 . For the m/1/C/DV, Glass and Potts proved that only dominant machines may appear on a critical path BIB007 . Years later, a heuristic using discrete sublot sizes and no setup times was proposed BIB022 ). Most of the papers used different methods to convert continuous into discrete sublot sizes BIB005 BIB012 BIB018 . Multi-objective lot streaming problem (minimizing makespan and mean flow time simultaneously) was investigated BIB016 . They also considered setup times such as BIB009 , who considered no-wait condition like BIB013 . 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 BIB009 . Bukchin extended his previous work in m/1/C to n jobs, but this time allowing interleaving  . Many researchers studied the no-wait FSLS problems not allowing interleaving but integer sizes (m/N/C/DV) were assumed BIB014 BIB023 BIB009 . Other authors allowed the use of inter-leaving among different jobs (such as Bukchin but using discrete values), not considering setup times BIB020 or considering them BIB021 ). Other authors focused on sequence dependent setup times BIB024 BIB025 and included no-idling condition BIB027 . For the 3/1/V problem, no setup times were considered in both cases, with consistent and discrete values BIB003 . A heuristic method was pro-posed for the m/1/V problem with no setup times and no-wait condition BIB012 . Later on, other paper considered transportation and setup times BIB017 . For the m/N/V, only one paper has been founded in which it was considered setup times BIB026 ). -765-Journal of Industrial Engineering and Management -http://dx.doi.org/10.3926/jiem.553