Lot streaming with attached setups in three-machine flow shops

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.     

Improved sheep flock heredity algorithm and artificial bee colony algorithm for scheduling m-machine flow shops lot streaming with equal size sub-lot problems

The objective of this paper is to develop intelligent search heuristics to solve n-jobs, m-machines lot streaming problem in a flow shop with equal size sub-lots where the objective is to minimise makespan and total flow time independently. Improved sheep flock heredity algorithm (ISFHA) and artificial bee colony (ABC) algorithms are applied to the problem above mentioned. The performance of these algorithms is evaluated against the algorithms reported in the literature. The computational analysis shows the better performance of ISFHA and ABC algorithms.     

On the equivalence of small batch assembly line balancing and lot streaming in a flow shop

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.     

A genetic algorithm for solving the economic lot scheduling problem in flow shops

In this study, we propose a hybrid genetic algorithm (HGA) to solve the economic lot scheduling problem in flow shops. The proposed HGA utilizes a so-called Proc PLM heuristic that tests feasibility for the candidate solutions obtained in the evolutionary process of genetic algorithm. When a candidate solution is infeasible, we propose to use a binary search heuristic to ‘fix’ the candidate solution so as to obtain a feasible solution with the minimal objective value. To evaluate the performance of the proposed HGA, we randomly generate a total of 2100 instances from seven levels of utilization rate ranged from 0.45 to 0.80. We solve each of those 2100 instances by the proposed HGA and the other solution approaches in the literature. Our experiments show that the proposed HGA outperforms traditional methods for solving the economic lot scheduling problem in flow shops.     

New heuristics for no-wait flow shops with a linear combination of makespan and maximum lateness

In this work we study a flow shop scheduling problem in which jobs are not allowed to wait between machines, a situation commonly referred to as no-wait. The criterion is to minimise a weighted sum of makespan and maximum lateness. A dominance relation for the case of three machines is presented and evaluated using experimental designs. Several heuristics and local search methods are proposed for the general m-machine case. The local search methods are based on genetic algorithms and iterated greedy procedures. An extensive computational analysis is conducted where it is shown that the proposed methods outperform existing heuristics and metaheuristics in all tested scenarios by a considerable margin and under identical CPU times.     

A comprehensive review of lot streaming

Lot streaming combined lot splitting with operations overlapping is one of the effective techniques used to implement the time-based strategy in today's era of global competition. Therefore, this technique has been studied extensively over the past few decades. In this paper, we first propose a uniquely categorized structure to characterize the existing lot streaming problems in terms of three main dimensions, seven subdimensions, and 17 levels. Then, a notation set is defined to systematically express each existing lot streaming problem by seven ordered elements corresponding to the seven subdimensions. Based on the classification structure and the defined notation set, a comprehensive survey is presented to make up for the lack of a literature review on this subject. The objective is to help the reader gain a clear understanding of the evolution of previous research on lot streaming. This paper concludes with some constructive suggestions for future research directions.     

Scheduling flow shops with blocking using a discrete self-organising migrating algorithm

A novel approach of a discrete self-organising migrating algorithm is introduced to solve the flowshop with blocking scheduling problem. New sampling routines have been developed that propagate the space between solutions in order to drive the algorithm. The two benchmark problem sets of Carlier, Heller, Reeves and Taillard are solved using the new algorithm. The algorithm compares favourably with the published algorithms Differential Evolution, Tabu Search, Genetic Algorithms and their hybrid variants. A number of new upper bounds are obtained for the Taillard problem sets.     

Lot streaming and scheduling multiple products in two-machine no-wait flowshops

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.     

Two-stage hybrid flow shop batching and lot streaming with variable sublots and sequence-dependent setups

