An MILP model and a hybrid evolutionary algorithm for integrated operation optimisation of multi-head surface mounting machines in PCB assembly

This paper focuses on an operation optimisation problem for a class of multi-head surface mounting machines in printed circuit board assembly lines. The problem involves five interrelated sub-problems: assigning nozzle types as well as components to heads, assigning feeders to slots and determining component pickup and placement sequences. According to the depth of making decisions, the sub-problems are first classified into two layers. Based on the classification, a two-stage mixed-integer linear programming (MILP) is developed to describe it and a two-stage problem-solving frame with a hybrid evolutionary algorithm (HEA) is proposed. In the first stage, a constructive heuristic is developed to determine the set of nozzle types assigned to each head and the total number of assembly cycles; in the second stage, constructive heuristics, an evolutionary algorithm with two evolutionary operators and a tabu search (TS) with multiple neighbourhoods are combined to solve all the sub-problems simultaneously, where the results obtained in the first stage are taken as constraints. Computational experiments show that the HEA can obtain good near-optimal solutions for small size instances when compared with an optimal solver, Cplex, and can provide better results when compared with a TS and an EA for actual instances.     

PCB assembly scheduling for collect-and-place machines using genetic algorithms

In printed circuit board (PCB) assembly, collect-and-place machines, which use a revolver-type placement head to mount electronic components onto the board, represent one of the most popular types of assembly machinery. The assignment of feeders to slots in the component magazine and the sequencing of the placement operations are the main optimisation problems for scheduling the operations of an automated placement machine. In this paper, we present different genetic algorithms (GAs) for simultaneously solving these highly interrelated problems for collect-and-place machines in PCB assembly. First we consider single-gantry machines as the basic type of machinery. In the conventional GA approach all placement operations and the feeder-slot assignment are represented by a single chromosome. In order to increase the efficiency of the genetic operators, we present a novel GA approach, which integrates a clustering algorithm for generating sub-sections of the PCB and grouping the corresponding placement operations. It is shown that the proposed GAs can be extended to schedule dual-gantry placement machines, which are equipped with two independent placement heads and two dedicated component magazines. Hence, component feeders have to be allocated between the two magazines. To solve this allocation problem, two different heuristic strategies are proposed. Finally, detailed numerical experiments are carried out to evaluate the performances of the proposed GAs.     

Mathematical model and metaheuristics for simultaneous balancing and sequencing of a robotic mixed-model assembly line

This article presents the first method to simultaneously balance and sequence robotic mixed-model assembly lines (RMALB/S), which involves three sub-problems: task assignment, model sequencing and robot allocation. A new mixed-integer programming model is developed to minimize makespan and, using CPLEX solver, small-size problems are solved for optimality. Two metaheuristics, the restarted simulated annealing algorithm and co-evolutionary algorithm, are developed and improved to address this NP-hard problem. The restarted simulated annealing method replaces the current temperature with a new temperature to restart the search process. The co-evolutionary method uses a restart mechanism to generate a new population by modifying several vectors simultaneously. The proposed algorithms are tested on a set of benchmark problems and compared with five other high-performing metaheuristics. The proposed algorithms outperform their original editions and the benchmarked methods. The proposed algorithms are able to solve the balancing and sequencing problem of a robotic mixed-model assembly line effectively and efficiently.     

An MILP model and clustering heuristics for LED assembly optimisation on high-speed hybrid pick-and-place machines

This paper deals with a scheduling optimisation problem arising in printed circuit board (PCB) assembly. In one class of PCB assembly, light-emitting diodes are to be assembled into the placement locations on PCBs by a machine with multiple pick-and-place heads. The scheduling optimisation problem is to determine the assembly sequence of placement locations and the assignment of pick-and-place heads for locations so as to minimise the assembly time. We formulate it as a mixed integer linear programming model. To solve the problem efficiently, we classify the PCBs into two types. For the first type of PCBs, on which the locations are linearly arranged, a constructive heuristic is proposed based on the analysis of the best next location after a location is assembled. For the second type of PCBs, on which the locations are circularly arranged, a heuristic based on clustering strategy and path relinking method is proposed. Computational experiments show that the solutions obtained by the two heuristics make 2.32 and 6.82% improvements averagely for the PCBs with linearly and circularly arranged locations, respectively, as compared to the solutions used in real production, and they are also better than those obtained by a hybrid genetic algorithm.     

