A modified colonial competitive algorithm for the mixed-model U-line balancing and sequencing problem

Implementation of mixed-model U-shaped assembly lines (MMUL) is emerging and thriving in modern manufacturing systems owing to adaptation to changes in market demand and application of just-in-time production principles. In this study, the line balancing and model sequencing (MS) problems in MMUL are considered simultaneously, which results in the NP-hard mixed-model U-line balancing and sequencing (MMUL/BS) problem. A colonial competitive algorithm (CCA) is developed and modified to solve the MMUL/BS problem. The modified CCA (MCCA) improves performance of original CCA by introducing a third type of country, independent country, to the population of countries maintained by CCA. Implementation details of the proposed CCA and MCCA are elaborated using an illustrative example. Performance of the proposed algorithms is tested on a set of test-bed problems and compared with that of existing algorithms such as co-evolutionary algorithm, endosymbiotic evolutionary algorithm, simulated annealing, and genetic algorithm. Computational results and comparisons show that the proposed algorithms can improve the results obtained by existing algorithms developed for MMUL/BS.     

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.     

遗传禁忌搜索算法在混流装配线排序中的应用

针对混流装配线排序问题，提出了一种混合遗传禁忌搜索算法，在每一代遗传演化之后，按一定比例随机选择部分解进行禁总搜索，以提高算法的全局搜索能力和收敛性。通过一个混流装配线排序实验，分别利用遗传算法和遗传禁忌搜索算法进行求解，结果表明遗传禁忌搜索算法具有更好的全局搜索能力和收敛性能。     

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.     

Simultaneous balancing and sequencing of mixed-model parallel two-sided assembly lines

Growing interests from customers in customised products and increasing competitions among peers necessitate companies to configure their manufacturing systems more effectively than ever before. We propose a new assembly line system configuration for companies that need intelligent solutions to satisfy customised demands on time with existing resources. A mixed-model parallel two-sided assembly line system is introduced based on the parallel two-sided assembly line system previously proposed in the literature. The mixed-model parallel two-sided assembly line balancing problem is illustrated with examples from the perspective of simultaneous balancing and sequencing. An agent-based ant colony optimisation algorithm is proposed to solve the problem. This algorithm is the first attempt in the literature to solve an assembly line balancing problem with an agent-based ant colony optimisation approach. The algorithm is illustrated with an example and its operational procedures and principles are explained and discussed.     

Simultaneous solving of balancing and sequencing problems in mixed-model assembly line systems

Recently, the mixed-model assembly line (MMAL) has been widely studied by many researchers. In fact, there are two basic problems, namely balancing and sequencing problems, which have been investigated in a lot of studies separately, but few researchers have solved both problems simultaneously. Regarding this, the best results in minimising total utility work have been gained by developing a co-evolutionary genetic algorithm (Co-GA) so far. This paper provides a mixed-integer linear programming (MILP) model to jointly solve the problems. Because of NP-hardness, an evolution strategies (ES) algorithm is presented and evaluated by the same test problems in the literature. Two main hypotheses, namely simultaneous search and feasible search, are tested in the proposed algorithm to improve the quality of solutions. To calibrate the algorithm, a Taguchi design of experiments is employed. The proposed ES is compared with the modified version of Co-GA and the MILP model results. According to numerical experiments and statistical proving, the proposed ES outperformed the modified Co-GA from two points of view: the objective function and the computational time. Additionally, the meta-heuristic algorithms are examined in terms of other well-known criteria in MMAL. Finally, the contribution of each hypothesis in accounting for this superiority is analysed.     

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.     

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.     

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

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

An urban transportation problem solved by parallel programming with hyper-heuristics

An innovative optimization strategy by means of hyper-heuristics is proposed. It consists of a parallel combination of three metaheuristics. In view of the need both to escape from local optima and to achieve high diversity, the algorithm cooperatively combines simulated annealing with genetic algorithms and ant colony optimization. A location routing problem (LRP), which aims at the design of transport networks, was adopted for the performance evaluation of the proposed algorithm. Information exchanges took place effectively between the metaheuristics and speeded up the search process. Moreover, the parallel implementation was useful since it allowed several metaheuristics to run simultaneously, thus achieving a significant reduction in the computational time. The algorithmic efficiency and effectiveness were ratified for a medium-sized city. The proposed optimization algorithm not only accelerated computations, but also helped to improve solution quality.     

