Worker allocation in lean U-shaped production lines

U-shaped lines are widely used in lean systems. In U-shaped production lines, each worker handles one or more machines on the line: the worker allocation problem is to establish which machines are handled by which worker. This differs from the widely-investigated U-line assembly line balancing problem in that the assignment of tasks to line locations is fixed. This paper address the worker allocation problem for lean U-shaped production lines where the objectives are to minimize the quantity of workers and maximize full work: such allocations provide the opportunity to eliminate the least-utilized worker by improving processes accordingly. A mathematical model is developed: the model allows for any allocation of machines to workers so long as workers do not cross paths. Walking times are considered, where workers follow circular paths and walk around other worker(s) on the line if necessary. A heuristic algorithm for tackling the problem is developed, along with a procedure representing the ‘traditional’ approach of constructing standard operations routines. Computational experiments considering three line sizes (up to 20 machines) and three takt time levels are performed. The results show that the proposed algorithm both improves upon the traditional approach and is more likely to provide optimal solutions.     

Coordinating batching decisions in manufacturing networks

Family-based dispatching heuristics aim for improving job flow times by reducing time spent on set-ups. They realise set-up efficiencies by batching similar types of jobs. By their intuitiveness and the simplicity of their decision logic, they may contribute to an easy to implement and viable strategy in many practical settings. Similar to common dispatching rules most existing family-based dispatching heuristics are myopic, i.e. their decision scope is restricted to a single manufacturing stage. Hence, they neglect opportunities for improving shop performance by coordinating batching decisions with other manufacturing stages. Case examples from industry underpin the need for exploring these opportunities. We do so by studying a simple two-stage flow shop, entailing a serial and a batch stage. To facilitate shop coordination we propose extensions to existing family-based dispatching heuristics. Extended heuristics seek to further increase set-up efficiencies by allowing for upstream job re-sequencing, and pro-active set-ups, i.e. set-ups that may be initiated prior to the arrival of a job. Outcomes of an extensive simulation study indicate significant performance gains for extended heuristics vs. existing heuristics. Performance gains are largest for moderate and high set-up to run-time ratios.     

Scheduling with product family set-up times: an application in TFT LCD manufacturing

The development of a scheduling methodology for module processing in thin film transistor liquid crystal display manufacturing is presented. The problem is a parallel machine-scheduling problem with family set-up times and due dates. Two objectives are considered: total tardiness and the number of family set-ups. Two heuristics are developed based on the MULTIFIT method and tabu search. The experimental results show that the proposed algorithms give schedules that are very efficient in terms of both total tardiness and the number of family set-ups.     

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.     

An ant colony optimisation algorithm for balancing two-sided U-type assembly lines with sequence-dependent set-up times

Some practical arrangements in assembly lines necessitate set-up times between consecutive tasks. To create more realistic models of operations, set-up times must be considered. In this study, a sequence-dependent set-up times approach for two-sided u-type assembly line (TUAL) structures is proposed for the first time. Previous studies on TUAL have not included set-up times in their analyses. Furthermore, an algorithm based on the Ant Colony Optimization (ACO) algorithm, which is using a heuristic priority rule based procedure has been proposed in order to solve this new approach. In this paper, we look at the sequence-dependent set-up times between consecutive tasks and consecutive cycles, called the “forward set-up time” and the “backward set-up time”, respectively. Additionally, we examine the “crossover set-up time”, which arises from a new sequence of tasks in a crossover station. In order to model more realistic assembly line configurations, it is necessary to include sequence-dependent set-up times when computing all of the operational times such as task starting times and finishing times as well as the total workstation time. In this study, the proposed approach aims to minimize the number of mated-stations as the primary objective and to minimize the number of total workstations as a secondary objective. In order to evaluate the efficiency of the proposed algorithm, a computational study is performed. As can be seen from the experimental results the proposed approach finds promising results for all literature-test problems.     

Robotic U-shaped assembly line balancing using particle swarm optimization

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

Family-based dispatching with parallel machines

Family-based dispatching heuristics seek to lower set-up frequencies by grouping similar types of jobs for joint processing. Hence, job flow times may be improved as less time is spent on set-ups. So far, family-based dispatching with parallel machines received little attention in literature. We address the perceived gap by proposing extensions to existing family-based dispatching heuristics. Main extensions concern improved rules for family priority settings and for coordinating the number of machines in use by a single family. Extended heuristics are tested by an extensive simulation study. Significant performance gains for extended heuristics vs. existing heuristics are found. Performance gains are largest for high set-up to run-time ratios.     

A Cost-Oriented Approach to Stochastic Line Balancing1

