Searching optimal resequencing and feature assignment on an automated assembly line

The resequencing and feature assignment problem (RFAP) appears among jobs in the assembly line, especially in the automotive industry. Each job in the assembly line must be assigned a feature from its feasible feature set. However, a changeover cost is incurred between two consecutive jobs with different features. To minimize the total changeover cost, the job sequence needs to be rearranged, but the rearrangement is restricted to the number of offline buffers. The RFAP turns out to be ????-hard in the strong sense. Based on a beam search heuristic to generate upper bounds of optimum solutions, we have proposed an iterative search scheme which can achieve optimum solutions in a reasonably short time, for cases sized as large as that in reality. Extensive experiments have shown very favourable results for our methods in terms of both the solution quality and the time efficiency.     

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.     

An optimal (Q,r) policy for a multipart assembly system under stochastic part procurement lead times

We consider an EOQ-type model for a simple production system, where a number of parts are acquired to produce a single product and the part procurement lead times are random. Assembly is instantaneous and takes place intermittently in batches but cannot start until all the parts are available. The problem is to simultaneously determine when to order each part and what lot size to produce, namely to determine the reorder point for each part and the assembly lot size, so that the average total cost per unit time, composed of the setup cost, inventory holding costs for the parts and the assembled product, and the shortage cost for the assembled product, is minimized. We then develop a tailormade solution method for this problem to obtain a global optimal solution by taking advantage of the structure of the problem formulation, where the nonlinear programming problem is decomposed into a family of subproblems parametrized by the average assembly delay time. Numerical experiments are then conducted for the case of twopart problems, and some interesting observations are made.     

Packing items to feed assembly lines

We treat a practical application of packing problems in feeding assembly lines. This study was motivated by a real situation encountered in the shop floor of a major automobile industry plant in Brazil. The assembly line feed problem (LFP) consists in how pack the items in the available containers to meet the line work centers’ requirements with a minimum total cost over the planning horizon. LFP is a variable-sized bin packing problem that has two special features: (i) a cardinality constraint on each bin’s size; and, (ii) a cost structure such that each bin’s cost varies according to the items that are packed in it. We propose an integer programming model and a GRASP heuristic for LFP. Numerical results on real-life test instances are reported.     

Supply chain models for an assembly system with preprocessing of raw materials

In this paper, we investigate the material procurement and delivery policy in a production system where raw materials enter into the assembly line from two different flow channels. The system encompasses batch production process in which the finished product demand is approximately constant for an infinite planning horizon. Two distinct types of raw materials are passed through the assembly line before to convert them into the finished product. Of the two types of raw materials, one type requires preprocessing inside the facility before the assembly operation and other group is fed straightway in the assembly line. The conversion factors are assigned to raw materials to quantify the raw material batch size required. To analyze such a system, we formulate a nonlinear cost function to aggregate all the costs of the inventories, ordering, shipping and deliveries. An algorithm using the branch and bound concept is provided to find the best integer values of the optimal solutions. The result shows that the optimal procurement and delivery policy minimizes the expected total cost of the model. Using a test problem, the inventory requirements at each stage of production and their corresponding costs are calculated. From the analysis, it is shown that the rate and direction change of total cost is turned to positive when delivery rates per batch reaches close to the optimal value and the minimum cost is achieved at the optimal delivery rate. Also, it is shown that total incremental cost is monotonically increasing, if the finished product batch size is increased, and if, inventory cost rates are increased. We examine a set of numerical examples that reveal the insights into the procurement-delivery policy and the performance of such an assembly type inventory model.     

Incorporating ergonomic risks into assembly line balancing

In manufacturing, control of ergonomic risks at manual workplaces is a necessity commanded by legislation, care for health of workers and economic considerations. Methods for estimating ergonomic risks of workplaces are integrated into production routines at most firms that use the assembly-type of production. Assembly line re-balancing, i.e., re-assignment of tasks to workers, is an effective and, in case that no additional workstations are required, inexpensive method to reduce ergonomic risks. In our article, we show that even though most ergonomic risk estimation methods involve nonlinear functions, they can be integrated into assembly line balancing techniques at low additional computational cost. Our computational experiments indicate that re-balancing often leads to a substantial mitigation of ergonomic risks.     

Coordination in decentralized assembly systems with uncertain component yields

The literature on assembly systems with random component yields has focused on centralized systems, where a single decision maker chooses all components’ production quantities and incurs all the costs. We consider a decentralized setting where the component suppliers choose their production quantities based solely on their own cost/reward structure, and the assembly firm makes ordering decisions based on its own cost/reward structure. When the suppliers control their inputs but the outputs exhibit random yields, coordination in such systems becomes quite complex. In such situations, incentive alignment control mechanisms are needed so that the suppliers will choose production quantities as in the centralized system case. One such mechanism is to penalize the supplier with the worse delivery performance. We analyze the conditions under which system coordination is achieved while respecting participation constraints. Further, we determine the optimal component ordering policy for the assembly firm and derive the optimal coordinating penalties.     

