Balancing of parallel U-shaped assembly lines

A new hybrid assembly line design, called parallel U-shaped assembly line system, is introduced and characterised along with numerical examples for the first time. Different from existing studies on U-shaped lines, we combine the advantages of two individual line configurations (namely parallel lines and U-shaped lines) and create an opportunity for assigning tasks to multi-line workstations located in between two adjacent U-shaped lines with the aim of maximising resource utilisation. Utilisation of crossover workstations, in which tasks from opposite areas of a same U-shaped line can be performed, is also one of the main advantages of the U-shaped lines. As in traditional U-shaped line configurations, the newly proposed line configuration also supports the utilisation of crossover workstations. An efficient heuristic algorithm is developed to find well-balanced solutions for the proposed line configurations. Test cases derived from existing studies and modified in accordance with the proposed system in this study are solved using the proposed heuristic algorithm. The comparison of results obtained when the lines are balanced independently and when the lines are balanced together (in parallel to each other) clearly indicates that the parallelisation of U-shaped lines helps decrease the need for workforce significantly.     

一种新型混合算法在混流装配调度中的应用

针对含有缓冲区的混流装配中同时存在的生产成本和库存成本问题,提出了一种基于遗传算法和差分进化算法的混合框架,并将其用于混流装配调度的实际问题中。通过融合遗传算法有效处理离散变量及差分进化算法有效处理连续变量的优点,在综合考虑降低生产成本和缓冲区库存的同时,兼顾了每个型号产品生产的顺序及数量。计算机仿真结果表明,与传统算法相比,该算法在混流装配调度上具有收敛速度快、优化能力强、算法可靠等优势。该混合算法可以显著改善多参数、高度非线性问题的优化结果,提高计算效率。     

Dynamic material flow control in mixed model assembly lines

This study investigates the control of material flow in mixed model assembly lines. It focuses on the use of tugger trains to feed stations in assembly lines by materials and parts from a warehouse or a supermarket. The movement of tugger trains is based on the principle of in-plant milk run. The study considers a strategy to deal with disturbances such as machine breakdown, line stoppage, defective parts, and resequencing of product models. These disturbances lead to unexpected fluctuations in stations demand for parts. The strategy is applied using a mix between the demand-oriented and e-kanban systems to facilitate the planning of three problems, namely, train routing, scheduling, and loading. The information obtained using e-kanban is combined with the information about the expected stations demand based on previously known sequence of product models and the materials needed for each model. Routing was investigated analytically while scheduling and loading problems were investigated using integer programming. Results showed that the method proposed outperforms the traditional methods of material flow planning.     

准序化供货模式下的混装线重排序

准序化供货是在准时制的基础上对零部件进行排序供货,其顺利实施需要依靠稳定的生产序列与零部件交付的可靠性。针对零部件交付过程中的意外事件,研究了受到意外事件影响时的工件重排序问题。首先以最小化所有工件在各工作站的超载时间与空闲时间总成本为目标,建立了问题的数学模型,并提出了三种贪婪规则和一种模拟退火算法。接着设计了算例来验证算法的性能。实验结果表明,四种算法均可在较短的时间内起到重排序的效果,其中模拟退火算法效果最好,也优于文献中的局部搜索算法。最后讨论了影响算例运行结果的因素。     

Dynamic scheduling in flexible assembly system based on timed Petri nets model

This paper investigates a scheduling model for optimal production sequencing in a flexible assembly system. The system features a set of machines working together in the same workspace, with each machine performing a subset of operations. Three constraints are considered: (1) the precedence relation among the operations specified by the assembly tree; (2) working space that limits concurrent operations; and (3) the variation of process time. The objective is to find both a feasible assignment of operations to machines and schedule tasks in order to minimize the completion time for a single product or a batch of products. The assembly process is modeled using timed Petri nets and task scheduling is solved with a dynamic programming algorithm. The method calculates the time required precisely. A detailed case study is discussed to show the effectiveness of the model and algorithm.     

Genetic algorithms for sequencing problems in mixed model assembly lines

Mixed model assembly lines are a type of production line where a variety of product models similar in product characteristics are assembled. The effective utilisation of these lines requires that a schedule for assembling the different products be determined. In this paper, the performance of genetic algorithms for sequencing problems in mixed model assembly lines is investigated. The problem first considered is a comparison between a existing heuristic and the proposed genetic algorithm to get the constant usage of every part used by the line considering variation at multi levels (Number of levels fixed as four. level 1—product, level 2—subassembly, level 3—component, level 4—raw-materials) for various test-bed problems. The algorithms proposed by Miltenburg and Sinnamon hereafter referred to as MS 1992 [IIE Trans. 24 (1992) 121] and the proposed genetic algorithm (GA) applied to mixed model assembly line are compared. Results of evaluation indicate that the GA performs better over MS1992 on 25 of the 40 problems investigated.