This paper presents a new heuristic for balancing paced assembly lines involving tasks which exhibit significant time variations. Labor and incompletion costs are explicitly considered in grouping tasks into work assignments to achieve a near minimum cost line design. The procedure is computationally attractive because its calculations are comparably efficient to those of heuristics which consider task times deterministically.     

Assembly sequence planning for processes with heterogeneous reliabilities

Stochasticity in assembly processes is often associated with the processing time and availability of machinery, tools and manpower, however in this paper it is determined by probability of an assembly task successful completion which here is referred to as task reliability. We present a mathematical model for optimising the expected assembly cost, and consider two scenarios: the first a situation where a failure of one assembly task requires rework of that task alone; second a situation in which a failure in the midst of the process requires resumption of previously completed tasks. In the worst case scenario the assembly process must restart from the beginning. We show that the first scenario is insensitive to sequencing unless there are set-up costs. In the second scenario the process is sensitive to tasks’ sequence. We present a heuristic that argues for accomplishing more uncertain tasks (with less reliability) earlier in the process to decrease the expected cost of assembly, and show that in a mutually dependent assembly process, when tasks’ reliabilities are similar, the cheaper tasks should be executed earlier in the process.     

Balancing two-sided assembly lines with sequence-dependent setup times

Two-sided assembly lines are often designed to produce large-sized products, such as automobiles, trucks and buses. In this type of production line, both left-side and right-side of the line are used in parallel. In all studies on two-sided assembly lines, sequence-dependent setup times have not yet been considered. However, in real life applications, setups may exist between tasks. Performing a task directly before another task may influence the latter task inside the same station, because a setup for performing the latter task may be required. Furthermore, if a task is assigned to a station as the last one, then it may cause a setup for performing the first task assigned to that station since the tasks are performed cyclically. In this paper, the problem of balancing two-sided assembly lines with setups (TALBPS) is considered. A mixed integer program (MIP) is proposed to model and solve the problem. The proposed MIP minimises the number of mated-stations (i.e., the line length) as the primary objective and it minimises the number of stations (i.e., the number of operators) as a secondary objective for a given cycle time. A heuristic approach (2-COMSOAL/S) for especially solving large-size problems based on COMSOAL (computer method of sequencing operations for assembly lines) method is also presented. An illustrative example problem is solved using 2-COMSOAL/S. To assess the effectiveness of MIP and 2-COMSOAL/S, a set of test problems are solved. The computational results show that 2-COMSOAL/S is very effective for the problem.     

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.     

Maximising profit for multiple-product,single-period,single-machine manufacturing under sequential set-up constraints that depend on lot size

The classical problem of order acceptance/rejection in make-to-order environments, when aiming to maximise profit with machine set-ups is extended in this paper to multiple set-ups depending on manufacturing batch size. In this case, if the manufacturing batch is larger than certain product-dependent bounds, not only is the initial set-up required but also periodic reset-ups are in order, generating sub-batches of the same order, such as tool resharpening and machine recalibration. A network formulation provides the basis for identifying effective algorithms to obtain a solution to the problem. A binary programming model (BPM) and a dynamic programming formulation (DPF) are proposed to solve the problem to optimality. In addition, two heuristics are developed to obtain lower bounds on maximum profit: each attempt to maximise customer satisfaction under production time restrictions, and to provide an extension to the classical knapsack problem. Numerical experimentation shows that computational time is not an issue when BPM and heuristics are applied, but the cost of commercial solvers for BPM algorithms might be problematic. However, if the aim is to code the DPF in-house, the curse of dimensionality in dynamic programming must be addressed, although dynamic programming does yield a full sensitivity analysis, which is useful for decision-making.     

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.     

Multiperiod production planning carrying over set-up time

Set-ups eat production capacity time and continue troubling production planning, especially on bottlenecks. The shortening of production planning periods to days, shifts or even less has increased the relative length of set-up times against the periods. Yet, many production planning models either ignore set-up times or, paradoxically, split longer multiperiod batches by adding set-ups at breaks between planning periods. The MILP-based capacitated lot-sizing models that include set-up carry-overs, i.e. allow a carry-over of a set-up of a product to the next period in case a product can be produced in subsequent periods, have incorporated fixed set-up fees without consideration of capacity consumed by set-up time. Inspired by production planning in process industries where set-up times still remain substantial, we incorporated set-up time with associated cost in two modifications of carry-over models. Comparison with an earlier benchmark model without set-up carry-over shows that substantial savings can be derived from the fundamentally different production plans enforced by carry-overs. Moreover, we show that heuristic inclusion of carry-overs by removal of set-ups from non-carry-over solutions is inefficient.     

带时限与回程的配送中心运输调度问题研究

