Simulated annealing algorithms for the multi-manned assembly line balancing problem: minimising cycle time

Multi-manned assembly lines are often designed to produce big-sized products, such as automobiles and trucks. In this type of production lines, there are multi-manned workstations where a group of workers simultaneously performs different operations on the same individual product. One of the problems, that managers of such production lines usually encounter, is to produce the optimal number of items using a fixed number of workstations, without adding new ones. In this paper, such a class of problems, namely, the multi-manned assembly line balancing problem is addressed, with the objective of minimising the cycle time. A mixed-integer mathematical programming formulation is proposed for the considered problem. This model has the primary objective of minimising the cycle time for a given number of workstations and the secondary objective of minimising the total number of workers. Since the addressed problem is NP-hard, two meta-heuristic approaches based on the simulated annealing algorithm have been developed: ISA and DSA. ISA solves the problem indirectly while DSA solves it directly. The performance of the two algorithms are tested and compared on a set of test problems taken from the literature. The results show that DSA outperforms ISA in term of solution quality and computational time.     

Profit-oriented disassembly-line balancing

As product and material recovery has gained importance, disassembly volumes have increased, justifying construction of disassembly lines similar to assembly lines. Recent research on disassembly lines has focused on complete disassembly. Unlike assembly, the current industry practice involves partial disassembly with profit-maximization or cost-minimization objectives. Another difference between assembly and disassembly is that disassembly involves additional precedence relations among tasks due to processing alternatives or physical restrictions. In this study, we define and solve the profit-oriented partial disassembly-line balancing problem. We first characterize different types of precedence relations in disassembly and propose a new representation scheme that encompasses all these types. We then develop the first mixed integer programming formulation for the partial disassembly-line balancing problem, which simultaneously determines (1) the parts whose demand is to be fulfilled to generate revenue, (2) the tasks that will release the selected parts under task and station costs, (3) the number of stations that will be opened, (4) the cycle time, and (5) the balance of the disassembly line, i.e. the feasible assignment of selected tasks to stations such that various types of precedence relations are satisfied. We propose a lower- and upper-bounding scheme based on linear programming relaxation of the formulation. Computational results show that our approach provides near optimal solutions for small problems and is capable of solving larger problems with up to 320 disassembly tasks in reasonable time.     

Stochastic two-sided U-type assembly line balancing: a genetic algorithm approach

In this paper, a novel stochastic two-sided U-type assembly line balancing (STUALB) procedure, an algorithm based on the genetic algorithm and a heuristic priority rule-based procedure to solve STUALB problem are proposed. With this new proposed assembly line design, all advantages of both two-sided assembly lines and U-type assembly lines are combined. Due to the variability of the real-life conditions, stochastic task times are also considered in the study. The proposed approach aims to minimise the number of positions (i.e. the U-type assembly line length) as the primary objective and to minimise the number of stations (i.e. the number of operators) as a secondary objective for a given cycle time. An example problem is solved to illustrate the proposed approach. In order to evaluate the efficiency of the proposed algorithm, test problems taken from the literature are used. The experimental results show that the proposed approach performs well.     

A method for assembly line balancing with more than one worker in each station

The typical assembly line is serial with no paralleling of work elements and work stations allowed. The series assumption restricts the least cycle time to be the maximum work element time, thus limiting the production rate.

An alternative way to increase the production rate (hence lowering the cycle time) is by assigning multiple workers to one work station. In this paper we propose the parallel assignment method (PAM) for achieving a higher production rate.

In the first phase of PAM the work elements are assigned to work stations under the multi-stage upper time limits. But as two or more workers are assigned to one station, the operation time of each worker is longer in proportion to the number of workers at the station.

Therefore, in the second phase of PAM work elements are assigned to the workers in each station so that each of the workers may perform shorter work elements where the work element is a minimum rational indivisible work item.

Practical problems which cannot he solved by serial line balancing methods are provided and.solved to explain the effectiveness of PAM.     

Supply chain optimisation with U-type assembly line balancing

In supply chain optimisation problems, determining the location and number of facilities is considered at a strategic level, while mid-term and short-term decisions such as those concerning assembly policy, inventory levels, lot sizes and scheduling are handled at the tactical and operational levels. However, considering these decisions simultaneously is almost always ignored during the optimisation of distribution/production processes. The aim of the study is to optimise the supply chain network (strategic level), including manufacturers, assemblers and customers, while simultaneously balancing the U-type assembly lines (tactical level) in assemblers. A nonlinear mixed integer mathematical model is proposed to minimise the total costs and the number of assembly stations while minimising the total fixed costs of stations. To show the validity and usefulness of the proposed model, a numerical example with different scenarios and sensitivity analyses is given and discussed.     

