Lot Splitting Under Learning Effects with Minimal Revenue Requirements and Multiple Lot Types

The lot splitting problem in the presence of learning is addressed. This work is an extension of an approach proposed for splitting in the case of a single item. We address the issue of a minimal revenue requirement from partial deliveries until a predetermined time. This is achieved by imposing a constraint on what is originally an unconstrained optimization problem. When sublots of different items are involved, the optimal splitting decisions have to be combined with the sequencing of the deliveries. Numerical examples are presented to demonstrate the proposed approach.     

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.     

Lot streaming in the presence of learning in sublot-attached setup times and processing times

Lot streaming is the process of splitting a production lot into sublots, and then processing the sublots on different machines in an overlapping manner. In this paper, we study the use of lot streaming for processing a lot in a two-machine flow shop when a sublot-attached setup time is incurred before the processing of each sublot. The objective is to determine number of sublots and sublot sizes and minimize makespan. We also consider the case when the effect of learning is observed in processing times, sublot-attached setup times, or, both. We present closed-form expressions for optimal sublot sizes and efficient search schemes to determine optimal number of sublots.     

Lot Streaming Flow Shop with a Heterogeneous Machine

Abstract

It is possible to obtain greater productivity of a production system by overlapping the operations required to process a manufacturing order. This methodology, known as lot streaming, requires dividing the production order (lot) into smaller sublots. In this article, we study production systems that include machines that operate in batch mode (processing a group of units at the same time) and single processing machines (processing one unit at a time) arranged in a flow shop configuration, that is all jobs must go through the same production stages in the same order. The obtained results show that addressing the problem with consistent sublots (a common sublot size used for the whole process) is inefficient. On the other hand, addressing the problem considering the sizing of sublots for each machine (variable sublots) greatly improves the quality of the solution but is computationally intensive (limiting the size of the problem that can be solved). Therefore, a decomposition procedure is proposed on the decision of sublots sizing. This procedure greatly improves the solution obtained using consistent sublots and does so with lower computational requirements than the variable sublots approach.     

Lot streaming in a multiple product permutation flow shop with intermingling

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 small- and medium-sized instances.     

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 genetic algorithm for the multi-stage and parallel-machine scheduling problem with job splitting – A case study for the solar cell industry

This paper studies a multi-stage and parallel-machine scheduling problem with job splitting which is similar to the traditional hybrid flow shop scheduling (HFS) in the solar cell industry. The HFS has one common hypothesis, one job on one machine, among the research. Under the hypothesis, one order cannot be executed by numerous machines simultaneously. Therefore, multiprocessor task scheduling has been advocated by scholars. The machine allocation of each order should be scheduled in advance and then the optimal multiprocessor task scheduling in each stage is determined. However, machine allocation and production sequence decisions are highly interactive. As a result, this study, motivated from the solar cell industry, is going to explore these issues. The multi-stage and parallel-machine scheduling problem with job splitting simultaneously determines the optimal production sequence, multiprocessor task scheduling and machine configurations through dynamically splitting a job into several sublots to be processed on multiple machines. We formulate this problem as a mixed integer linear programming model considering practical characteristics and constraints. A hybrid-coded genetic algorithm is developed to find a near-optimal solution. A preliminary computational study indicates that the developed algorithm not only provides good quality solutions but outperforms the classic branch and bound method and the current heuristic in practice.     

Jobshop lot streaming with routing flexibility,sequence-dependent setups,machine release dates and lag time

Lot streaming is a technique of splitting production lots into smaller sublots in a multi-stage manufacturing system so that operations of a given lot can overlap. This technique can reduce the manufacturing makespan and is an effective tool in time-based manufacturing. Research on lot streaming models and solution procedures for flexible jobshops has been limited. The flexible jobshop scheduling problem is an extension of the classical jobshop scheduling problem by allowing an operation to be assigned to one of a set of eligible machines during scheduling. In this paper we develop a lot streaming model for a flexible jobshop environment. The model considers several pragmatic issues such as sequence-dependent setup times, the attached or detached nature of the setups, the machine release date and the lag time. In order to solve the developed model efficiently, an island-model parallel genetic algorithm is proposed. Numerical examples are presented to demonstrate the features of the proposed model and compare the computational performance of the parallel genetic algorithm with the sequential algorithm. The results are very encouraging.     

Aligning workload control theory and practice: lot splitting and operation overlapping issues

This paper addresses the problem of lot splitting in the context of workload control (WLC). Past studies on WLC assumed that jobs released to the shop floor proceed through the different stages of processing without being split. However, in practice, large jobs are often split into smaller transfer sublots so that they can move more quickly and independently through the production process and allow operations overlapping relating to the same job. This paper assesses the performance of different lot splitting policies for job release and dispatching strategies under lot splitting. A new dispatching rule was designed to specifically take advantage of lot splitting and operations overlapping in the context of WLC. Discrete-event simulation is used to assess system performance in relation to the ability to provide shorter delivery times and on time deliveries. Results highlight the importance of releasing the sublots of the same job together and demonstrate that combining an effective lot splitting policy with an appropriate dispatching rule can enhance the performance of production systems.     

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.     

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.     

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.     