在优化模型中将配送任务执行时间及每日调用车辆数量及路径作为决策对象,以车辆的固定费用、行驶费用、未按时完成服务产生的惩罚、存储费用等作为优化目标。在遗传算法中采用自然数编码形式以便于优化车辆数量,采用基于扫描算法的启发式算法构造更好的初始解,引入单亲遗传算子、重启机制及并行禁忌搜索以提高种群质量和深度寻优。经不同规模算例间对比测试,显示基于扫描算法的混合遗传算法具有最佳的优化性能。     

Sequence Dependent Machine Set-Up Times and Similarity of Parts: A Mathematical Model

This paper attempts to develop a mathematical relation between machine set-up times and similarity of parts. First, the task for setting up a machine was broken down into a distinct number of elements whose state was expressed as a binary vector called set-up task elimination vector. By introducing a corresponding rime vector, it was shown that sequence dependent set-up time is the product of the two vectors. Next, a quantitative relation between set-up tasks and the design characteristics of parts was defined as a binary interaction matrix while the similarity of parts was defined as a binary vector. It turned out that the set-up tasks elimination vector is the Boolean product of the interaction matrix and the similarity vector. Using this information, a machine set-up model was developed in terms of similarity of parts. The computation of machine set-up times and a sequencing heuristic using the model were illustrated.     

An optimisation support for the design of hybrid production lines including assembly and disassembly tasks

The optimisation problems related to the assignment of tasks to workstations in assembly and disassembly lines have been largely discussed in the literature. They are known, respectively, as Assembly Line Balancing and Disassembly Line Balancing Problems. In this study, both types of task performed on the identical product are integrated in a common hybrid production system. Therefore, the logistic process is simplified and disassembly tasks can supply easier the assembly tasks with the required components. The considered production system has the layout of two parallel lines with common workstations. The product flow is conventional in the assembly line and reverse in the disassembly line. The paper provides a new mathematical model for designing such a hybrid system and an approximate approach based on ant colony optimisation for solving large-scale instances. The solution method is tested in a case study. The obtained results are compared with the solution provided by the design of two independent lines. The analysis of the results highlights the potential benefits of the hybrid production system.     

随机型双边装配线平衡问题的一种启发式算法

为有效求解随机型双边装配线第Ⅰ类平衡问题(STALBP 1),在分析双边装配线平衡特点的基础上,考虑各任务操作时间的随机性,提出了一种启发式算法。在该启发式算法中,假定各任务的操作时间服从正态分布,运用具有操作方位约束的任务优先分配等规则来进行任务的选择和分配,通过改变预设超限概率,在不同生产节拍下,分别得到不同的平衡方案。实例验证了算法的有效性。     

Lot-splitting approach of a hybrid manufacturing system under CONWIP production control: a mathematical model

This paper discusses the advantages of lot splitting in hybrid manufacturing environments where cellular and functional layouts are combined under Constant Work in Process (CONWIP) production control. The proposed model fills a research gap in the related literature by applying lot splitting and pull production simultaneously. A linear CONWIP control mathematical model that minimises the average flow time is developed in case of lot splitting. The developed model has sequence-dependent set-up times. The demand level, coefficient of variation (CV) impact and set-up time reduction effect on CONWIP production control are also investigated. The model is solved using GAMS21.6 optimisation software; the optimal backlog list, the number and size of sublots are reported. The proposed model is compared with lot production under push control in different settings as well as with two different heuristics from the literature. Experimental results indicate that in all settings, the lot splitting is more advantageous than lot production in terms of average flow time. CV has a greater effect than set-up time reduction on average flow time.     

Balancing of mixed-model parallel U-shaped assembly lines considering model sequences

As a consequence of increasing interests in customised products, mixed-model lines have become the most significant components of today’s manufacturing systems to meet surging consumer demand. Also, U-shaped assembly lines have been shown as the intelligent way of producing homogeneous products in large quantities by reducing the workforce need thanks to the crossover workstations. As an innovative idea, we address the mixed-model parallel U-shaped assembly line design which combines the flexibility of mixed-model lines with the efficiency of U-shaped lines and parallel lines. The multi-line stations utilised in between two adjacent lines provide extra efficiency with the opportunity of assigning tasks into workstations in different combinations. The new line configuration is defined and characterised in details and its advantages are explained. A heuristic solution approach is proposed for solving the problem. The proposed approach considers the model sequences on the lines and seeks efficient balancing solutions for their different combinations. An explanatory example is also provided to show the sophisticated structure of the studied problem and explain the running mechanism of the proposed approach. The results of the experimental tests and their statistical analysis indicated that the proposed line design requires fewer number of workstations in comparison with independently balanced mixed-model U-lines.