A priority rule-based constructive heuristic and an improvement method for balancing assembly lines with parallel multi-manned workstations

Assembly lines of big-size products such as buses, trucks and helicopters are very different from the lines studied in the literature. These products’ manufacturing processes have a lot of tasks most of which have long task times. Since traditional assembly line models including only one worker in each station (i.e. simple assembly lines) or at most two workers (two-sided assembly lines) may not be suitable for manufacturing these type of products, they need much larger shop floor for a number of stations and long product flow times. In this study, an assembly line balancing problem (ALBP) with parallel multi-manned stations is considered. Following the problem definition, a mixed integer programming formulation is developed. A detailed study of priority rules for simple ALBPs is also presented, and a new efficient constructive heuristic algorithm based on priority rules is proposed. In order to improve solutions found by the constructive heuristic, a genetic algorithm-based solution procedure is also presented. Benchmark instances in the literature are solved by using the proposed mathematical programming formulation. It has been seen that only some of the small-size instances can be solved optimally by this way. So the efficiency of the proposed heuristic method is verified in small-size instances whose optimal solutions are found. For medium- and big-size instances, heuristics’ results and CPU times are demonstrated. A comparative evaluation with a branch and bound algorithm that can be found in the literature is also carried out, and results are presented.     

Bi criteria flexible assembly line design problem with equipment decisions

In this paper, we address the assembly line balancing and design problem of assigning tasks and equipment to work stations where there are several equipment alternatives for each task. We consider minimizing the total equipment cost and the number of work stations criteria. We aim to generate efficient solutions with respect to these criteria and propose a branch and bound algorithm whose efficiency is enhanced with powerful reduction and bounding mechanisms. We find that our algorithm is capable of solving problem instances with up to 25 tasks and five pieces of equipment.     

Balancing manual mixed-model assembly lines using overtime work in a demand variation environment

This study deals with the balancing problem of a manual mixed-model assembly line, where the production volume or the product mix changes from shift to shift during the planning horizon. The unstable demand can be characterised by several representative scenarios, and the line uses overtime work to meet the demand variation. The balancing problem concerns how to assign assembly tasks to stations and determine the amount of overtime in each possible demand scenario. The objective is to satisfy the demand in each possible scenario with the minimum labour costs paid for both normal shifts and overtime work. A lower bound on the labour costs is proposed, and a heuristic algorithm is developed to quickly find a feasible solution. A branch, bound and remember (BB&;R) algorithm is then proposed to find better solutions. These solution methods are tested on 765 instances. The BB&;R algorithm obtains optimal solutions for 510 instances and gives high-quality solutions for the remaining 255 instances within 60?s. The experimental results show that the use of overtime work and adjustable cycle times significantly reduces the labour costs, especially when the demand or task processing time variations are large.     

Increasing production rate in U-type assembly lines with sequence-dependent set-up times

U-shaped assembly lines are commonly used in just-in-time production systems as they have some advantages over straight lines. Although maximizing production rates on these lines by assigning tasks to stations is common practice in industrial environments, studies on the stated assembly line balancing problem are limited. This article deals with maximizing the production rate on U-shaped assembly lines under sequence-dependent set-up times. Sequence-dependent set-up times mean that after a task is performed, a set-up time, the duration of which depends on adjacent tasks, is required to start the next task operation. These set-ups are considered by dividing them into two groups, named forward and backward set-ups, to make the problem more practical. Two heuristics based on simulated annealing and genetic algorithms are improved beside the mathematical model. Experimental results show that solving the stated problem using the mathematical model is nearly impossible, while heuristics may obtain solutions that have acceptable deviations from the lower bounds.     

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.     

Evaluation of the influence of dominance rules for the assembly line design problem under consideration of product design alternatives

The current competitive situation increases the importance of realistically estimating product costs during the early phases of product and assembly line planning projects. In this article, several multi-objective algorithms using difference dominance rules are proposed to solve the problem associated with the selection of the most effective combination of product and assembly lines. The list of developed algorithms includes variants of ant colony algorithms, evolutionary algorithms and imperialist competitive algorithms. The performance of each algorithm and dominance rule is analysed by five multi-objective quality indicators and fifty problem instances. The algorithms and dominance rules are ranked using a non-parametric statistical test.     

An improved approach for determination of index positions on CNC magazines with cutting tool duplications by integrating shortest path algorithm

Optimisation of automatic tool changer (ATC) indexing problem, where cutting tools are allocated to the stations on a turret magazine of a CNC machine, is one of the challenging problems in machining. The aim of the problem is to minimise the total indexing time of ATC. This problem becomes even more challenging if duplication of cutting tools is allowed and a bidirectional ATC is used. The problem has a unique feature which has not been stressed yet by other researchers, that is, although ATC indexing (master problem) is the main optimisation problem, objective function evaluation of this problem is a standalone optimisation problem (sub problem) indeed. Although an approximation algorithm does not guarantee optimality for the master problem, the subproblem must be solved optimally; otherwise, deficiencies arising from ill-defined objective function might be encountered. Considering this interesting future, a novel methodology, which employs a shortest path algorithm, is developed. Thus, the subproblem of this complicated problem can be optimally solved. Moreover, two metaheuristics, based on threshold accepting and descent first improvement greedy methodologies, are proposed for generating efficient solutions. Finally, several benchmarking instances are generated and solved to test the proposed algorithms.     

