Dynamic routing and the performance of automated manufacturing cells

There has been a considerable amount of research done on the “cell formation” problem, in which machining cells are designed to process a family of components. More recently, it has been suggested that machining cells should be designed so that they take advantage of the flexibility for processing parts that have alternate, or multiple machine routing possibilities. It is argued that such flexibility will improve machine utilization as well as other measures of cell performance and may reduce the need for centralized cell loading and scheduling algorithms. Unfortunately, if the cell is automated, routing flexibility requirements can create a complex control problem for the cell controller. In this paper we implement a cell controller designed to handle the requirements of the flexible routing of parts and compare the performance of the cell to the case in which each part has only one routing. We find that significant improvements occur when the cell design is capable of processing parts with flexible routings.     

A price-directed decomposition approach for solving large-scale capacitated part-routing problems

We consider the problem of planning the production steps of several parts through a manufacturing system with both process and routing flexibilities. The problem is formulated as a network flow-based linear programming model which seeks to minimise the total material handling, production, and outsourcing costs subject to satisfying all the part demands and not exceeding any of the machine capacity limits. We develop a price-directed decomposition-based approach that exploits the special structure of the model in order to solve it. An extensive computation experiment is carried out in order to gain some insights into the impacts of flexibility in the manufacturing system on the optimal decision and cost, and to test the efficiency of the procedure in handling large scale problems.     

A methodology for designing flexible cellular manufacturing systems

Cell formation in cellular manufacturing deals with the identification of machines that can be grouped to create manufacturing cells and the identification of part families to be processed within each cell. Dynamic and random variations in part demands can negatively impact cell performance by creating unstable machine utilizations. The purpose of this paper is to introduce and illustrate an interactive cell formation method that can be used to design 'flexible' cells. Flexibility in this context refers to routing flexibility (i.e., the ability for the cellular system to process parts within multiple cells) and demand flexibility (i.e., the ability of the cell system to respond quickly to changes in part demand and part mix). Through an experimental analysis using multiple data sets, we also validate the procedure and provide guidelines for parameter settings depending upon the type of flexibility of interest to the user. Finally, trade-offs and interdependences between alternative types of flexibility in the context of cellular systems are illustrated.     

Dynamic cellular manufacturing system design considering alternative routing and part operation tradeoff using simulated annealing based genetic algorithm

In this paper, an integrated mathematical model of multi-period cell formation and part operation tradeoff in a dynamic cellular manufacturing system is proposed in consideration with multiple part process route. This paper puts emphasize on the production flexibility (production/subcontracting part operation) to satisfy the product demand requirement in different period segments of planning horizon considering production capacity shortage and/or sudden machine breakdown. The proposed model simultaneously generates machine cells and part families and selects the optimum process route instead of the user specifying predetermined routes. Conventional optimization method for the optimal cell formation problem requires substantial amount of time and memory space. Hence a simulated annealing based genetic algorithm is proposed to explore the solution regions efficiently and to expedite the solution search space. To evaluate the computability of the proposed algorithm, different problem scenarios are adopted from literature. The results approve the effectiveness of the proposed approach in designing the manufacturing cell and minimization of the overall cost, considering various manufacturing aspects such as production volume, multiple process route, production capacity, machine duplication, system reconfiguration, material handling and subcontracting part operation.     

PRODUCTION SCHEDULING IN A FLEXIBLE MANUFACTURING SYSTEM WITH SETUPS

A model is presented for the planning and scheduling of production batches in a flexible manufacturing system environment in which setup costs and times are nonnegligible and alternate routings are possible. The formulation is an integer program with a multicommodity flow network structure. A heuristic procedure based on price-directive decompostion using column generation is used to obtain solutions. Numerical experimentation is performed to assess die quality of the heuristic versus optimal solutions, and to determine the impact of routing flexibility on total cost, inventory levels, bottlenecks, capacity utilization, throughput time, number of setups and split lots. Important cost-benefit trade-off implications are shown for the design of flexible manufacturing systems.     

Efficient algorithm for cell formation with sequence data,machine replications and alternative process routings

Cell formation is an important problem in the design of a cellular manufacturing system. Despite a large number of papers on cell formation being published, only a handful incorporate operation sequence in intercell move calculations and consider alternative process routings, cell size, production volume and allocating units of identical machines into different cells. Modelling the above factors makes the cell formation problem complex but more realistic. The paper develops a model and solution methodology for a problem of cell formation to minimize the sum of costs of intercell moves, machine investment and machine operating costs considering all the factors mentioned above. An algorithm comprised of simulated annealing and local search heuristics has been developed to solve the model. A limited comparison of the proposed algorithm with an optimal solution generated by complete enumeration of small problems indicates that the algorithm produces a solution of excellent quality. Large problems with 100 parts and 50 machine types are efficiently solved using the algorithm.     