A GA-based solution approach for balancing printed circuit board assembly lines

Printed circuit board (PCB) assembly lines consist of a number of different machines for mounting electronic components onto PCBs. While high-speed placement machines are employed to assemble standard components, so-called fine-pitch placement machines are used to mount complex electronic components with high precision and by use of specific nozzles. In this paper, we investigate a typical mass production environment where a single type of PCB is assembled in a line comprising high-speed as well as high-precision placement machines. The PCB assembly line balancing problem consists of assigning component feeders, each holding a specific electronic component type, and the corresponding placement operations to machines in the line so as to minimize the assembly cycle time. To solve this problem, a two-stage solution procedure based on genetic algorithm (GA) is proposed. In the first stage, component feeders are assigned to the placement machines with the objective of balancing the workload within the assembly line. A number of candidate solutions are then transmitted to the second stage, where specific machine optimization algorithms are applied to determine the feeder-slot assignment in the component magazine of the machines and the placement sequence of the various components. As a result, fine-tuned placement operation times are achieved which reflect the individual operation mode and the actual component setup of the placement machines. Finally, from the candidate solutions the one which minimizes the actual PCB assembly time is selected.     

A coordinated algorithm for integrated production scheduling and vehicle routing problem

In this paper, the integrated production scheduling and vehicle routing problem is considered for a Make-to-Order manufacturer, who has a single machine for production and limited vehicles with capacity constraints for transportation. The objective is to determine production scheduling and vehicle routing, which are two interacted decisions, to minimise the maximum order delivery time. A property on optimal production sequence is proposed first, based on which backward and forward batching methods are developed and are embedded into a proposed genetic algorithm. The proposed genetic algorithm is capable of providing high-quality solutions by determining the two decisions simultaneously. For comparison purpose, a two-stage algorithm is developed, which decomposes the overall problem into two successively solved sub-problems. The experiments show that the proposed genetic algorithm can provide higher quality solutions than the proposed two-stage algorithm and two published algorithms studying related problems.     

缓冲区容量约束下发动机混流装配线排序研究

为解决缓冲区容量约束下发动机混流装配排序问题,以关键部件消耗均匀化和最大完工时间最小化为目标,建立了优化数学模型,设计了一种多目标遗传算法,采用了混合交叉算子和启发式变异方法,并设计了基于帕累托分级和共享函数的适应度函数,将多目标遗传算法和多目标模拟退火算法的优化结果进行了比较。研究结果表明,多目标遗传算法在满意度和计算效率方面均优于多目标模拟退火算法,是一种有效的混流装配线排序问题求解算法。     

Meta-heuristics for the distributed two-stage assembly scheduling problem with bi-criteria of makespan and mean completion time

This paper focuses on the distributed two-stage assembly flowshop scheduling problem for minimising a weighted sum of makespan and mean completion time. This problem involves two inter-dependent decision sub-problems: (1) how to allocate jobs among factories and (2) how to schedule the assigned jobs at each factory. A mathematical model is formulated for solving the small-sized instances of the problem. Since the NP-hardness of the problem, we also proposed a variable neighbourhood search (VNS) algorithm and a hybrid genetic algorithm combined with reduced variable neighbourhood search (GA-RVNS) to solve the distributed two-stage assembly flowshop scheduling problems and approximately optimise makespan and mean completion time simultaneously. Computational experiments have been conducted to compare the performances of the model and proposed algorithms. For a set of small-sized instances, both the model and the proposed algorithms are effective. The proposed algorithms are further evaluated on a set of large-sized instances. The results statistically show that both GA-RVNS and VNS obtain much better performances than the GA without RVNS-based local search step (GA-NOV). For the instances with small numbers of jobs, VNS achieves better performances than GA-RVNS. However, for the instances with large numbers of jobs, GA-RVNS yields better performances than the VNS. It is also shown that the overall performances of VNS are very close to GA-RVNS with different numbers of factories, weights given to makespan and numbers of machines at the first stage.     