A novel bi-level hierarchy towards available-to-promise in mixed-model assembly line sequencing problems

This article addresses advanced available-to-promise (AATP) in mixed-model assembly line sequencing problems. In the developed framework, customers are prioritized with respect to 11 defined criteria using the technique for order of preference by similarity to ideal solution (TOPSIS) method, and order quantities are calculated using a nonlinear mathematical program. Next, a mixed binary nonlinear mathematical program is developed to determine the optimum sequence of the optimized order quantities to minimize the total lateness. Since the proposed models are intractable, a hybrid genetic algorithm–simulated annealing method is also developed. Finally, an industrial case study is reported, the results of which validate the developed AATP framework.     

A genetic algorithm for the stochastic mixed-model U-line balancing and sequencing problem

Mixed-model assembly lines are widely used to improve the flexibility to adapt to the changes in market demand, and U-lines have become popular in recent years as an important component of just-in-time production systems. As a consequence of adaptation of just-in-time production principles into the manufacturing environment, mixed-model production is performed on U-lines. This type of a production line is called a mixed-model U-line. In mixed-model U-lines, there are two interrelated problems called line balancing and model sequencing. In real life applications, especially in manual assembly lines, the tasks may have varying execution times defined as a probability distribution. In this paper, the mixed-model U-line balancing and sequencing problem with stochastic task times is considered. For this purpose, a genetic algorithm is developed to solve the problem. To assess the effectiveness of the proposed algorithm, a computational study is conducted for both deterministic and stochastic versions of the problem.     

A bi-objective mixed-model assembly line sequencing problem considering customer satisfaction and customer buying behaviour

Customer satisfaction and focusing on the most profitable customers are the key elements to achieving a sustainable competitive advantage in the current business environment. The mixed-model assembly line (MMAL) is an efficient type of manufacturing system that has been used increasingly over recent years to satisfy diverse customer demands. Product sequencing in an MMAL system has a huge effect on the performance of the firm in meeting customer demand and, therefore, on customer satisfaction. This study aims to address a sequencing problem with respect to recency, frequency and monetary factors. A two-stage framework is developed to achieve this goal. First, the prioritized orders based on the preference ranking organization method for enrichment of evaluations (PROMETHEE) are categorized into high-priority and normal-priority orders. Then, a bi-objective mathematical programming model is developed to determine the optimum sequence of products to minimize the total cost, as well as to maximize levels of customer satisfaction. After validation of the proposed model, owing to the NP-hard nature of this problem, two multi-objective metaheuristics are applied to tackle the second stage of this study. Several test problems are presented to evaluate the performance of these algorithms. The results show the superiority of one solution approach over the other.     

Multi-objective evolutionary simulated annealing optimisation for mixed-model multi-robotic disassembly line balancing with interval processing time

This paper considers the design and balancing of mixed-model disassembly lines with multi-robotic workstations under uncertainty. Tasks of different models are performed simultaneously by the robots which have different capacities for disassembly. The robots have unidentical task times and energy consumption respectively. Task precedence diagrams are used to model the precedence relations among tasks. Considering uncertainties in disassembly process, the task processing times are assumed to be interval numbers. A mixed-integer mathematical programming model is proposed to minimise the cycle time, peak workstation energy consumption, and total energy consumption. This model has a significant managerial implication in real-life disassembly line systems. Since the studied problem is known as NP-hard, a metaheuristic approach based on an evolutionary simulated annealing algorithm is developed. Computational experiments are conducted and the results demonstrate the proposed algorithm outperforms other multi-objective algorithms on optimisation quality and computational efficiency.     

A two-stage three-machine assembly scheduling problem with deterioration effect