A paint manufacturing firm's customers typically place orders for two or more products simultaneously. Each product belongs to a family that denotes batching compatibility during manufacturing. Further, products can be split into several sublots to allow overlapping production in a two-stage hybrid flow shop wherein various identical, capacitated machines operate in parallel at each stage. We present a mixed-integer linear program (MILP) for this integrated batching and lot streaming problem with variable sublots, incompatible job families, and sequence-dependent setup times. The model determines the number and size of sublots for each product and the production sequencing for each sublot such that the total weighted completion time is minimised. To promote practical implementation, we develop and evaluate heuristics to efficiently solve this problem.     

The G-group heuristic to solve the multi-product,sequencing, lot sizing and scheduling problem in flow shops

This paper presents a new heuristic to solve the problem of making sequencing, lot sizing and scheduling decisions for a number of products manufactured in a flow shop environment, so as to minimize the sum of setup and inventory holding costs while a given demand is fulfilled without backlogging. The proposed solution method first determines sequencing decisions then lot sizing and scheduling decisions are simultaneously determined. This heuristic, called the G-group method, divides the set of products into G groups and requires that products belonging to the same group have the same cycle time. Also, the cycle time of each group is restricted to be an integer multiple of a basic period. For each basic period of the global cycle, the products to be produced during this period and the production sequence to be used are chosen. Then, a non-linear program is solved to determine lot sizes and to construct a feasible production schedule. To evaluate its performance, the G-group method was compared to four other methods. Numerical results show that the proposed heuristic outperforms all these methods.     

Efficient heuristic approaches to transform job shops into flow shops

In this paper, we address the problem of transforming a job shop layout into a flow shop with the objective of minimizing the length of the resulting flow line. Since this problem is NP-hard, we focus our attention on developing high quality approximate solutions. We start by reviewing existing heuristics for the problem as well as some heuristics developed for the Shortest Common Supersequence problem, a well-known stringology problem similar to the one under consideration. We then present a new decomposition approach for the problem that allows the application of local search techniques. We have embedded this approach into a tabu search procedure that is shown to be effective in subsequent computational experiments. Finally, we provide best-so-far solutions for classical job shop problem instances, so they can be used as benchmark instances for further research.     

Scheduling flow shops with operators

This paper addresses the problem of assigning a number of operators, less than the number of machines, in a flow shop environment. We study two different problems. The first is the assignment of operators subject to a fixed job sequence; the second is on handling simultaneously the assignment of operators and the scheduling of jobs on the machines. We present complexity results and develop a new lower bound. Heuristic algorithms are designed for both problems. An experimental study is then conducted to evaluate the quality of our solving methods. The results show that the appropriate approach depends on the parameters of the problem, including the number of operators. The methods also provided results close to the theoretical lower bound in most of the cases.     

Quality flow model in automotive paint shops

Improving paint quality is of significant importance for vehicle manufacturing. In this paper, a quality flow model is presented to analyse and improve quality in automotive paint shops. Specifically, we study the vehicle-painting process with multiple inspection stations. After each inspection, vehicles failed to achieve quality requirement will be repaired before moving to the next operation. In such systems, the quality variations may propagate along the painting process. To address this, a three-state quality flow model has been developed, and analytical formulas to evaluate product quality have been derived. In addition, to improve quality performance, a bottleneck analysis method has been introduced to identify the most critical stage that impedes product quality in the strongest manner. Two case studies at automotive paint shops are introduced to illustrate the applicability of the method.     

Flexible job shop scheduling with lot streaming and sublot size optimisation

Models and optimisation approaches are developed for a flexible job shop scheduling problem with lot streaming and lot sizing of the variable sublots. A two-stage optimisation procedure is proposed. First, the makespan value is minimised with the smallest sublots defined for the problem instance. This makes it possible to shorten the makespan significantly, because each sublot is transferred separately to the next operation of a job. In the second stage, the sizes of the sublots are maximised without increasing the obtained makespan value. In this way, the quantity of sublots and transport activities is limited together with the related manufacturing cost. Two objectives are defined for the second stage. The first one is the maximisation of the sum of the sublot sizes of all operations, the second one is the maximisation of the number of the operations which do not need to be split at all. Mixed-integer linear programming, constraint programming and graph-based models are implemented for the problem. Two optimisation approaches are developed and compared in computational experiments for each stage and objective, one approach is based on a third-party solver, and the second one on an independent own implementation, namely a tabu search and a greedy constructive heuristic.     