Generation of assembly graphs by systematic analysis of assembly structures

In assembly line balancing problems, parallel execution of assembly operations is often advocated because of its enhanced flexibility and minimum lead-time. Although the theoretical maximum number of possible assembly sequences combinatorially explodes with the number of components in a product, graphical representations can depict these sequences in a surveyable way. The AND/OR graph representation is an appropriate basis for optimum sequence selection, which can be achieved via heuristic, metaheuristic, and exact methods. The exact method, based on binary linear programming, is described. To arrive at the appropriate model, a novel approach for AND/OR graph generation, based on subassembly detection, is presented. The method is demonstrated with simple cases and next extended to increasingly complex products. A modification of the optimization method is applied, which enables a search for sequences with maximum parallelism.     

Due date assignment for multistage assembly systems

This paper is concerned with the study of the constant due-date assignment policy in a multistage assembly system. The multistage assembly system is modeled as an open queueing network. It is assumed that the product order arrives according to a Poisson process. In each service station, there is either one or infinite machine with exponentially distributed processing time. The transport times between every pair of service stations are independent random variables with generalized Erlang distributions. It is assumed that each product has a penalty cost that is some linear function of its due-date and its actual completion time. The due date is found by adding a constant to the time that the order arrives. This constant value is the constant lead time that a product might expect between time of placing the order and time of delivery. By applying the longest path analysis in queueing networks, we obtain the distribution function of manufacturing lead time. Then, the optimal constant lead time is computed by minimizing the expected aggregate cost per product. Finally, the results are verified by Monte Carlo simulation.     

Complexities and algorithms for synchronized scheduling of parallel machine assembly and air transportation in consumer electronics supply chain

In this paper, we study the problem of synchronized scheduling of assembly and air transportation to achieve accurate delivery with minimized cost in consumer electronics supply chain. This problem was motivated by a major PC manufacturer in consumer electronics industry. The overall problem is decomposed into two sub-problems, which consist of an air transportation allocation problem and an assembly scheduling problem. The air transportation allocation problem is formulated as an integer linear programming problem with the objective of minimizing transportation cost and delivery earliness tardiness penalties. The assembly scheduling problem seeks to determine a schedule ensuring that the orders are completed on time and catch the flights such that the waiting penalties between assembly and transportation is minimized. The problem is formulated as a parallel machine scheduling problem with earliness penalties. The computational complexities of the two sub-problems are investigated. The air transportation allocation problem with split delivery is shown to be solvable. The parallel machine assembly scheduling problem is shown to be NP-complete. Simulated annealing based heuristic algorithms are presented to solve the parallel machine problem.     

State-of-the-art exact and heuristic solution procedures for simple assembly line balancing

The assembly line balancing problem arises and has to be solved when an assembly line has to be configured or redesigned. It consists of distributing the total workload for manufacturing any unit of the product to be assembled among the work stations along the line. The so-called simple assembly line balancing problem (SALBP), a basic version of the general problem, has attracted attention of researchers and practitioners of operations research for almost half a century.In this paper, we give an up-to-date and comprehensive survey of SALBP research with a special emphasis on recent outstanding and guiding contributions to the field.     

Lot-sizing two-echelon assembly systems with random yields and rigid demand

We consider a two-echelon assembly system producing a single final product for which the demand is known. The first echelon consists of several parallel stages, whereas the second echelon consists of a single assembly stage. We assume that the yield at each stage is random and that demand needs to be satisfied in its entirety; thus, several production runs may be required. A production policy should specify, for each possible configuration of intermediate inventories, on which stage to produce next and the lot size to be processed. The objective is to minimize the expected total of setup and variable production costs.We prove that the expected cost of any production policy can be calculated by solving a finite set of linear equations whose solution is unique. The result is general in that it applies to any yield distribution. We also develop efficient algorithms leading to heuristic solutions with high precision and, as an example, provide numerical results for binomial yields.     

Sequencing mixed-model assembly lines: Survey,classification and model critique

Manufacturers in a wide range of industries nowadays face the challenge of providing a rich product variety at a very low cost. This typically requires the implementation of cost efficient, flexible production systems. Often, so called mixed-model assembly lines are employed, where setup operations are reduced to such an extent that various models of a common base product can be manufactured in intermixed sequences. However, the observed diversity of mixed-model lines makes a thorough sequence planning essential for exploiting the benefits of assembly line production. This paper reviews and discusses the three major planning approaches presented in the literature, mixed-model sequencing, car sequencing and level scheduling, and provides a hierarchical classification scheme to systematically record the academic efforts in each field and to deduce future research issues.     

Continuous location of an assembly station