Lagrangean relaxation approach to joint optimization for production planning and scheduling of synchronous assembly lines

This paper focuses on simultaneous optimisation of production planning and scheduling problem over a time period for synchronous assembly lines. Differing from traditional top-down approaches, a mixed integer programming model which jointly considers production planning and detailed scheduling constraints is formulated, and a Lagrangian relaxation method is developed for the proposed model, whereby the integrated problem is decomposed into planning, batch sequencing, tardiness and earliness sub-problems. The scheduling sub-problem is modelled as a time-dependent travelling salesman problem, which is solved using a dynasearch algorithm. A proposition of Lagrangian multipliers is established to accelerate the convergence speed of the proposed algorithm. The average direction strategy is employed to solve the Lagrangian dual problem. Test results demonstrate that the proposed model and algorithm are effective and efficient.     

Non-dominated ranked genetic algorithm for a multi-objective mixed-model assembly line sequencing problem

The increasing market demand for product variety forces manufacturers to design mixed-model assembly lines (MMAL) on which a variety of product models similar to product characteristics are assembled. This paper presents a method combining the new ranked based roulette wheel selection algorithm with Pareto-based population ranking algorithm, named non-dominated ranking genetic algorithm (NRGA) to a just-in-time (JIT) sequencing problem when two objectives are considered simultaneously. The two objectives are minimisation the number of setups and variation of production rates. This type of problem is NP-hard. Various operators and parameters of the proposed algorithm are reviewed to calibrate the algorithm by means of the Taguchi method. The solutions obtained via NRGA are compared against solutions obtained via total enumeration (TE) scheme in small problems and also against four other search heuristics in small, medium and large problems. Experimental results show that the proposed algorithm is competitive with these other algorithms in terms of quality and diversity of solutions.     

Advanced scatter search approach and its application in a sequencing problem of mixed-model assembly lines in a case company

Mixed-model assembly line sequencing is significant in reducing the production time and overall cost of production. To improve production efficiency, a mathematical model aiming simultaneously to minimize overtime, idle time and total set-up costs is developed. To obtain high-quality and stable solutions, an advanced scatter search approach is proposed. In the proposed algorithm, a new diversification generation method based on a genetic algorithm is presented to generate a set of potentially diverse and high-quality initial solutions. Many methods, including reference set update, subset generation, solution combination and improvement methods, are designed to maintain the diversification of populations and to obtain high-quality ideal solutions. The proposed model and algorithm are applied and validated in a case company. The results indicate that the proposed advanced scatter search approach is significant for mixed-model assembly line sequencing in this company.     

A genetic algorithm for solving the economic lot scheduling problem in flow shops

In this study, we propose a hybrid genetic algorithm (HGA) to solve the economic lot scheduling problem in flow shops. The proposed HGA utilizes a so-called Proc PLM heuristic that tests feasibility for the candidate solutions obtained in the evolutionary process of genetic algorithm. When a candidate solution is infeasible, we propose to use a binary search heuristic to ‘fix’ the candidate solution so as to obtain a feasible solution with the minimal objective value. To evaluate the performance of the proposed HGA, we randomly generate a total of 2100 instances from seven levels of utilization rate ranged from 0.45 to 0.80. We solve each of those 2100 instances by the proposed HGA and the other solution approaches in the literature. Our experiments show that the proposed HGA outperforms traditional methods for solving the economic lot scheduling problem in flow shops.     

