A Petri net-based heuristic for mixed-model assembly line balancing problem of Type-E

To effectively respond to the changing market demands, a manufacturer should produce variety of products with small lots. Thus, multiple products (models) are assembled simultaneously on a same line. However, it is very challenging to balance such an assembly line. This paper conducts a study on balancing a mixed-model assembly line of Type E. To solve this problem, a coloured-timed Petri net model is developed to describe the task precedence relationship. Also, the optimisation problem is formulated as a mathematical programming model. Then, with the models, a two-stage heuristic algorithm is proposed to solve the problem. At the first stage, based on the Petri net model, a P-invariant algorithm (PA) is presented to minimise the number of workstations. At the second stage, a heuristic is proposed to further minimise the cycle time by combining the PA with a binary search algorithm (BSA). Performance of the proposed method is evaluated by an illustrative example and numerical experiments. It is shown that it works well in terms of both solution accuracy and computational efficiency for large size problems.     

Decomposition heuristic for parallel-machine transfer line design with dual-uncertainties-based chance constraints

In this article, a new transfer line structure, the parallel-machine transfer line (PMTL), is studied. Compared to a traditional transfer line, PMTL is designed for high reliability due to its capacity for overdesign, by considering the uncertain failure of machines in the design. Dual uncertainties including the uncertain occurrence of machine failure and uncertain failure repair times are simultaneously considered in PMTL, and a chance-constrained programming (CCP) model is proposed for the uncertain PMTL design problem. A novel decomposition heuristic (DH) that is able to decompose the CCP into related sub-problems according to the relevance of the constraints is introduced, and linearization and transformation of the constraints are carried out to solve the sub-problems. Several experimental examples of uncertain PMTL design problems are prepared and solved by the DH and stochastic simulation, and the results show that DH outperforms the stochastic simulation with similar results but in a shorter computation time.     

A heuristic approach for balancing mixed-model assembly line of type I using genetic algorithm

The mixed model assembly line is becoming more important than the traditional single model due to the increased demand for higher productivity. In this paper, a set of procedures for mixed-model assembly line balancing problems (MALBP) is proposed to make it efficiently balance. The proposed procedure based on the meta heuristics genetic algorithm can perform improved and efficient allocation of tasks to workstations for a pre-specified production rate and address some particular features, which are very common in a real world mixed model assembly lines (e.g. use of parallel workstations, zoning constraints, resource limitation). The main focus of this study is to study and modify the existing genetic algorithm framework. Here a heuristic is proposed to reassign the tasks after crossover that violates the constraints. The new method minimises the total number of workstation with higher efficiency and is suitable for both small and large scale problems. The method is then applied to solve a case of a plastic bag manufacturing company where the minimum number of workstations is found performing more efficiently.     

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.     

Tolerance chart balancing for machining process planning

This paper provides a mathematical model for tolerance chart balancing for machining process planning. The formulation of the proposed model is based on the graphic ‘rooted tree’ representation technique in describing the sequence of the machining process. The criteria considered in the presented study are based on the combined effects of manufacturing cost and quality loss under constraints such as process capability limits, design functionality restrictions, and product quality requirements. Applications of these models include minimizing the total cost of manufacturing activities and quality related issues with process selection and tolerance allocation in machining process planning, particularly in the early stage of planning.     

Scheduling of deadlock and failure-prone automated manufacturing systems via hybrid heuristic search

This work focuses on the scheduling problem of deadlock and failure-prone automated manufacturing systems, and presents a new scheduling method by combining a robust supervisory control policy and hybrid heuristic search. It aims to minimise makespan, i.e. the completion time of the last part. Based on the extended reach ability graph of the system, it establishes a new heuristic function and two dispatching rules to guide the search process for a schedule. By embedding a robust supervisory control policy into the search process, it develops a polynomial robust dynamic window search algorithm. Failure and repair events of unreliable resources may occur during the execution of a schedule obtained by the proposed algorithm and may make the schedule infeasible. To reduce the influence caused by them and ensure all parts to be finished, this work proposes two event-driven strategies. The first one suspends the execution of the parts requiring failed resources and those to be started until all failed resources are repaired and permits only those parts that have already been processed on working machines to be completed. The second one invokes the proposed algorithm to obtain a new schedule at the vertex generated after a resource failure or repair event and executes the new schedule. Both strategies are effective while the latter performs better at the expense of more computation.     

A fast branch,bound and remember algorithm for disassembly line balancing problem