Lot-splitting decisions and learning effects

We consider a lot-splitting model where the unit manufacturing time follows a learning curve. Our objective is to maximize the net present value of the total revenue collected at the delivery of the sublots. An algorithm is developed to solve the problem. Computational experiments are conducted to study the performance of two 'convenient' operational approaches, namely the equal sublot size approach and the equal time interval approach. The computational results suggest that these two solution approaches are nearly optimal and that the net present value of the total revenue becomes less sensitive to the sublot sizes as the learning effect increases.     

An efficient heuristic approach for parallel machine scheduling with job splitting and sequence-dependent setup times

In this paper, we consider a simplified real-life identical parallel machine scheduling problem with sequence-dependent setup times and job splitting to minimize makespan. We propose a heuristic to solve this problem. Our method is composed of two parts. The problem is first reduced into a single machine scheduling problem with sequence-dependent setup times. This reduced problem can be transformed into a Traveling Salesman Problem (TSP), which can be efficiently solved using Little's method. In the second part, a feasible initial solution to the original problem is obtained by exploiting the results of the first part. This initial solution is then improved in a step by step manner, taking into account the setup times and job splitting. We develop a lower bound and evaluate the performances of our heuristic on a large number of randomly generated instances. The solution given by our heuristic is less than 4.88% from the lower bound.     

An application of genetic algorithms to lot-streaming flow shop scheduling

A Hybrid Genetic Algorithm (HGA) approach is proposed for a lot-streaming flow shop scheduling problem, in which a job (lot) is split into a number of smaller sublots so that successive operations can be overlapped. The objective is the minimization of the mean weighted absolute deviation of job completion times from due dates. This performance criterion has been shown to be non-regular and requires a search among schedules with intermittent idle times to find an optimal solution. For a given job sequence, a Linear Programming (LP) formulation is presented to obtain optimal sublot completion times. Objective function values of LP solutions are used to guide the HGA's search toward the best sequence. The performance of the HGA approach is compared with that of a pairwise interchange method.     

Lot-splitting approach of a hybrid manufacturing system under CONWIP production control: a mathematical model

This paper discusses the advantages of lot splitting in hybrid manufacturing environments where cellular and functional layouts are combined under Constant Work in Process (CONWIP) production control. The proposed model fills a research gap in the related literature by applying lot splitting and pull production simultaneously. A linear CONWIP control mathematical model that minimises the average flow time is developed in case of lot splitting. The developed model has sequence-dependent set-up times. The demand level, coefficient of variation (CV) impact and set-up time reduction effect on CONWIP production control are also investigated. The model is solved using GAMS21.6 optimisation software; the optimal backlog list, the number and size of sublots are reported. The proposed model is compared with lot production under push control in different settings as well as with two different heuristics from the literature. Experimental results indicate that in all settings, the lot splitting is more advantageous than lot production in terms of average flow time. CV has a greater effect than set-up time reduction on average flow time.     

On discrete lot streaming in no-wait 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 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 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.     

Flux difference splitting for the Euler equations with axial symmetry

An approximate (linearised) Riemann solver is presented for the solution of the Euler equations of gas dynamics for axially symmetric flows. The method is Roe's flux difference splitting with a technique for dealing with source terms and incorporates operator splitting. Results for the problem of a converging spherical shock are presented. This work forms part of the research programme of the Institute for Computational Fluid Dynamics at the Universities of Oxford and Reading and was funded by A.W.R.E., Aldermaston under contract no. NSN/13B/2A88719.     

Optimal inspection sublots for deteriorating batch production

This paper analyzes a problem of optimal inspection intervals for a failure-prone batch production facility. The model makes a seemingly minor modification to similar models that have appeared recently, but which results in a significant change in the form of the optimal policy. Optimal solutions are developed for both continuous and integer valued sublot sizes. The paper also examines the effects of inspection sublots in an economic lot sizing context and shows that a simple, exact modification of the Economic Production Quantity formula is often possible in the continuous relaxation of the problem.     

Analysis of gap times in a two-stage stochastic flowshop with overlapping operations

The impact of transfer batching (also referred to as lot splitting) on the performance of flowshops has received widespread attention in the literature. Most papers have emphasized the usefulness of lot splitting in cutting down average flow times, as it enables the overlapping of operations at different stages of the flowshop. However, while most analytical papers have studied deterministic flowshops, an important downside of lot splitting has been overlooked; i.e., the occurrence of idle time between the processing of consecutive sublots belonging to the same process batch (referred to as gap times). Gap times add no value to the product; they merely increase the process batch makespan at the different stages. In deterministic systems, these gap times may be avoided by balancing the processing rates of the different machines in the shop; in stochastic settings, however, they may occur even when the system is perfectly balanced, due to the inherent variability in the setup and processing times. Studying a two-stage flowshop with a single product type, this paper provides insight into the behavior of the gap times, and develops an approximation for the process batch makespan at the second stage in terms of the system characteristics and the lot splitting policy.