A PSO-based approach to cell formation problems with alternative process routings

Group technology (GT) has been extensively applied to cellular manufacturing system (CMS) design for decades due to many benefits such as decreased number of part movements among cells and increased machine utilisation in cells. This paper considers cell formation problems with alternative process routings and proposes a discrete particle swarm optimisation (PSO) approach to minimise the number of exceptional parts outside machine cells. The approach contains two main steps: machine partition and part-routing assignment. Through inheritance and random search, the proposed algorithm can effectively partition machines into different cells with consideration of multiple part process routings. The computational results are compared with those obtained by using simulated annealing (SA)-based and tabu search (TS)-based algorithms. Experimental results demonstrate that the proposed algorithm can find equal or fewer exceptional elements than existing algorithms for most of the test problems selected from the literature. Moreover, the proposed algorithm is further tailed to incorporate various production factors in order to extend its applicability. Four sample cases are tested and the results suggest that the algorithm is capable of solving more practical cell formation problems.     

An agent-based negotiation approach to integrate process planning and scheduling

This paper presents the development of an agent-based negotiation approach to integrate process planning and scheduling (IPPS) in a job shop kind of flexible manufacturing environment. The agent-based system comprises two types of agents, part agents and machine agents, to represent parts and machines respectively. For each part, all feasible manufacturing processes and routings are recorded as alternative process plans. Similarly, alternative machines for an operation are also considered. With regard to the scheduling requirements and the alternative process plans of a part, the proposed agent-based IPPS system aims to specify the process routing and to assign the manufacturing resources effectively. To establish task allocations, the part and machine agents have to engage in bidding. Bids are evaluated in accordance with a currency function which considers an agent's multi-objectives and IPPS parameters. A negotiation protocol is developed for negotiations between the part agents and the machine agents. The protocol is modified from the contract net protocol to cater for the multiple-task and many-to-many negotiations in this paper. An agent-based framework is established to simulate the proposed IPPS approach. Experiments are conducted to evaluate the performance of the proposed system. The performance measures, including makespan and flowtime, are compared with those of a search technique based on a co-evolutionary algorithm.     

Manufacturing cell design: an integer programming model employing genetic algorithms

The design of a cellular manufacturing system requires that a part population, at least minimally described by its use of process technology (part/machine incidence matrix), be partitioned into part families and that the associated plant equipment be partitioned into machine cells. At the highest level, the objective is to form a set of completely autonomous units such that inter-cell movement of parts is minimized. We present an integer program that is solved using a genetic algorithm (GA) to assist in the design of cellular manufacturing systems. The formulation uses a unique representation scheme for individuals (part/machine partitions) that reduces the size of the cell formation problem and increases the scale of problems that can be solved. This approach offers improved design flexibility by allowing a variety of evaluation functions to be employed and by incorporating design constraints during cell formation. The effectiveness of the GA approach is demonstrated on several problems from the literature.     

Manufacturing cells' design in consideration of various production factors

A cell formation problem is introduced that incorporates various real-life production factors such as the alternative process routing, operation sequence, operation time, production volume of parts, machine capacity, machine investment cost, machine overload, multiple machines available for machine types and part process routing redesigning cost. None of the cell formation models in the literature has considered these factors simultaneously. A similarity coefficient is developed that incorporates alternative process routing, operation sequence, operation time and production volume factors. Although very few studies have considered the machine capacity violated issue under the alternative process routing environment, owing to the difficulties of the issue discussed here, these studies fail to deal with the issue because they depend on some unrealistic assumptions. Five solutions have been proposed here and are used to cope with this difficulty. A heuristic algorithm that consists of two stages is developed. The developed similarity coefficient is used in stage 1 to obtain basic machine cells. Stage 2 solves the machine-capacity violated issue, assigns parts to cells, selects process routing for each part and refines the final cell formation solution. Some numerical examples are used to compare with other related approaches in the literature and two large size problems are also solved to test the computational performance of the developed algorithm. The computational results suggest that the approach is reliable and efficient in either the quality or the speed for solving cell formation problems.     

Machine cell formation using a mathematical model and a genetic-algorithm-based heuristic