The other problem solved is a multiple objective sequencing problem in mixed model assembly lines. Three practically important objectives are minimizing total utility work keeping a constant rate of part-usage, minimizing the variability in parts usage and minimizing total setup cost. In this paper, the performance of the selection mechanisms, the Pareto stratum-niche cubicle and the selection based on scalar fitness function value are compared with respect to the objective of minimising variation in part-usage, minimising total utility work and minimising the setup cost. Results of evaluation indicate that the genetic algorithm that uses the Pareto stratum-niche cubicle performs better than the genetic algorithm with the other selection mechanisms.     

Evaluation of assembly sequences using generalized flexible assembly systems scheduling problem

The evaluation and selection of assembly sequences are performed in the planning stage of assembly processes. This paper deals with the effect of selecting particular assembly sequences to the performance of flexible assembly systems(FAS). The performance of FAS is evaluated using the generalized FAS scheduling problem(GFASSP). Compared to the conventional FASSP, GFASSP tries to select the most efficient assembly sequences for each product as well as minimize cycle time to complete the assemblies in FAS environment while considering the transfer time of subassemblies.     

Sequencing in mixed model assembly lines: A genetic algorithm approach

The mixed model assembly lines are becoming increasingly popular in a wide area of industries. We consider the sequencing problem in mixed model assembly lines, which is critical for efficient utilization of the lines. We extend standard formulation of the problem to allow a hybrid assembly line, in which closed and open workstations are intermixed, and sequence-dependent setup time. A new approach using an artificial intelligence search technique, called genetic algorithm, is proposed. A genetic representation suitable for the problem is investigated, and genetic control parameters that yield good results are empirically found. A new genetic operator, Immediate Successor Relation Crossover (ISRX), is introduced and several existing ones are modified. An extensive experiment is carried out to determine a proper choice of the genetic operators. The performance of the genetic algorithm is compared with those of heuristic algorithm and of branch-and-bound method. The results show that our algorithm greatly reduces the computation time and its solution is very close to the optimal solution. We have identified the ISRX operator to play a significant role in improving the performance.     

汽车混流装配线物料动态配送研究

为解决汽车混流装配线物料准确地动态配送问题,设计了基于RFID技术的汽车混流装配的零部件动态配送方案.通过RFID识别跟踪实际生产进度,将配送单动态地发给配送人员,采用惩罚函数对人员配送效率进行考核,并计算配送开始的最佳时间.结合算例验证了方案的可行性和实用性.     

Differential evolution variants to schedule flexible assembly lines

Scarce resources such as material, labor, and equipment are to be optimized to improve the performance and lower production costs in flexible assembly lines. These resources are usually allocated optimally through the generation of schedules. In this paper, variants of a differential evolution-based algorithm are employed to schedule flexible assembly lines (FAL). The performance of the assembly line is optimized based on two performance criteria, namely the weighted sum of Earliness/Tardiness penalties and the balance of the assembly line. Different variants of the Bi-level differential evolution (BiDE) algorithms are developed to study the effects of three FAL problems. The parameters of BiDE algorithm for FAL problems are fine-tuned. The performance of the BiDE algorithm is evaluated using the datasets and the Bi-level Genetic Algorithm (BiGA) available in the literature. The experimental results show that the proposed differential evolution-based algorithm outperforms BiGA in terms of mean best fitness.     

Human factor policy testing in the sequencing of manual mixed model assembly lines

In this paper the human resource management in manual mixed model assembly U-lines is considered. The objective is to minimise the total conveyor stoppage time to achieve the full efficiency of the line. A model, that includes effects of the human resource, was developed in order to evaluate human factor policies impact on the optimal solution of this line sequencing problem. Different human resource management policies are introduced to cope with the particular layout of the proposed line. Several examples have been proposed to investigate the effects of line dimensions on the proposed management policies. The examples have been solved through a genetic algorithm. The obtained results confirm the effectiveness of the proposed model on the performance optimisation of the line.Scope and purposeThis paper deals with the sequencing problem of a mixed model U-assembly line; in particular, it considers the minimisation of the total line stoppage time as an objective function. In order to improve the assembly line performances and to empathise the impact of the human resource in production environment, several help policies between workers have been analysed. Moreover, in the proposed model, finite values of the workers walking speed have been taken into account: in this way, their influence on the adopted help policies was evaluated. As the proposed problem was demonstrated to be NP-hard, a proper genetic algorithm was developed for its optimisation. An extensive experiment was carried out to determine a proper choice among the adopted help policies.     