Robotic U-shaped assembly line balancing using particle swarm optimization

Automation in an assembly line can be achieved using robots. In robotic U-shaped assembly line balancing (RUALB), robots are assigned to workstations to perform the assembly tasks on a U-shaped assembly line. The robots are expected to perform multiple tasks, because of their capabilities. U-shaped assembly line problems are derived from traditional assembly line problems and are relatively new. Tasks are assigned to the workstations when either all of their predecessors or all of their successors have already been assigned to workstations. The objective function considered in this article is to maximize the cycle time of the assembly line, which in turn helps to maximize the production rate of the assembly line. RUALB aims at the optimal assignment of tasks to the workstations and selection of the best fit robot to the workstations in a manner such that the cycle time is minimized. To solve this problem, a particle swarm optimization algorithm embedded with a heuristic allocation (consecutive) procedure is proposed. The consecutive heuristic is used to allocate the tasks to the workstation and to assign a best fit robot to that workstation. The proposed algorithm is evaluated using a wide variety of data sets. The results indicate that robotic U-shaped assembly lines perform better than robotic straight assembly lines in terms of cycle time.     

ANTBAL: an ant colony optimization algorithm for balancing mixed-model assembly lines with parallel workstations

This paper presents ANTBAL, an ant colony optimization algorithm for balancing mixed-model assembly lines. The proposed algorithm accounts for zoning constraints and parallel workstations and aims to minimize the number of operators in the assembly line for a given cycle time. In addition to this goal, ANTBAL looks for solutions that smooth the workload among workstations, which is an important aspect to account for in balancing mixed-model assembly lines. Computational experience shows the superior performance of the proposed algorithm.     

A multiple criteria decision making approach for the assembly line balancing problem

In practice, measuring total profit for a given assembly line balancing (ALB) problem is an involved process that is sometimes impossible because of much uncertainty and unavailability of data. In this paper, ALB is formulated as a multiple criteria problem where several easily quantifiable criteria (objectives) and constraints are defined. Objective functions include number of stations, cycle time, and operations cost, all to be minimized. After a discussion of applications and an overview of multiple criteria decision making (MCDM) approaches for ALB, the MCDM-ALB problem is formulated. Basic definitions and properties of MCDM for ALB are outlined and then an interactive MCDM approach is developed for solving the MCDM-ALB problem. To solve the problem, the decision maker (DM) interactively responds to paired comparisons of multicriteria alternatives. Through a limited number of interactions with the DM, the most preferred alternative is obtained. Many unexplored alternatives are eliminated by using a one-dimensional multiple criteria search. To present the DM's preference, we use the most flexible and general class of utility functions; namely, either quasi-concave or quasi-convex utility functions. An example is solved and computational experiments are reported. It is demonstrated that the bicriteria ALB, cycle time versus number of stations, can be easily solved by using the developed procedure. For the case that there are different criteria, an improved goal programming is developed to solve the MCDM-ALB problem. The motivation for development of the method, based on a case study of a lamp-making plant of the General Electric Company, is discussed.     

Sequencing procedure for balancing the workloads variations in case of mixed model assembly system with multiple secondary feeder lines

In order to increase flexibility and reduce costs, assembly systems are changing from simple mixed-model assembly lines, to multi-lines systems, where some components are assembled in secondary lines, called feeder lines, connected to the main line by a ‘pull philosophy’. The production of different models in such a complex multi-lines assembly system, where the tasks to perform could be very different from model to model, impacts the production with very high workload time variations, with the consequence of lack of productivity. If operators can perform tasks on different stations on both the feeder and the main lines these time variations can generally be absorbed. But if working across the stations is not possible (closed stations), the balancing of these workload time variations becomes critical. In such contexts the consolidated approach, that allows to configure mixed-model-multi lines assembly system with a single average model representative of the whole mix, can be very limited and is unable to bring substantial results. This paper aims to introduce an innovative sequencing model for mixed-model-multi-lines system, in the case of closed stations, in which it is possible to obtain, after a first long term configuration, a short term balancing, using an appropriate sequencing, for a given production mix and characteristics of the assembly system. The proposed procedure is applied to un-paced assembly lines and validated through simulation and industrial applications.     