This paper presents a comprehensive mathematical model and a genetic-algorithm-based heuristic for the formation of part families and machine cells in the design of cellular manufacturing systems. The model incorporates dynamic cell configuration, alternative routings, sequence of operations, multiple units of identical machines, machine capacity, workload balancing among cells, operation cost, subcontracting cost, tool consumption cost, set-up cost and other practical constraints. To solve this model efficiently, a two-phase genetic-algorithm-based heuristic was developed. In the first phase, independent cells are formed which are relatively simple to generate. In the second phase, the solution found during the first phase is gradually improved to generate cells optimizing inter-cell movement and other cost terms of the model. A number of numerical examples of different sizes are presented to demonstrate the computational efficiency of the heuristic developed.     

Development of manufacturing control strategies using unsupervised machine learning

This research considers the control of manufacturing systems that support job routing and process sequence flexibility. A machine learning system is presented that uses a simulation model of the target manufacturing system to discover opportunistic control rules. Learning is unsupervised and is driven by a genetic algorithm. The learning method requires very little a priori control knowledge. For this presentation, the decision-making agents are the part types being processed. Part types evolve cooperative strategies for selecting the best route through the manufacturing system based on simulated real-time information that describes the state of the system. Results are presented that demonstrate the effectiveness of the approach.     

Cellular manufacturing system design considering machines reliability and parts alternative process routings

Cell formation is an important problem in the design of cellular manufacturing systems (CMS). Most cell formation methods appeared in the literature assume that each part has one process plan, and all machines are 100% reliable with unlimited capacity. However, this is not realistic in manufacturing systems. Considering machines reliability in addition to machines capacity and machine duplicates during the part route selection process help to obtain better machine grouping and minimum total cost for CMS. Considering these factors in addition to operations sequence and production volumes makes the problem more complex but more realistic. Most of the methods appeared in the literature to solve such problems use mathematical programming procedures that take large amount of computational efforts. Procedures using similarity coefficient method are more flexible in incorporating various important production data and lend easily to computer applications. A new similarity coefficient equation that incorporates all these production factors is developed. Also, a procedure that captures the similarity between machine groups and minimises the total CMS cost is developed. The procedure utilises functional cells to eliminate intercellular moves and achieve ‘one-piece flow’ practise. The methodology is compared with other methods in the literature and found to be more effective.     

A mathematical programming model for reconfiguration of flexible manufacturing cells

In flexible manufacturing cells, changes in demand size, product mix, part variety, existing routings and set-up/operation times may require reconfiguration of the cells. In this study, an approach is developed to decide when and how such a reconfiguration should be carried out for existing cells. This study considers reconfiguration in terms of changing part routings, adding a new machine type in a cell, duplicating an existing machine type, removing an existing machine from a cell and transferring a machine to another cell. The study also shows the total number of tools of each type on each machine located in each cell after reconfiguration. To make the optimal reconfiguration decisions, a mathematical programming model to minimize the total reconfiguration cost is developed. The developed model considers the lower and upper bounds on machine utilizations and the time limits on machine cycle times to decide when to reconfigure the system.     

Flexible Parts Routing in Manufacturing Systems*

We study dynamic parts routing in flexible manufacturing systems. To quantify flexibility, we develop an entropy type of measure that incorporates all the job and machine characteristics that contribute to routing flexibility. Based on this measure and the principle of “least reduction in entropy” (LRE), two operating rules, the part selection rule and the machine selection rule, are established. These rules are then applied to drive some simulated systems and compared with the “shortest processing time” (SPT) rule. It is found that LRE either outperforms or is as good as SPT in terms of makespan and machine utilization.     

Multi-objective cell formation and production planning in dynamic virtual cellular manufacturing systems

This article presents a fuzzy goal programming-based approach for solving a multi-objective mathematical model of cell formation problem and production planning in a dynamic virtual cellular manufacturing system. In a dynamic environment, the product mix and part demand change over a planning horizon decomposed into several time periods. Thus, the cell formation done for one period may be no longer efficient for subsequent periods and hence reconfiguration of cells is required. Due to the variation of demand and necessity of reconfiguration of cells, the virtual cellular manufacturing (VCM) concept has been proposed by researchers to utilise the benefits of cellular manufacturing without reconfiguration charges. In a VCM system, machines, parts and workers are temporarily grouped for one period during which machines and workers of a group dedicatedly serve the parts of that group. The only difference of VCM with a real CM is that machines of the same group are not necessarily brought to a physical proximity in VCM. The virtual cells are created periodically depending on changes in demand volumes and mix, as new parts accumulate during a planning horizon. The major advantage of the proposed model is the consideration of demand and part mix variation over a multi-period planning horizon with worker flexibility. The aim is to minimise holding cost, backorder cost and exceptional elements in a cubic space of machine–part–worker incidence matrix. To illustrate the applicability of the proposed model, an example has been solved and computational results are presented.     