In recent years, the interests of disassembly line have increased owing to economic reasons and the increase of environmental awareness. Effective line can provide many advantages in terms of economic aspect and it facilitates competition the companies with others. This study contributes to the relevant literature by a branch, bound and remember algorithm for disassembly line balancing problem with AND/OR precedence. The proposed exact solution method employs the memory-based dominance rule to eliminate the reduplicated sub-problems by storing all the searched sub-problems and to utilise cyclic best-first search strategy to obtain high-quality complete solutions fast. In this paper, minimising the number of stations is taken as the performance measure. The proposed methodology is tested on a set of 260 instances and compared with the mathematical model using CPLEX solver and five well-known metaheuristics. Computational results show that the proposed method is capable of obtaining the optimal solutions for all the tested instances with less than 0.1?seconds on average. Additionally, comparative study demonstrates that the proposed method is the state-of-the-art algorithm and outperforms the CPLEX solver and metaheuristics in terms of both solution quality and search speed aspects.     

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.     

Flexible assembly line design problem with fixed number of workstations

In the paper, we study a flexible assembly line design problem with equipment decisions. We assume the task times and equipment costs are correlated in the sense that for all tasks the cheaper equipment gives no smaller task time. Given the cycle time and number of workstations we aim to find the assignment of tasks and equipment to the workstations so as to minimise the total equipment cost. We develop a branch and bound algorithm that uses powerful lower bounds and reduction mechanisms. Our computational experiments have revealed that our algorithm can solve large-sized problem instances in reasonable solution times.     

An improved gravitational search algorithm for profit-oriented partial disassembly line balancing problem

Disassembly is indispensable to recycle and remanufacture end-of-life products, and a disassembly line-balancing problem (DLBP) is studied frequently. Recent research on disassembly lines has focused on a complete disassembly for optimising the balancing ability of lines. However, a partial disassembly process is widely applied in the current industry practice, which aims at reusing valuable components and maximising the profit (or minimising the cost). In this paper, we consider a profit-oriented partial disassembly line-balancing problem (PPDLBP), and a mathematical model of this problem is established, which is to achieve the maximisation of profit for dismantling a product in DLBP. The PPDLBP is NP-complete since DLBP is proven to be a NP-complete problem, which is usually handled by a metaheuristics. Therefore, a novel efficient approach based on gravitational search algorithm (GSA) is proposed to solve the PPDLBP. GSA is an optimisation technique that is inspired by the Newtonian gravity and the laws of motion. Also, two different scale cases are used to test on the proposed algorithm, and some comparisons with the CPLEX method, particle swarm optimisation, differential evolution and artificial bee colony algorithms are presented to demonstrate the excellence of the proposed approach.     

A multi-objective distribution-free model and method for stochastic disassembly line balancing problem

End-of-life product recycling is a hot research topic in recent years, which can reduce the waste and protect the environment. To disassemble products, the disassembly line balancing is a principal problem that selects tasks and assigns them to a number of workstations under stochastic task processing times. In existing works, stochastic task processing times are usually estimated by probability distributions or fuzzy numbers. However, in real-life applications, only their partial information is accessible. This paper studies a bi-objective stochastic disassembly line balancing problem to minimise the line design cost and the cycle time, with only the knowledge of the mean, standard deviation and upper bound of stochastic task processing times. For the problem, a bi-objective chance-constrained model is developed, which is further approximated into a bi-objective distribution-free one. Based on the problem analysis, two versions of the ?-constraint method are proposed to solve the transformed model. Finally, a fuzzy-logic technique is adapted to propose a preferable solution for decision makers according to their preferences. A case study is presented to illustrate the validity of the proposed models and algorithms. Experimental results on 277 benchmark-based and randomly generated instances show the efficiency of the proposed methods.     

Design of stochastic assembly lines considering line balancing and part feeding with supermarkets

This article aims to address the assembly line balancing problem (ALBP) and supermarket location problem (SLP) as two long-term interrelated decision problems considering the stochastic nature of the task times and demands. These problems arise in real-world assembly lines during the strategic decision-making phase of configuring new assembly lines from both line balancing and part-feeding (PF) aspects. A hierarchical mathematical programming model is developed, in which the first level resolves the stochastic ALBP by minimizing the workstation numbers and the second level deals with the stochastic SLP while optimizing the PF shipment, inventory and installation costs. The results of case data from an automotive parts manufacturer and a set of standard test problems verified that the proposed model can optimize the configuration of assembly lines considering both ALBP and SLP performance measures. This study also validates the effect of the stochastic ALBP on the resulting SLP solutions.     

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.     