Supply chain optimisation with assembly line balancing

Supply chain management operates at three levels, strategic, tactical and operational. While the strategic approach generally pertains to the optimisation of network resources such as designing networks, location and determination of the number of facilities, etc., tactical decisions deal with the mid-term, including production levels at all plants, assembly policy, inventory levels and lot sizes, and operational decisions are related to how to make the tactical decisions happen in the short term, such as production planning and scheduling. This paper mainly discusses and explores how to realise the optimisation of strategic and tactical decisions together in the supply chain. Thus, a supply chain network (SCN) design problem is considered as a strategic decision and the assembly line balancing problem is handled as a tactical decision. The aim of this study is to optimise and design the SCN, including manufacturers, assemblers and customers, that minimises the transportation costs for determined periods while balancing the assembly lines in assemblers, which minimises the total fixed costs of stations, simultaneously. A nonlinear mixed-integer model is developed to minimise the total costs and the number of assembly stations while minimising the total fixed costs. For illustrative purposes, a numerical example is given, the results and the scenarios that are obtained under various conditions are discussed, and a sensitivity analysis is performed based on performance measures of the system, such as total cost, number of stations, cycle times and distribution amounts.     

Using simulated annealing to solve a multiobjective assembly line balancing problem with parallel workstations

This research presents a Simulated Annealing based technique to address the assembly line balancing problem for multiple objective problems when paralleling of workstations is permitted. The Simulated Annealing methodology is used for 23 line balancing strategies across seven problems. The resulting performance of each solution was studied through a simulation experiment. Many of the problems consisted of multiple products, which were sequenced in a mixed model fashion, task times were assumed to be stochastic, and parallel workstations were permitted. Two primary performance objectives were of most interest: total cost (labour and equipment) per part, and the degree to which the desired cycle time was achieved. Other traditional line balancing and production performance measures were also collected. This paper demonstrates how Simulated Annealing can be used to obtain line balancing solutions when one or more objectives are important. The experimental results showed that Simulated Annealing approaches yielded significantly better solutions on cycle time performance but average solutions on cost performance. When cycle time performance and total unit cost are weighted equally, performance rankings showed that Simulated Annealing approaches still showed better mean performance than the other approaches.     

A novel integer programming formulation with logic cuts for the U-shaped assembly line balancing problem

U-shaped assembly lines are regarded as an efficient configuration in Just-In-Time manufacturing. Balancing the workload in these lines is an unsolved problem that attracted significant research within the past two decades. We present a novel integer programming formulation for U-shaped line balancing problems, where cycle time, the interval between two consecutive outputs, is known and the aim is to minimize the number of workstations. To enhance the efficiency of the LP relaxation of the new formulation, we present three types of logic cuts (assignable-station-cuts, task-assignment-cuts and knapsack-cuts) that exploit the inherent logic of the problem structure. The new formulation and logic cuts are tested on an extensive set of benchmark problems to provide a comparative analysis with the existing models in the literature. The results show that our novel formulation augmented by assignable-station-cuts is significantly better than the previous formulations.     

Mixed model assembly system with multiple secondary feeder lines: layout design and balancing procedure for ATO environment

The constant research for efficiency and flexibility has forced assembly systems to change from simple/single assembly lines to mixed model assembly lines, while the necessity to reduce inventory has led the transition from single to multi-line systems, where some components are assembled in secondary lines, called feeder lines, connected to the main one by a ‘pull philosophy’. A possible approach to configure such an assembly system is to balance the main line first and use the retrieved cycle time to balance each feeder line separately, which is a questionable solution, especially if operators can perform tasks on both the feeder and the main line. Moreover for its complexity the mixed model balancing problem is usually solved transforming it into a single model by creating a single ‘virtual average model’, representative of the whole production mix. The use of a virtual average model assumes that the processing times of some models are higher or lower than the cycle time, which creates overload/idle time at the stations. This approach, especially in complex multi line production systems, largely reduces the assembly line productivity and increases the buffers dimensions. This paper faces the mixed model assembly line balancing problem in the presence of multiple feeder lines, introducing an innovative integrated main-feeder lines balancing procedure in case of unpaced assembly systems. The proposed approach is compared with the classical one and validated through simulation and industrial applications.     

Assembly line balancing with parallel workstations and dead time