RMS中工件路径网络生成方法

利用图论建立RMS中工件路径网络生成模型。给出设备物理布局生成的3种算法：设备物理规划布局算法、基于二次布置问题(QAP)模型的VMC设备物理布局算法以及已有设备物理布局算法。给出AGV路径网络生成算法、AGV路径网络生成改进算法、可替代路径网络生成算法,包括节点间最短路径寻找子算法、路径网络预处理子算法。算法的输入为表示重构对象节点间距离信息的距离矩阵文件和表示某生产周期多工艺路线的流量文件,输出为优化的路径网络。用Visual C 实现了以上算法,实例测试验证了算法的正确性。     

Incorporating dynamism in traditional machine loading problem: an AI-based optimisation approach

Machine breakdowns have been recognised in flexible manufacturing systems (FMS) as the most undesirable characteristic adversely affecting the overall efficiency. In order to ameliorate product quality and productivity of FMS, it is necessary to analyse, as well as to minimise the effect of breakdowns on the objective measures of various decision problems. This paper addresses the machine loading problem of FMS with a view to maximise the throughput and minimise the system unbalance and makespan. Moreover, insufficient work has been done in the domain of machine loading problem that considers effect of breakdowns. This motivation resulted in a potential model in this paper that minimises the effect of breakdowns so that profitability can be augmented. The present work employs an on-line machine monitoring scheme and an off-line machine monitoring scheme in conjunction with reloading of part types to cope with the breakdowns. The proposed model bears similarity with the dynamic environment of FMS, hence, termed as the dynamic machine loading problem. Furthermore, to examine the effectiveness of the proposed model, results for throughput, system unbalance and makespan on different dataset from previous literature has been investigated with application of intelligence techniques such as genetic algorithms (GA), simulated annealing (SA) and artificial immune systems (AIS). The results incurred under breakdowns validate the robustness of the developed model for dynamic ambient of FMS.     

A robust cell formation approach for varying product demands

In cellular manufacturing environments, manufacturing cells are generally formed based on deterministic product demands. In this paper, we consider a system configuration problem with product demands expressed in a number of probabilistic scenarios. An optimization model integrating cell formation and part allocation is developed to generate a robust system configuration to minimize machine cost and expected inter-cell material handling cost. A two-stage Tabu search based heuristic algorithm is developed to find the optimal or near optimal solutions to the NP-hard problem. Numerical examples show that this model leads to an appropriate compromise between system configuration costs and expected material handling costs to meet the varying product demands. These example problems also show that the proposed algorithm is effective and computationally efficient for small or medium size problems.     

Adaptive scheduling and tool flow control in flexible job shops

The recent manufacturing environment is characterized as having diverse products due to mass customization, short production lead-time, and ever-changing customer demand. Today, the need for flexibility, quick responsiveness, and robustness to system uncertainties in production scheduling decisions has dramatically increased. In traditional job shops, tooling is usually assumed as a fixed resource. However, when a tooling resource is shared among different machines, a greater product variety, routing flexibility with a smaller tool inventory can be realized. Such a strategy is usually enabled by an automatic tool changing mechanism and tool delivery system to reduce the time for tooling set-up, hence it allows parts to be processed in small batches. In this paper, a dynamic scheduling problem under flexible tooling resource constraints is studied and presented. An integrated approach is proposed to allow two levels of hierarchical, dynamic decision making for job scheduling and tool flow control in flexible job shops. It decomposes the overall problem into a series of static sub-problems for each scheduling horizon, handles random disruptions by updating job ready time, completion time, and machine status on a rolling horizon basis, and considers the machine availability explicitly in generating schedules. The effectiveness of the proposed dynamic scheduling approach is tested in simulation studies under a flexible job shop environment, where parts have alternative routings. The study results show that the proposed scheduling approach significantly outperforms other dispatching heuristics, including cost over time (COVERT), apparent tardiness cost (ATC), and bottleneck dynamics (BD), on due-date related performance measures. It is also found that the performance difference between the proposed scheduling approach and other heuristics tend to become more significant when the number of machines is increased. The more operation steps a system has, the better the proposed method performs, relative to the other heuristics.