Supply chain network optimization considering assembly line balancing and demand uncertainty

In supply chain optimisation problems, determining the location, number and capacity of facilities is concerned as strategic decisions, while mid-term and short-term decisions such as assembly policy, inventory levels and scheduling are considered as the tactical and operational decision levels. This paper addresses the optimisation of strategic and tactical decisions in the supply chain network design (SCND) under demand uncertainty. In this respect, a two-stage stochastic programming model is developed in which strategic location decisions are made in the first-stage, while the second-stage contains SCND problem and the assembly line balancing as a tactical decision. In the solution scheme, the combination of sample average approximation and Latin hypercube sampling methods is utilised to solve the developed two-stage mixed-integer stochastic programming model. Finally, computational experiments on randomly generated problem instances are presented to demonstrate the performance and power of developed model in handling uncertainty. Computational experiments showed that stochastic model yields better results compared with deterministic model in terms of objective function value, i.e. the sum of the first-stage costs and the expected second-stage costs. This issue proved that uncertainty would be a significant and fundamental element of developed model and improve the quality of solutions.     

Modelling and optimisation of energy-efficient U-shaped robotic assembly line balancing problems

Within U-shaped assembly lines, the increase of labour costs and subsequent utilisation of robots has led to growing energy consumption, which is the current main expense of auto and electronics industries. However, there are limited researches concerning both energy consumption reduction and productivity improvement on U-shaped robotic assembly lines. This paper first develops a nonlinear multi-objective mixed-integer programming model, reformulates it into a linear form by linearising the multiplication of two binary variables, and then refines the weight of multiple objectives so as to achieve a better approximation of true Pareto frontiers. In addition, Pareto artificial bee colony algorithm (PABC) is extended to tackle this new complex problem. This algorithm stores all the non-dominated solutions into a permanent archive set to keep all the good genes, and selects one solution from this set to overcome the strong local minima. Comparative experiments based on a set of newly generated benchmarks verify the superiority of the proposed PABC over four multi-objective algorithms in terms of generation distance, maximum spread, hypervolume ratio and the ratio of non-dominated solution.     

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.     

A heuristic model for dynamic flexible job shop scheduling problem considering variable processing times

In real scheduling problems, unexpected changes may occur frequently such as changes in task features. These changes cause deviation from primary scheduling. In this article, a heuristic model, inspired from Artificial Bee Colony algorithm, is proposed for a dynamic flexible job-shop scheduling (DFJSP) problem. This problem consists of n jobs that should be processed by m machines and the processing time of jobs deviates from estimated times. The objective is near-optimal scheduling after any change in tasks in order to minimise the maximal completion time (Makespan). In the proposed model, first, scheduling is done according to the estimated processing times and then re-scheduling is performed after determining the exact ones considering machine set-up. In order to evaluate the performance of the proposed model, some numerical experiments are designed in small, medium and large sizes in different levels of changes in processing times and statistical results illustrate the efficiency of the proposed algorithm.     

An efficient hybrid artificial bee colony algorithm for disassembly line balancing problem with sequence-dependent part removal times

This study deals with a sequence-dependent disassembly line balancing problem by considering the interactions among disassembly tasks, and a multi-objective mathematical model is established. Subsequently, a novel hybrid artificial bee colony algorithm is proposed to solve the problem. A new rule is used to initialize a bee colony population with certain diversity, and a dynamic neighbourhood search method is introduced to guide the employed/onlooker bees to promising regions. To rapidly leave the local optima, a global learning strategy is employed to explore higher quality solutions. In addition, a multi-stage evaluation method is designed for onlookers to effectively select employed bees to follow. The performance of the proposed algorithm is tested on a set of benchmark instances and two case scenarios, and the results are compared with several other metaheuristics in terms of solution quality and computation time. The comparisons demonstrate that the proposed algorithm exhibits superior performance.     

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.     

Branch and bound and heuristic procedures for assembly line balancing with paralleling of stations

A critical assumption made in formulating the classical assembly line balancing model is that the line is ‘serial’ with no ‘paralleling’ of stations allowed. A model is proposed here which allows the paralleling of stations, thereby achieving a higher production rate and lower labour costs. The mathematical formulation of the proposed model results in a mixed integer program. A branch and bound and a heuristic solution procedure, derived from the branch and bound method, are presented. An example problem is used for illustration. Some computational experience is also provided.