Scheduling just-in-time part supply for mixed-model assembly lines

With increasing cost competition and product variety, providing an efficient just-in-time (JIT) supply has become one of the greatest challenges in the use of mixed-model assembly line production systems. In the present paper, therefore, we propose a new approach for scheduling JIT part supply from a central storage center. Usually, materials are stored in boxes that are allotted to the consumptive stations of the line by a forklift. For such a real-world problem, a new model, a complexity proof as well as different exact and heuristic solution procedures are provided. Furthermore, a direct comparison with a simple two-bin kanban system is provided. Such a system is currently applied in the real-world industrial process that motivates our research. It becomes obvious that this policy is considerably outperformed according to the resulting inventory- and α-service levels. Moreover, at the interface between logistics and assembly operations, strategic management implications are obtained. Specifically, based on the new approach, it is the first time a statistical analysis is being made as to whether widespread Level Scheduling policies, which are well-known from the Toyota Production System, indeed facilitate material supply. Note that in the literature it is frequently claimed that this causality exists.     

Shortest-route formulation of mixed-model assembly line balancing problem

A shortest-route formulation of the mixed-model assembly line balancing problem is presented. Common tasks across models are assumed to exist and these tasks are performed in the same stations. The formulation is based on an algorithm which solves the single-model version of the problem. The mixed-model system is transformed into a single-model system with a combined precedence diagram. The model is capable of considering any constraint that can be expressed as a function of task assignments.     

Minimizing the number of workers in a paced mixed-model assembly line

We study a problem of minimizing the maximum number of identical workers over all cycles of a paced assembly line comprised of m stations and executing n parts of k types. There are lower and upper bounds on the workforce requirements and the cycle time constraints. We show that this problem is equivalent to the same problem without the cycle time constraints and with fixed workforce requirements. We prove that the problem is NP-hard in the strong sense if $m=4$ and the workforce requirements are station independent, and present an Integer Linear Programming model, an enumeration algorithm and a dynamic programming algorithm. Polynomial in k and polynomial in n algorithms for special cases with two part types or two stations are also given. Relations to the Bottleneck Traveling Salesman Problem and its generalizations are discussed.     

Controlling mixed-model assembly lines in real-time by using distributed systems

The production of large quantities is frequently handled by the use of assembly lines. These systems yield significant reductions of variable costs for the production of homogenous products. But due to increasing competition and differentiated demands, today it is no longer sufficient to offer only standardized products. To combine the wishes and requirements of the customers with the advantages of an efficient flow line production, different product variants are produced simultaneously on the same mixed-model assembly line. Therefore, the task of controlling such production processes is becoming more complex since an efficient production execution has to be realized in spite of the occurring oscillating work content of the different variants. Additionally, unforeseen disturbances in the production process can compromise its planned execution. To deal with these problems, this paper proposes a new approach for an adaptive real-time control of assembly lines that extends the pure sequencing problem by the integration of specific line-balancing aspects and the mapping of consequences of possible disturbance scenarios. Such a scenario could be, for instance, the loss of a worker, a material bottleneck or a machine breakdown. To guarantee an efficient continuation of the production process, the controlling instrument reacts instantly to a disturbance by adapting the current plan in a very short time, consisting of only a few cycle times, to reduce the additional costs caused by the disturbances.     

Designing a mixed-model,open-station assembly line using mixed-integer programming