A weighted approach for assembly line design with station paralleling and equipment selection

This paper studies the problem of assembly line design, focusing on station paralleling and equipment selection. Two problem formulations, minimizing the number of stations, and minimizing the total cost, are discussed. The latter formulation is demonstrated by several examples, for different assembly system conditions: labor intensive or equipment intensive, and with task times that may exceed the required cycle time. It is shown that the problem of assembly system design with parallel stations can be treated as a special case of the problem of equipment selection for an assembly line. A branch and bound optimal algorithm developed for the equipment selection problem is adapted to solve the parallel station problem. Experiments are designed to investigate and demonstrate the influence of system parameters, such as assembly sequence flexibility and cycle time, on the balancing improvement due to station paralleling. An ILP formulation is developed for the combined problem of station paralleling with equipment selection, and an optimal solution of an example problem is presented.     

Balancing of U-type assembly systems using simulated annealing

The paper presents a new simulated annealing (SA)-based algorithm for the assembly line-balancing problem with a U-type configuration. The proposed algorithm employs an intelligent mechanism to search a large solution space. U-type assembly systems are becoming increasingly popular in today's modern production environments since they are more general than the traditional assembly systems. In these systems, tasks are to be allocated into stations by moving forward and backward through the precedence diagram in contrast to a typical forward move in the traditional assembly systems. The performance of the algorithm is measured by solving a large number of benchmark problems available in the literature. The results of the computational experiments indicate that the proposed SA-based algorithm performs quite effectively. It also yields the optimal solution for most problem instances. Future research directions and a comprehensive bibliography are also provided here.     

Simultaneous versus sequential loading and scheduling of flexible assembly systems

A monolithic and a hierarchical approach is presented for loading and scheduling in a general flexible assembly system and a flexible assembly line. The system is made up of a set of assembly stations of various types each with limited working space and is capable of simultaneously producing a mix of product types. The objective is to determine an assignment of assembly tasks to stations and an assembly schedule for all products so as to complete the products in a minimum time. In the monolithic approach loading and scheduling decisions are made simultaneously. In the hierarchical approach, however, first the station workloads are balanced by solving the loading problem, and then detailed assembly schedule is determined for prefixed task assignments and assembly routes by solving a standard job-shop problem. Mixed integer programming formulations are presented for simultaneous and for sequential loading and scheduling. Loading and scheduling with alternative or with single task assignments are considered. Numerical examples are included to illustrate and compare the two approaches proposed.     

基于"边折叠"的可逆累进网格生成算法的研究

在分析已有累进网格生成算法的基础上,提出一种基于“边折叠”网格化简方法的累进网格生成算法,构造了累进网格的表示新方法。算法消除了累进网格技术中的二义性,具有支持多种网格类型、保持相邻层次细节模型间的平滑过渡等特点。实验表明,算法具有有效性和可靠性。     

Scheduling duplicate serial stations in transfer lines

To support the production rate, some transfer line stations with long cycle times must be duplicated. A job is processed in only one of the duplicate stations. If laid out in parallel, this duplication essentially doubles the capacity, but, for practical reasons, these duplicate stations are often laid out in a series. The serial layout has a capacity less than the parallel's, and also raises some operational questions. We enunciated and analysed this actual problem of operating duplicate stations in series. We simulated an existing closed-loop transfer-line with duplicate stations in series using the actual failure and repair characteristics of the automated stations, and compared a new heuristic with three simple policies.     

Sequencing mixed-model assembly lines operating with a heterogeneous workforce

We study the problem of sequencing mixed-model assembly lines operating with a heterogeneous workforce. The practical motivation for this study comes from the context of managing assembly lines in sheltered work centres for the disabled. We propose a general framework in which task execution times are both worker and model dependent. Within this framework, the problem is defined and mathematical mixed-integer models and heuristic procedures are proposed. These include a set of fast constructive heuristics, two local search procedures based on approximate measures using either a solution upper bound or the solution of a linear program and a GRASP metaheuristic. Computational tests with instances adapted from commonly used literature databases are used to validate the proposed approaches. These tests give insight on the quality of the different techniques, which prove to be very efficient both in terms of computational effort and solution quality when compared to other strategies such as a random sampling or the solution of the MIP models using a commercial solver.     

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.     

Assembly line balancing: general resource-constrained case

The problem of designing and balancing assembly lines has been widely studied in the literature. A recently introduced issue is the efficient use of constrained resources with specific assumptions, in which a task needs a resource type (A) or one of two resources (A ∨ B). This paper presents a more general resource-constrained case, in which each task needs resources that may be simple or multiple, alternative and/or concurrent: for instance, (3A), (A ∧ 4B ∧ 3C), (3A ∨ 2B ∨ C), (A ∧ B) ∨ (2C ∧ D) or (A ∨ B) ∧ (2C ∨ D). We also introduce an upper bound on the number of available resources. Finally, we present a computational experiment using the mathematical models that we develop, showing the instances that can be efficiently solved.     