The two-stage assembly scheduling problem has received growing attention in the research community. Furthermore, in many two-stage assembly scheduling problems, the job processing times are commonly assumed as a constant over time. However, it is at odds with real production situations some times. In fact, the dynamic nature of processing time may occur when machines lose their performance during their execution times. In this case, the job that is processed later consumes more time than another one processed earlier. In view of these observations, we address the two-stage assembly linear deterioration scheduling problem in which there are two machines at the first stage and an assembly machine at the second stage. The objective is to complete all jobs as soon as possible (or to minimise the makespan, implies that the system can yield a better and efficient task planning to limited resources). Given the fact that this problem is NP-hard, we then derive some dominance relations and a lower bound used in the branch-and-bound method for finding the optimal solution. We also propose three metaheuristics, including dynamic differential evolution (DDE), simulated annealing (SA) algorithm, and cloud theory-based simulated annealing (CSA) algorithm for find near-optimal solutions. The performances of the proposed algorithms are reported as well.     

Balancing and sequencing of stochastic mixed-model assembly U-lines to minimise the expectation of work overload time

A mixed-model assembly U-line is a flexible production system capable of manufacturing a variety of similar models, and it has become popular as an important component of the just-in-time production system. However, it poses new challenges for the optimal design of assembly lines because both the task assignment and the production sequence affect the workload variance among workstations. As a consequence, this paper addresses the line balancing problem and the model sequencing problem jointly and proposes a 0–1 stochastic programming model. In this model, task times are assumed to be stochastic variables independently distributed with normal distributions and the objective is to minimise the expectation of work overload time for a given combination of cycle time and number of workstations. To solve the problem, a simulated annealing-based algorithm is developed, which can also be used to minimise the absolute deviation of workloads in a deterministic environment. The experimental results for a set of benchmark problems show that the proposed algorithm outperforms the existing algorithms in terms of solution quality and running time.     

Line balancing and model sequencing to reduce work overload in mixed-model U-line production environments

Mixed-model U-lines (MMULs) are important elements of just-in-time production systems. For successful implementation of MMULs, a smoothed workload distribution among workstations is important. This requires that line balancing and model sequencing problems are solved simultaneously. This article presents a mixed, zero–one, nonlinear mathematical programming formulation for balancing and sequencing MMULs simultaneously with the objective of reducing work overload. Since the problem is NP-hard, an effective simulated annealing approach is also presented and its performance compared with existing approaches. The results show that the proposed simulated annealing algorithm outperforms existing approaches.     

Heuristic approaches for mixed-model sequencing problem with stochastic processing times

Despite many pioneering efforts and works over the past decades, stochastic events have not been studied extensively in mixed-model assembly lines thus far. For a mixed-model sequencing problem with stochastic processing times, this paper aims to minimise expected total work overload. It also focuses on the most critical workstation of the line. In practice, this assumption is useful when the whole or a big portion of the assembly line is considered as a single station. In order to tackle the problem, a dynamic programming (DP) algorithm as well as two greedy heuristics from the literature is employed. However, it is realised that the DP cannot guarantee the optimal sequence neither for stochastic nor deterministic problems. It is because the calculation of work overload is involved in a recursive procedure that affects the states’ value functions. Therefore, by the use of network representation, the problem is modelled as a shortest path problem and a new heuristic, inspired by Dijkstra’s algorithm is developed to deal with it. Numerical results show that the proposed method outperforms other algorithms strongly. Finally, some discussion is provided about why one should consider stochastic parameters and why the proposed heuristic performs well in this regard.     

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.     

A MCVRP-based model for PCB assembly optimisation on the beam-type placement machine

The beam-type placement machine is capable of picking up multiple components simultaneously from the feeders in printed circuit board (PCB) assembly. Simultaneous pickup occurs only if the heads in the beam are aligned with the feeders and the nozzle-types on these heads match with the component-types on the feeders. In order to minimise the assembly cycle time, the optimisation problem is decomposed into two sub-problems, the pickup combination and sequencing problem, and the placement cluster and sequencing problem. These two sub-problems are simultaneously solved by the proposed hybrid genetic algorithm (HGA). The pickup combination and sequencing problem is similar to the popular multi-compartment vehicle routing problem (MCVRP); a genetic algorithm (GA) for the MCVRP is therefore modified and applied to solving the pickup combination and sequencing problem. A greedy heuristic algorithm is used to solve the placement cluster and sequencing problem. The numerical experiments reveal that the HGA outperforms the algorithms proposed by previous papers.