This paper presents a dynamic programming (DP) algorithm for solving an assembly line-balancing )ALB( problem with parallel workstations. Solutions represent a trade-off between the minimum number of stations required to achieve a balance and the cost of installing additional facilities. Both task costs and equipment costs are considered. A second feature of the algorithm is that it takes into account unproductive time during a cycle.

The advantage of the DP approach is that it readily permits the recursive relationship associated with the serial ALB problem to be modified to accommodate the cost of paralleling. Solutions are obtained with an enumeration scheme that exploits known lower bounds. Two examples, and the results from a series of industry-based test problems, are presented to highlight the computations. In general, the algorithm performs well, but runs into trouble when the order strength of the underlying precedence graph is close to one or zero.     

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.     

Analysis of the type II robotic mixed-model assembly line balancing problem

In recent years, there has been an increasing trend towards using robots in production systems. Robots are used in different areas such as packaging, transportation, loading/unloading and especially assembly lines. One important step in taking advantage of robots on the assembly line is considering them while balancing the line. On the other hand, market conditions have increased the importance of mixed-model assembly lines. Therefore, in this article, the robotic mixed-model assembly line balancing problem is studied. The aim of this study is to develop a new efficient heuristic algorithm based on beam search in order to minimize the sum of cycle times over all models. In addition, mathematical models of the problem are presented for comparison. The proposed heuristic is tested on benchmark problems and compared with the optimal solutions. The results show that the algorithm is very competitive and is a promising tool for further research.     

Performance evaluation of ant colony optimization-based solution strategies on the mixed-model assembly line balancing problem

The aim of this article is to compare the performances of iterative ant colony optimization (ACO)-based solution strategies on a mixed-model assembly line balancing problem of type II (MMALBP-II) by addressing some particular features of real-world assembly line balancing problems such as parallel workstations and zoning constraints. To solve the problem, where the objective is to minimize the cycle time (i.e. maximize the production rate) for a predefined number of workstations in an existing assembly line, two ACO-based approaches which differ in the mission assigned to artificial ants are used. Furthermore, each ACO-based approach is conducted with two different pheromone release strategies: global and local pheromone updating rules. The four ACO-based approaches are used for solving 20 representative MMALBP-II to compare their performance in terms of computational time and solution quality. Detailed comparison results are presented.     

MIP approach to balancing transfer lines with blocks of parallel operations

A novel line balancing problem is considered. It differs from assembly line balancing problems in that the operations of each workstation are partitioned into blocks of simultaneously executed (parallel) operations. The blocks of each workstation are executed sequentially. For the line design stage considered in this paper, the compatibility (inclusion and exclusion) constraints for grouping operations into blocks and workstations as well as precedence constraints are known. The goal is to minimize a weighted sum of the number of workstations and the number of blocks while achieving a desired cycle time and satisfying all the constraints. The developed exact and heuristic methods are based on a mixed-integer programming approach. Experimental results are reported.     

Design of flexible assembly line to minimize equipment cost

In this paper we develop an optimal and a heuristic algorithm for the problem of designing a flexible assembly line when several equipment alternatives are available. The design problem addresses the questions of selecting the equipment and assigning tasks to workstations, when precedence constraints exist among tasks. The objective is to minimize total equipment costs, given a predetermined cycle time (derived from the required production rate). We develop an exact branch and bound algorithm which is capable of solving practical problems of moderate size. The algorithm's efficiency is enhanced due to the development of good lower bounds, as well as the use of some dominance rules to reduce the size of the branch and bound tree. We also suggest the use of a branch-and-bound-based heuristic procedure for large problems, and analyze the design and performance of this heuristic.     

Assembly line sequencing for model mix

This paper describes a model sequencing algorithm for model-mix assembly lines. A new formulation of the sequencing problem is proposed, the objective function of which is to minimize the overall assembly line-length for no operator interference. Lower bounds for the overall line-length are developed.

Two types of work station interfaces are considered; ‘closed’, where boundaries cannot be violated, and ‘open’ where defined boundaries do not exist—adjacent operators being allowed to enter each others apparent work areas without causing any interference.

A complete factorial experiment was made on five factors to determine their influence on the overall assembly line length. These are, the number of models, the model cycle time deviation, the production demand deviation for each model, the operator time deviation, and the number of stations in the assembly line. The main conclusions of this experiment are discussed and recommendations made for the selection of parameters used in the design of model-mix assembly lines.

Also discussed is an approach for accommodating small changes in production demand for existing assembly lines.