An open-station assembly line that manufactures mixed models of sheet metal cabinets is considered in this research. The problem minimizes the total cost of the idle and utility times incurred in an assembly line with different line parameters (such as launch interval, station length, starting point of work, upstream walk, locus of the operator's movement, etc.) and operation sequences of the mixed models. An open-station system plays a significant controlling role in determining the optimal line parameters that minimize the total cost of idle and utility times in a mixed-model assembly line. Thus, a mixed-integer programming model for an open-station system is developed here to determine line parameters optimally. The model is tested on a three-station mixed-model line, which is a partial representation of a complete long assembly line. This research obtained a set of line parameters that minimize the total cost of idle and utility times optimally. Results indicate that the minimum total cost of idle and utility times in an open-station system decreases with line length. Other results pertinent to the line design are also demonstrated.     

Improved methods of assembly sequence determination for automatic assembly systems

The assembly sequence is determined using product unit cost as the performance measure. The global optimum for a given problem is found by partially enumerating assembly station configurations with branch and bound methods. The study shows that the proposed methods perform faster than simulated annealing for the example problems used. It is shown that the unit cost function is not necessarily convex which is assumed in previous research.     

A heuristic solution for fuzzy mixed-model line balancing problem

This paper addresses the mixed-model line balancing problem with fuzzy processing time. A fuzzy binary linear programming model is formulated for the problem. This fuzzy model is then transformed to a mixed zero–one program. Due to the complexity nature in handling fuzzy computation, new approximated fuzzy arithmetic operation is presented. A fuzzy heuristic is developed to solve this problem based on the aggregating fuzzy numbers and combined precedence constraints. The general idea of our approach is to arrange the jobs in a sequence by a varying-section exchange procedure. Then jobs are allocated into workstations based on these aggregated fuzzy times with the considerations of technological constraint and cycle time limit. Promising results are obtained by experiments.     

An endosymbiotic evolutionary algorithm for the integration of balancing and sequencing in mixed-model U-lines

This paper proposes a new evolutionary approach to deal with both balancing and sequencing problems in mixed-model U-shaped lines. The use of U-shaped lines is an important element in Just-In-Time production. For an efficient operation of the lines, it is important to have a proper line balancing and model sequencing. A new genetic approach, called endosymbiotic evolutionary algorithm, is proposed to solve the two problems of line balancing and model sequencing at the same time. The algorithm imitates the natural evolution process of endosymbionts that is an extension of existing cooperative or symbiotic evolutionary algorithm. The distinguishing feature of the proposed algorithm is that it maintains endosymbionts that are a combination of an individual and its symbiotic partner. The existence of endosymbionts can accelerate the speed that individuals converge to good solutions. This enhanced capability of exploitation together with the parallel search capability of traditional symbiotic algorithms results in finding better quality solutions than existing hierarchical approaches and symbiotic algorithms. A set of experiments are carried out, and the results are reported.     

Scheduling the part supply of mixed-model assembly lines in line-integrated supermarkets

Line-integrated supermarkets constitute a novel in-house parts logistics concept for feeding mixed-model assembly lines. In this context, supermarkets are decentralized logistics areas located directly in each station. Here, parts are withdrawn from their containers by a dedicated logistics worker and sorted just-in-sequence (JIS) into a JIS-bin. From this bin, assembly workers fetch the parts required by the current workpiece and mount them during the respective production cycle. This paper treats the scheduling of the part supply processes within line-integrated supermarkets. The scheduling problem for refilling the JIS-bins is formalized and a complexity analysis is provided. Furthermore, a heuristic decomposition approach is presented and important managerial aspects are investigated.     

Hybrid approaches to optimize mixed-model assembly lines in low-volume manufacturing

In this paper, a production planning problem for mixed-model assembly lines in low-volume manufacturing as can be found in aircraft manufacturing is considered. This type of manufacturing is labor-intensive. Low-volume production of huge-sized jobs, i.e. airplanes, is typical. Balancing labor costs and inventory holding costs assuming a given job sequence is the purpose of this paper. Therefore, worker assignments to each station and start times and processing times for each job on each station are determined. Two different mathematical models are proposed. The first formulation is a time-indexed linear formulation that allows for a flexible allocation of workers to periods and stations while the second one has a non-linear objective function and allows only for a fixed assignment of workers to stations. It is proven that the second formulation leads to a linear program with continuous decision variables if the values of the decision variables that determine the number of workers assigned to a station are given, while the first formulation contains even in this situation binary decision variables. Heuristics that hybridize the mathematical formulations with variable neighborhood search techniques are proposed. Computational experiments on randomly generated problem instances and on real-world instances demonstrate the high performance of the heuristics.     

Optimally routing and scheduling tow trains for JIT-supply of mixed-model assembly lines

In recent years, more and more automobile producers adopted the supermarket-concept to enable a flexible and reliable Just-in-Time (JIT) part supply of their mixed-model assembly lines. Within this concept, a supermarket is a decentralized in-house logistics area where parts are intermediately stored and then loaded on small tow trains. These tow trains travel across the shop floor on specific routes to make frequent small-lot deliveries which are needed by the stations of the line. To enable a reliable part supply in line with the JIT-principle, the interdependent problems of routing, that is, partitioning stations to be supplied among tow trains, and scheduling, i.e., deciding on the start times of each tow train’s tours through its assigned stations, need to be solved. This paper introduces an exact solution procedure which solves both problems simultaneously in polynomial runtime. Additionally, management implications regarding the trade-off between number and capacity of tow trains and in-process inventory near the line are investigated within a comprehensive computational study.     

Algorithms for Toyota's goal of sequencing mixed models on an assembly line with multiple workstations

Toyota's goal of sequencing mixed models on an assembly line is to keep the constant usage rate of every part used in the assembly line. This paper deals with Toyota's goal of sequencing mixed models on an assembly line with multiple workstations. A sequencing problem with Toyota's goal is formulated. Two algorithms based on different mechanisms, respectively modified goal chasing and simulated annealing, are developed for solving the sequencing problem. A number of numerical experiments are carried out for evaluating the efficiency of the algorithms. Computational results show that one of the algorithms generates good sub-optimal solutions with very short CPU times, while the other can reach optimal solutions with longer, but acceptable, CPU times.     

A survey on problems and methods in generalized assembly line balancing

Assembly lines are traditional and still attractive means of mass and large-scale series production. Since the early times of Henry Ford several developments took place which changed assembly lines from strictly paced and straight single-model lines to more flexible systems including, among others, lines with parallel work stations or tasks, customer-oriented mixed-model and multi-model lines, U-shaped lines as well as unpaced lines with intermediate buffers.In any case, an important decision problem, called assembly line balancing problem, arises and has to be solved when (re-) configuring an assembly line. It consists of distributing the total workload for manufacturing any unit of the product to be assembled among the work stations along the line.Assembly line balancing research has traditionally focused on the simple assembly line balancing problem (SALBP) which has some restricting assumptions. Recently, a lot of research work has been done in order to describe and solve more realistic generalized problems (GALBP). In this paper, we survey the developments in GALBP research.     

Several methods usable in production systems prediction

In this paper, we describe three methods based on the use of a dynamical system, the use of neural networks with rough sets, and the use of a fuzzy-logic method in order to predict the behavior of data processing extracted from a highly automated factory.The work presented here is a preliminary study done in order to develop a decision aid system for a highly automated factory in southern France (Merlin-Gérin). This factory produces low cost electrical circuit breakers in high volumes with short order delays. The aim is to predict the occurrence of ruptures in the production system where a rupture corresponds to a missed delivery date.The aim of our research is to model the global behavior of manufacturing systems, and then to correlate production tactical choices with their effects. We would like then to clarify the existing relations between some sectors of the enterprise. More precisely, the work carried out at Merlin-Gérin consists in a prediction of their nondelivery ratio, which is evaluated according to an analysis of historical data provided by production processing.     

A hybrid heuristic for a multi-objective real-life car sequencing problem with painting and assembly line constraints

We address a multi-objective version of the car sequencing problem, which consists in sequencing a given set of cars to be produced in a single day, minimizing the number of violations of assembly constraints and the number of paint color changes in the production line. We propose a set of heuristics for approximately solving this problem, based on the paradigms of the VNS and ILS metaheuristics, to which further intensification and diversification strategies have been added. Computational results on real-life test instances are reported. The work presented in this paper obtained the second prize in the ROADEF challenge 2005 sponsored by Renault.     

An evaluation of constructive heuristic methods for solving the alternative subgraphs assembly line balancing problem

This paper evaluates a set of constructive heuristic methods developed to solve the novel Alternative Subgraphs Assembly Line Balancing Problem (ASALBP), which considers variants for different parts of a production or manufacturing process. Each variant is represented by a precedence subgraph that defines the tasks to be performed and their processing times. The proposed methods use priority rules and random choice to select the assembly subgraphs and to assign the tasks to the stations in order to minimize the number of required workstations. The methods are evaluated by a computational experiment based on medium- and large-scale benchmark problems. This work is supported by the Spanish MCyT project DPI2004-03472, co-financed by FEDER, and by a Venezuelan Grant by the University of Los Andes.     

Multi-level production scheduling for a class of flexible machining and assembly systems

A class of machining and assembly systems characterised by a flat assembly component structure, the existence of families of similar items, non-negligible setups and fast material flow between work-centres is considered. A hierarchical production scheduling framework is proposed for this class of systems. The decision problems at each level of the hierarchy are identified and formulated. The formulations constitute a sufficiently accurate reflection of reality, while at the same time leading to tractable mathematical models that can be handled by carefully chosen and adapted optimisation techniques. The models can, when combined with suitable knowledge bases form the core of an effective multi-pass, hierarchical decision support system. Possible srategies for coordinating the various decision problems at the different levels of the hierarchy are also discussed.This work was supported by the ACME Directorate of the Science and Engineering Research Council of the United Kingdom, Grant No. GR/D 51476, and was carried out in collaboration with Lucas Aerospace (Engines Division), Shaftmoor Lane, Birmingham, U.K.On leave from Warsaw University of Technology, Institute of Automatic Control, Nowowiejska 15/19, 00-665 Warszawa, Poland.     

Solving a robotic assembly line balancing problem using efficient hybrid methods

In this paper we are studying a robotic assembly line balancing problem. The goal is to maximize the efficiency of the line and to balance the different tasks between the robots by defining the suitable tasks and components to assign to each robot. We are interested in a robotic line which consists of seizing the products on a moving conveyor and placing them on different location points. The performances evaluations of the system are done using a discret event simulation model. This latter has been developed with C++ language. As in our industrial application we are bounded by the execution time, we propose some resolution methods which define the suitable component and point positions in order to define the strategy of pick and place for each robot. These methods are based on the ant colony optimization, particle swarm optimization and genetic algorithms. To enhance the quality of the developed algorithms and to avoid local optima, we have coupled these algorithms with guided local search. After that, an exact method based on full enumeration is also developed to assess the quality of the developed methods. Then, we try to select the best algorithm which is able to get the best solutions with a small execution time. This is the main advantage of our methods compared to exact methods. This fact represents a great interest taking in consideration that the selected methods are used to manage the functioning of real industrial robotic assembly lines. Numerical results show that the selected algorithm performs optimally for the tested instances in a reasonable computation time and satisfies the industrial constraint.     

A branch-and-bound based solution approach for the mixed-model assembly line-balancing problem for minimizing stations and task duplication costs

A common assumption in the literature on mixed-model assembly line balancing is that a task that is common to multiple models must be assigned to a single station. In this paper, we relax this restriction, and allow a common task to be assigned to different stations for different models. We seek to minimize the sum of costs of the stations and the task duplication. We develop an optimal solution procedure based on a backtracking branch-and-bound algorithm and evaluate its performance via a large set of experiments. A branch-and-bound based heuristic is then developed for solving large-scale problems. The heuristic solutions are compared with a lower bound and experiments show that the heuristic provides much better solutions than those obtained by traditional approaches.     

On the convergence of line iterative methods for cyclically reduced non-symmetrizable linear systems

Summary. We derive analytic bounds on the convergence factors associated with block relaxation methods for solving the discrete two-dimensional convection-diffusion equation. The analysis applies to the reduced systems derived when one step of block Gaussian elimination is performed on red-black ordered two-cyclic discretizations. We consider the case where centered finite difference discretization is used and one cell Reynolds number is less than one in absolute value and the other is greater than one. It is shown that line ordered relaxation exhibits very fast rates of convergence. Received March 3, 1992/Revised version received July 2, 1993