Petri net dynamics-based scheduling of flexible manufacturing systems with assembly

This paper presents a heuristic search method based on Petri nets for scheduling flexible manufacturing systems with assembly (FMSA) by partially generating the reachability graph. FMSAs are modeled by two types of timed place Petri nets, called generalized symmetric (GSN) and asymmetric nets (GAN). GSN is a sub-class of GAN. The special Petri net structures of GSN and GAN allow us to efficiently solve their state equations for solutions that constitute a part of the proposed heuristic function. Considering the dynamic information of nets such as concurrency and synchronization, the part of the heuristic function is adjusted since state equation solutions may over-estimate the real cost. The adjustment is based on a lower bound of the real cost and on dynamically comparing the partial estimated cost and partial real cost during the search process. Extensive simulation study shows that in most cases this work obtain better solutions than prior work.     

超启发式交叉熵算法求解分布式装配柔性作业车间调度问题

本文针对一类新型两阶段分布式装配柔性作业车间调度问题(DAFJSP),建立问题模型,以最小化最大完工时间为优化目标并提出一种超启发式交叉熵算法(HHCEA)进行求解.首先,设计基于工序序列、工厂分配和产品序列的三维向量编码规则和结合贪婪策略的解码规则,同时提出4种启发式方法以提高初始解的质量.然后,设计高低分层结构的HHCEA,高层为提高对搜索方向的引导性,采用交叉熵算法(CEA)学习和积累优质排列的信息,其中各排列由结合问题特点设计的11种启发式操作(即11种有效的邻域操作)构成;低层为增加在解空间中的搜索深度,将高层确定的每个排列中的启发式操作依次重复执行指定次数并在执行过程中加入基于模拟退火的扰动机制,以此作为一种新的启发式方法执行搜索.最后,通过仿真实验与算法对比验证HHCEA可有效求解DAFJSP.     

Amacoia a multiagent system for designing flexible assembly lines

AMACOIA (approche multiagents pour la conception d'installations d'assemblage) is a tool for designing flexible assembly lines. Its objective is to determine the functional specifications of the equipment (manipulators, fixtures, grippers, conveyors, etc.) and the organizational structure (cells, workstations) for the least expensive assembly line able to assemble a product (or a family of products) within the contract cycle time. The design process is implemented by two interacting multiagent systems. One searches through the assembly sequence space, and the other searches through the assembly line space. The resulting assembly line is built by negotiation and self-organization of the agents. Both multiagent systems are regulated by simulated annealing to optimize the technological cost of the assembly line.     

Mixed-model U-shaped assembly lines: Balancing and comparing with straight lines with buffers and parallel workstations

In the paper a genetic algorithm approach is proposed to balance asynchronous mixed-model U-shaped lines with stochastic task times. U-shaped lines have become popular in recent years for their ability to outperform straight assembly lines in terms of line efficiency. The great majority of studies in the literature deal with paced synchronous U-shaped lines. Asynchronous lines can be more efficient than synchronous lines, but are more difficult to study, due to blocking and starvation phenomena caused by the variability of completion times: this makes it difficult to calculate the effective throughput. This variability, that in straight lines comes from the stochastic nature of task times and from the changing of models entering the line, is even higher in U-shaped lines, where an operator can work at two different models in the same cycle at the two sides of the line. For this reason, the genetic algorithm proposed is coupled to a parametric simulator for the evaluation of the objective function, which contains the simulated throughput. Two alternative chromosomal representations are tested on an ample set of instances from the literature. The best solutions are also compared with the best solutions known in the literature, on the same instances, for straight lines with buffers and parallel workstations. From the comparison it turns out that U-shaped lines are generally more efficient with respect to straight lines with buffers. This is because crossover work centers naturally act similarly to unitary buffers, providing two places in which two loads can be placed simultaneously. The superiority of U-shaped lines holds true as long as it is possible to take full advantage of the employment of crossover work centers. For particular types of instances, depending on the distribution of task times, this possibility decreases, so that straight lines with parallel workstations and buffers are preferable.     