Minimizing the expected flowtime in stochastic flow shops

In this paper we consider a flow shop with blocking, n jobs, m machines, and stochastic processing times. We show that if the jobs can be stochastically ordered, then a SEPT sequence minimizes the expected flowtime on two machines.     

Adaptive scheduling of batch servers in flow shops

Batch servicing is a common way of benefiting from economies of scale in manufacturing operations. Good examples of production systems that allow for batch processing are ovens found in the aircraft industry and in semiconductor manufacturing. In this paper we study the issue of dynamic scheduling of such systems within the context of multi-stage flow shops. So far, a great deal of research has concentrated on the development of control strategies, which only address the batch stage. This paper proposes an integral scheduling approach that also includes succeeding stages. In this way, we aim for shop optimization, instead of optimizing performance for a single stage. Our so-called look-ahead strategy adapts its scheduling decision to shop status, which includes information on a limited number of near-future arrivals. In particular, we study a two-stage flow shop, in which the batch stage is succeeded by a serial stage. The serial stage may be realized by a single machine or by parallel machines. Through an extensive simulation study it is demonstrated how shop performance can be improved by the proposed strategy relative to existing strategies.     

Scheduling a no-wait flow shop containing unbounded batching machines

We study the problem of scheduling n jobs in a no-wait flow shop consisting of m batching machines. Each job has to be processed by all the machines. All jobs visit the machines in the same order. A job completed on an upstream machine should be immediately transferred to the downstream machine. Batching machines can process several jobs simultaneously in a batch so that all jobs of the same batch start and complete together. The processing time of a batch is equal to the maximum processing time of the jobs in this batch. We assume that the capacity of any batch is unbounded. The problem is to find an optimal batch schedule such that the maximum job completion time, that is the makespan, is minimized. For m = 2, we prove that there exists an optimal schedule with at most two batches and construct such a schedule in O(n log n) time. For m = 3, we prove that the number of batches can be limited to nine and give an example where all optimal schedules have seven batches. Furthermore, we prove that the best schedules with at most one, two and three batches are 3-, 2- and 3/2-approximate solutions, respectively. The first two bounds are tight for corresponding schedules. Finally, we suggest an assignment method that solves the problem with m machines and at most r batches in O(n^{m(r-2)+1+[m/r]}) time, if m and r are fixed. The method can be generalized to minimize an arbitrary maximum cost or total cost objective function.     

Batch scheduling in differentiation flow shops for makespan minimisation

This paper considers a two-stage three-machine differentiation flow shop that comprises a common machine at stage 1 and two independent dedicated machines at stage 2. Two types of jobs are to be processed. All jobs must visit the stage-1 machine, and then the jobs of each type proceed to their dedicated machine for stage-2 processing. The stage-1 machine processes the jobs in batches, each of which, whenever formed, requires a constant setup time. The objective is to find a schedule that attains the minimum makespan. While the problem is strongly NP-hard, we investigate the case where the processing sequences of the two types of jobs are given and fixed. A polynomial-time dynamic programming algorithm is designed to solve this problem. We then deploy this algorithm to compute the lower bounds of the general problem.     

A hybrid genetic algorithm for flowshop lot streaming with setups and variable sublots

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.     

A simulation generator for dual-card kanban-controlled flow shops

This paper introduces a simulation generator for dual-card, kanban-controlled flow shops. Modelling kanban-controlled, pull manufacturing systems is a challenging task. The simulation generator eliminates modelling and the coding stages of simulation analysis and generates codes in SIMAN simulation language. An easy to use data-driven environment allows users to develop, edit, save and execute models without requiring any programming skills. The simulation generator is capable of simulating multi-product, multi-stage flow shops with multiple kanban cards (withdrawal and production order kanbans) and variable container sizes.