Demand existing at client points in the plane for several products should be met. Products have to be assembled from different components obtainable at given prices at various sources with known production capacities. The optimal design of the resulting supply chain must be determined, including the location of a central assembly station in the plane, so as to minimize the total operational cost comprising buying and transport of components as well as transport of final products. This problem leads to a difficult nonlinear and non-convex optimization problem for which a locally convergent algorithm is proposed. Some computational results are presented.     

Cost-oriented assembly line balancing: Model formulations,solution difficulty,upper and lower bounds

This paper deals with cost-oriented assembly line balancing. First we focus on the special objective function and a formal problem statement. Then we concentrate on general model formulations that can be solved by standard optimisation tools and introduce several improvements to existent models. These models are designed for either general branch-and-bound techniques with LP-relaxation or general implicit enumeration techniques. Further we discuss the solution difficulty of the problem and show that the “maximally-loaded-station-rule” has to be replaced by the “two-stations-rule”. Compared to the time-oriented version, this causes an enormous increase in solution difficulty. We introduce improved and new bounds for the number of stations and for the relevant costs per product unit. These are used in the general model formulations as well as in specially designed optimisation methods. Finally we give a brief overview of these specially designed methods that are discussed in detail in Amen (2000a,b, 2001).     

Optimization framework for process scheduling of operation-dependent automobile assembly lines

Productivity, cost, and completion time are regarded as performance measures for assembly production management. The traditional decomposition of Assembly Line Balancing (ALB) and Car sequencing (CS) does not work well, especially when operations belonging to different car types are sequence-dependent and time overlap between two successive workstations is allowed. In this paper, we first use a motivating industrial-scale example to demonstrate that the traditional ALB/CS decomposition method could not satisfy modern continuous production demands in a flexible assembly line. Then, we present a new optimization objective to scale the Operation Process Precision (OPP) that relates to the operation assignment sequence. Lastly, we propose a two-stage hierarchical optimization framework to solve the CS, the operation allocation, and the operation sequence problems. This framework consists of (a) a new Mixed Integer Linear Programming (MILP) model for sequencing automobiles and allocating their operations to each station, and (b) a novel MILP model for determining the operation sequence and timing of each car type. The motivating industrial case is revisited with the proposed framework to illustrate its validity and efficiency.     

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.     

Application of robust optimization to automated test assembly

In automated test assembly (ATA), 0-1 linear programming (0-1 LP) methods are applied to select questions (items) from an item bank to assemble an optimal test. The objective in this 0-1 LP optimization problem is to assemble a test that measures, in as precise a way as possible, the ability of candidates. Item response theory (IRT) is commonly applied to model the relationship between the responses of candidates and their ability level. Parameters that describe the characteristics of each item, such as difficulty level and the extent to which an item differentiates between more and less able test takers (discrimination) are estimated in the application of the IRT model. Unfortunately, since all parameters in IRT models have to be estimated, they do have a level of uncertainty to them. Some of the other parameters in the test assembly model, such as average response times, have been estimated with uncertainty as well. General 0-1 LP methods do not take this uncertainty into account, and overestimate the predicted level of measurement precision. In this paper, alternative robust optimization methods are applied. It is demonstrated how the Bertsimas and Sim method can be applied to take this uncertainty into account in ATA. The impact of applying this method is illustrated in two numerical examples. Implications are discussed, and some directions for future research are presented.     

A Lagrangian relaxation approach to the mixed-product assembly line sequencing problem: A case study of a door-lock company in Taiwan

In mixed-product assembly line sequencing, the production resources required for the assembly lines should be scheduled to minimize the overall cost and meet customer demand. In this paper, we study an assembly line sequencing problem for the door-lock industry in Taiwan and develop an integer programming formulation with realistic constraints. The complex solution space makes the resulting program difficult to solve using commercial optimization packages. Therefore, a heuristic based on the Lagrangian relaxation principle is developed to solve this problem efficiently. We evaluate the efficiency of the developed Lagrangian relaxation heuristic by comparing its solutions with those obtained using a commercial optimization package: the computational results show that the developed heuristic solves the real-world problem faster than the optimization package by almost 15 times in CPU time at a comparable solution quality.     

Balancing assembly lines with tabu search

Balancing assembly lines is a crucial task for manufacturing companies in order to improve productivity and minimize production costs. Despite some progress in exact methods to solve large scale problems, softwares implementing simple heuristics are still the most commonly used tools in industry. Some metaheuristics have also been proposed and shown to improve on classical heuristics but, to our knowledge, no computational experiments have been performed on real industrial applications to clearly assess their performance as well as their flexibility. Here we present a new tabu search algorithm and discuss its differences with respect to those in the literature. We then evaluate its performance on the Type I assembly line balancing problem. Finally, we test our algorithm on a real industrial data set involving 162 tasks, 264 precedence constraints, and where the assembly is carried out on a sequential line with workstations located on both sides of the conveyor, with two possible conveyor heights and no re-positioning of the product. We discuss the flexibility of the metaheuristic and its ability to solve real industrial cases.