一种面向柔性生产的动态调度模型*

为解决柔性生产中两个生产单元与多作业对象的优化调度问题,提出一种基于能力平衡的动态调度模型。将生产单元模型化为一种容器,把生产能力视为容积,并划分为设定能力和机动能力。通过建立两单元的机动能力连通模型,根据流体力学原理提出了一组动态调度规则,并开发了可用于现场调度的高效的启发式优化算法。在滚装运输企业进行的案例研究表明,该模型及其算法在实际生产运作中具有切实的可行性和有效性。     

Event and object oriented simulation to fast evaluate operational objectives of mixed model assembly lines problems

In this paper an event and object oriented simulator for assembly lines is presented. The tool, developed in Java, is capable to simulate mixed model assembly lines, with stochastic task times, parallel stations, fixed scheduling sequences, and buffers within workstations. The simulator is a flexible supporting tool in finding solution of the mixed model assembly line balancing problem (and the optimal sequencing and buffer allocation problems associated to it). It is capable to immediately calculate the throughput of a complex line, by simply receiving as inputs three arrays representing: the task times durations, the line configuration (number of workcentres, of buffers within them, of parallel workstations in each workcentre, of tasks assigned to each workcentre), and the sequence of models entering the line. Its fastness and flexibility allow its utilization in those algorithms and procedures where the evaluation of a fitness function (which includes the throughput as performance indicator) has to be performed several times. It allows overcoming the limit of using others measures of throughput, presented in literature, that are poorly correlated to its real value when the complexity of the line increases. The simulator is an expandable tool; in its current version provides the possibility to simulate both straight and U-shaped lines, and to generate both random and fixed sequences of models entering the line.     

以多Agent系统为架构的实时调度模型

构建了一个适用于柔性作业车间(FJSP)调度的实时模型,将车间加工设备和作业封装为Agent,通过Agent之间的招投标实现实时调度。采用了虚拟货币机制来构造实时调度模型,该机制可使交货期紧张的作业拥有更高的优先级选择加工机器,使调度方案在满足实时性的同时得到优化;模型还引入急件插入机制,在处理紧急任务时可在尽量减少对其他任务干扰的前提下顺利实现对紧急任务的调度。与其他同类调度模型相比,提出的模型在实时性、调度质量上和用户满意度上都拥有其独特优势。     

An effective algorithm for flexible assembly job-shop scheduling with tight job constraints

Thus far, the available works on the flexible assembly job-shop scheduling problem (FAJSP) consider job processing and assembly separately. However, in some real production systems, if equipment is composed of thousands of jobs and assembled in many stages, some jobs and assemblies cannot be processed simultaneously. Therefore, this work proposes an FAJSP with tight job constraints (FAJSP-JC) in which jobs and assemblies can be processed simultaneously, and each assembly is treated as an operation. A job constraint genetic algorithm (JCGA) is presented to solve the proposed FAJSP-JC with the goal of minimizing the makespan. In the JCGA, a novel two-dimensional encoding method (2D-encoding) is designed to conveniently express the operating constraints and tight job constraints, and an effective decoding method is proposed to decode the 2D-encoded information. Furthermore, a crossover operator and a mutation operator are designed to improve the computational efficiency and expand the solution space. Ten benchmark instances of the FAJSP-JC are constructed to test the JCGA. The Taguchi method is used to obtain the best combination of the key parameters that are used in the JCGA. Computational experiments carried out confirm that the JCGA is able to easily obtain better solutions compared to the genetic algorithm (GA) with a division encoding method and the classical GA, demonstrating its superior performance over these algorithms in terms of both solution quality and computational efficiency.     

An agent-based algorithm for personnel shift-scheduling and rescheduling in flexible assembly lines

This article is about a multi-agent based algorithm for personnel scheduling and rescheduling in a dynamic environment of a paced multi-product assembly center. The purpose is first to elaborate daily employees?? assignment to workstations so as to minimize the operational costs as well as personnel dissatisfactions; the second is to generate an alternative planning when the first solution has to be rescheduled due to disturbances related to absenteeism. The proposed approach takes into account individual competencies, mobility and preferences of each employee, along with the competency requirements associated with each assembly activity, with respect to both the current master assembly schedule and the line balancing for each product. We use solutions obtained through a simulated annealing algorithm in order to benchmark the performance of the multi-agent approach. Experimental results show that our multi-agent approach can produce high-quality and efficient solutions in a short computational time.