Mathematical models and a hunting search algorithm for the no-wait flowshop scheduling with parallel machines

Majority of researches in no-wait flowshop scheduling assume that there is only one machine at each stage. But, factories commonly duplicate machines in parallel for each operation. In this case, they balance the speed of the stages, increase the throughput of the shop floor and reduce the impact of bottleneck stages. Despite their importance, there is no paper to study the general no-wait flowshop with parallel machines. This paper studies this problem where the objective is to minimise makespan. Since there is no mathematical model for the problem, we first mathematically formulate it in form of two mixed integer linear programming models. By the models, the small instances are optimally solved. We then propose a novel hunting search metaheuristic algorithm (HSA) to solve large instances of the problem. HSA is derived based on a model of group hunting of animals when searching for food. A set of experimental instances are carried out to evaluate the algorithm. The algorithm is carefully evaluated for its performance against an available algorithm by means of statistical tools. The related results show that the proposed HSA provides sound performance comparing with other algorithms.     

A two-phase variable neighbourhood search algorithm for assembly line worker assignment and balancing problem type-II: an industrial case study

The assembly line worker assignment and balancing problem type-II (ALWABP-2) occurs when workers and tasks (where task times depend on workers’ skills) are to be simultaneously assigned to a fixed number of workstations with the goal of minimising the cycle time. In this study, a two-phase variable neighbourhood search (VNS) algorithm is proposed to solve the ALWABP-2 due to the NP-hard nature of this problem. In the first phase of the algorithm, a VNS approach is applied to assign tasks to workstations with the aim of minimising the cycle time while in the second phase, a variable neighbourhood descent method is applied to assign workers to workstations. The performance of the proposed algorithm is tested on well-known benchmark instances. In addition, the proposed algorithm has been used to solve a real case study from a consumer electronics company that manufactures LCD TVs. The results show that the algorithm is superior to the methods reported in the literature in terms of its higher efficiency and robustness. Furthermore, the algorithm is easy to implement and significantly improves the performance of the final assembly line for the investigated LCD TV real case study.     

Formulations and solution algorithms for dynamic assembly routing problem

We study a dynamic version of the assembly routing problem. The assembly lot sizing section deals with decisions concerning the production phase, whereas the routing section organises the collection of raw materials necessary for the production. Traditionally, these two problems are treated separately, and more specifically, in a hierarchical way. We propose three linear programming models: a non-vehicle index model, a two-commodity flow formulation and a logic-based benders decomposition. We develop aggregated rounded capacity constraints for non-vehicle index model and separated them dynamically during the Branch & Cut procedure. Logic-based benders decomposition algorithm solves the Dynamic Assembly Routing Problem iteratively and obtains a feasible solution at each iteration. The numerical tests show that, the two first models are particularly effective at finding the optimal solutions in a reasonable amount of time on instances with up to 50 components and 3 periods.     

One- and two-sided assembly line balancing problems with real-world constraints

In this study, we consider balancing problems of one- and two-sided assembly lines with real-world constraints like task or machine incompatibilities. First, we study the one-sided assembly line balancing problem (ALBP) with a limited number of machine types per workstation. Using a genetic algorithm (GA), we find optimal results for real-world instances. A set of larger test cases is used to compare two well-established solution approaches, namely GA and tabu search (TS). Additionally, we apply a specific differential evolution algorithm (DE), which has recently been proposed for the considered ALBP. Our computational results show that DE is clearly dominated by GA. Furthermore, we show that GA outperforms TS in terms of computational time, if capacity constraints are tight. Given the algorithm’s computational performance as well as the fact that it can easily be adapted to additional constraints, we then use it to solve two-sided ALBP. Three types of constraints and two different objectives are considered. We outperform all previously published methods in terms of solution quality and computational time. Finally, we are the first to provide feasible test instances as well as benchmark results for fully constrained two-sided ALB.     

Balancing transfer lines using Benders decomposition and ant colony optimisation techniques

In this paper, we investigate a transfer line balancing problem in order to find the line configuration that minimises the non-productive time. The problem is defined at an auto manufacturing company where the cylinder head is manufactured. Technological restrictions among design features and manufacturing operations are taken into consideration. The problem is represented by an integer programming model that assigns design features and cutting tools to machining stations, and specifies the number of machines and production sequence in each station. Three algorithms are developed to efficiently solve the problem under study. The first algorithm uses Benders decomposition approach that decomposes the proposed model into an assignment problem and a sequencing problem. The second algorithm is a hybrid algorithm that mixes Benders decomposition approach with the ant colony optimisation technique. The third algorithm solves the problem using two nested ant colonies. Using 15 different problem dimensions, we compare results of the three algorithms in a computational study. The first algorithm finds optimal solutions of small problem instances only. Second and third algorithms demonstrate optimality gaps less than 4.04 and 3.8%, respectively, when compared to the optimal results given by the first algorithm. Moreover, the second and third algorithms are very promising in solving medium and large-scale problem instances.