Two-dimensional phase unwrapping using a hybrid genetic algorithm

A novel hybrid genetic algorithm (HGA) is proposed to solve the branch-cut phase unwrapping problem. It employs both local and global search methods. The local search is implemented by using the nearest-neighbor method, whereas the global search is performed by using the genetic algorithm. The branch-cut phase unwrapping problem [a nondeterministic polynomial (NP-hard) problem] is implemented in a similar way to the traveling-salesman problem, a very-well-known combinational optimization problem with profound research and applications. The performance of the proposed algorithm was tested on both simulated and real wrapped phase maps. The HGA is found to be robust and fast compared with three well-known branch-cut phase unwrapping algorithms.     

Ant colony optimisation algorithms for two-stage permutation flow shop with batch processing machines and nonidentical job sizes

This paper focuses on minimising the maximum completion time for the two-stage permutation flow shop scheduling problem with batch processing machines and nonidentical job sizes by considering blocking, arbitrary release times, and fixed setup and cleaning times. Two hybrid ant colony optimisation algorithms, one based on job sequencing (JHACO) and the other based on batch sequencing (BHACO), are proposed to solve this problem. First, max-min pheromone restriction rules and a local optimisation rule are embedded into JHACO and BHACO, respectively, to avoid trapping in local optima. Then, an effective lower bound is estimated to evaluate the performances of the different algorithms. Finally, the Taguchi method is adopted to investigate and optimise the parameters for JHACO and BHACO. The performances of the proposed algorithms are compared with that of CPLEX on small-scale instances and those of a hybrid genetic algorithm (HGA) and a hybrid discrete differential evolution (HDDE) algorithm on full-scale instances. The computational results demonstrate that BHACO outperforms JHACO, HDDE and HGA in terms of solution quality. Besides, JHACO strikes a balance between solution quality and run time.     

A modified particle swarm optimisation algorithm to solve the part feeding problem at assembly lines

The Assembly Line Part Feeding Problem (ALPFP) is a complex combinatorial optimisation problem concerned with the delivery of the required parts to the assembly workstations in the right quantities at the right time. Solving the ALPFP includes simultaneously solving two sub-problems, namely tour scheduling and tow-train loading. In this article, we first define the problem and formulate it as a multi-objective mixed-integer linear programming model. Then, we carry out a complexity analysis, proving the ALPFP to be NP-complete. A modified particle swarm optimisation (MPSO) algorithm incorporating mutation as part of the position updating scheme is subsequently proposed. The MPSO is capable of finding very good solutions with small time requirements. Computational results are reported, demonstrating the efficiency and effectiveness of the proposed MPSO.     

A method combining rules with genetic algorithm for minimizing makespan on a batch processing machine with preventive maintenance

This paper considers the problem of minimising makespan on a single batch processing machine with flexible periodic preventive maintenance. This problem combines two sub-problems, scheduling on a batch processing machine with jobs’ release dates considered and arranging the preventive maintenance activities on a batch processing machine. The preventive maintenance activities are flexible but the maximum continuous working time of the machine, which is allowed, is determined. A mathematical model for integrating flexible periodic preventive maintenance into batch processing machine problem is proposed, in which the grouping of jobs with incompatible job families, the starting time of batches and the preventive maintenance activities are optimised simultaneously. A method combining rules with the genetic algorithm is proposed to solve this model, in which a batching rule is proposed to group jobs with incompatible job families into batches and a modified genetic algorithm is proposed to schedule batches and arrange preventive maintenance activities. The computational results indicate the method is effective under practical problem sizes. In addition, the influences of jobs’ parameters on the performance of the method are analyzed, such as the number of jobs, the number of job families, jobs’ processing time and jobs’ release time.     

Minimising work overload in mixed-model assembly lines with different types of operators: a case study from the truck industry

This paper considers the problem of sequencing mixed-model assembly lines (MMALs). Our goal is to determine the sequence of products to minimise work overload. This problem is known as the MMAL sequencing problem with work overload minimisation: we explicitly use task operation times to find the product sequence. This paper is based on an industrial case study of a truck assembly line. In this industrial context, as a reaction to work overloads, operators at the workstations finish their tasks before the product reaches the next workstation, but at the expense of fatigue. Furthermore, there are different types of operators, each with different task responsibilities. The originality of this work is to model this new way of reacting against work overloads, to integrate three operator types in the sequencing model and to apply the developed methods in a real industrial context. To solve this problem, we propose three meta-heuristic procedures: genetic algorithm, simulated annealing and a combination of these two meta-heuristics. All the methods proposed are tested on industrial data and compared to the solutions obtained using a mixed-integer linear programme. The results show that the proposed methods considerably improve the results of the current procedure used in the case study.     

A decomposition-based approach to flexible flow shop scheduling under machine breakdown

Manufacturing systems in real-world production are generally dynamic and often subject to a wide range of uncertainties. Recently, research on production scheduling under uncertainty has attracted substantial attention. Although some methods have been developed to address this problem, scheduling under uncertainty remains inherently difficult to solve by any single approach. This article considers makespan optimisation of a flexible flow shop (FFS) scheduling problem under machine breakdown. It proposes a novel decomposition-based approach to decompose an FFS scheduling problem into several cluster scheduling problems which can be solved more easily by different approaches. A neighbouring K-means clustering algorithm is developed to first group the machines of an FFS into an appropriate number of machine clusters, based on a proposed machine allocation algorithm and weighted cluster validity indices. Two optimal back propagation networks, corresponding to the scenarios of simultaneous and non-simultaneous job arrivals, are then selectively adopted to assign either the shortest processing time (SPT) or the genetic algorithm (GA) to each machine cluster to solve cluster scheduling problems. If two neighbouring machine clusters are allocated with the same approach, they are subsequently merged. After machine grouping and approach assignment, an overall schedule is generated by integrating the solutions to the sub-problems. Computation results reveal that the proposed approach is superior to SPT and GA alone for FFS scheduling under machine breakdown.     

A hybrid genetic algorithm for the single row layout problem

The arrangement of machines or departments along a straight line is known as single row layout and it is a widely employed configuration in flexible manufacturing systems. In this paper, a hybrid genetic algorithm (HGA) is proposed to solve the single row layout design problem with unequal sized machines and unequal clearances. The algorithm is developed by hybridisation of a genetic algorithm with a local search operator. The proposed HGA is tested on 51 well known data sets from the literature with equal and unequal clearances, and the results are compared with the best known solutions. Finally, algorithm's effectiveness in reaching previously known best solutions is revealed and improvements up to 7% in problems with unequal clearance are obtained.     

Productivity improvement through a sequencing generalised assignment in an assembly line system

This paper considers the assignment of heterogeneous workers to workstations of an assembly line in order to minimise the total production time. As the structure of the system implies that each of the workstations needs at least one worker, thus the problem can be considered as a generalised assignment problem (GAP). The objective is to perform an efficient human resource planning for a specified horizon consisting of several periods. Hence, we present an extension of the generalised assignment problem, consisting of a set of GAPs (one for each planning period) in which each GAP depends on the previous ones. A mixed integer mathematical model is presented for this sequencing assignment problem. The model is solved by an exact algorithm using Gurobi solver. It is proved that the problem is NP-hard and solving the medium and large size instances is not possible by the exact algorithms. Hence, two matheuristic approaches based on the disaggregated formulation of GAP are proposed. The first approach solves the problem through two sub-problems as the transportation formulation and assignment formulation. The second approach solves the problem by decomposition of the problem into several classical GAPs. The approaches are examined by a total of 27 instances. The results illustrate the efficiency of the proposed algorithms in the computational time and accuracy of the solutions.