A hybrid multi-objective GA for simultaneous scheduling of machines and AGVs in FMS

A carefully designed and efficiently managed material handling system plays an important role in planning and operation of a flexible manufacturing system. Most of the researchers have addressed machine and vehicle scheduling as two independent problems and most of the research has been emphasized only on single objective optimization. Multiobjective problems in scheduling with conflicting objectives are more complex and combinatorial in nature and hardly have a unique solution. This paper addresses multiobjective scheduling problems in a flexible manufacturing environment using evolutionary algorithms. In this paper the authors made an attempt to consider simultaneously the machine and vehicle scheduling aspects in an FMS and addressed the combined problem for the minimization of makespan, mean flow time and mean tardiness objectives.     

AGV schedule integrated with production in flexible manufacturing systems

Flexible manufacturing systems (FMS) comprise, automated machine tools, automated material handling, and automated storage and automated retrieval systems (AS/RS) as essential components. Effective sequencing and scheduling of the material handling systems (MHS) can have a major impact on the productivity of the manufacturing system. The material handling cannot be neglected while scheduling the production tasks. It is necessary to take into account the interaction between machines, material handling systems and computer. In this context, this paper attempts to link the operation of automated guided vehicles (AGV) with the production schedule and suggests a heuristic algorithm that employs vehicle dispatching rules (vdr) for conflict resolution. The vdrs considered in this paper are: shortest operation time (SPT), longest operation time (LPT), longest travel time (LTT) and shortest travel time (STT). The performance of the vdrs in the proposed heuristic is compared with makespan criteria. The results show that the STT provides the best solutions compared to other vdrs.     

Scheduling optimization of flexible manufacturing system using cuckoo search-based approach

In the present work, a cuckoo search (CS)-based approach has been developed for scheduling optimization of a flexible manufacturing system by minimizing the penalty cost due to delay in manufacturing and maximizing the machine utilization time. To demonstrate the application of cuckoo search (CS)-based scheme to find the optimum job, the proposed scheme has been applied with slight modification in its Levy flight operator because of the discrete nature of the solution on a standard FMS scheduling problem containing 43 jobs and 16 machines taken from literature. The CS scheme has been implemented using Matlab, and results have been compared with other soft computing-based optimization approaches like genetic algorithm (GA) and particle swarm optimization found in the literature. The results shown by CS-based approach have been found to outperform the results of existing heuristic algorithms such as GA for the given problem.     

A genetic algorithm for solving a multi-floor layout design model of a cellular manufacturing system with alternative process routings and flexible configuration

This paper presents a novel integer linear programming model for designing multi-floor layout of cellular manufacturing systems (CMS). Three major and interrelated decisions are involved in the design of a CMS; namely cell formation (CF), group layout (GL), and group scheduling (GS). A novel aspect of this model is concurrently making the CF and GL decisions to achieve an optimal design solution in a multi-floor factory. Other compromising aspects are: multi-floor layout to form cells in different floors is considered, multi-rows layout of equal area facilities in each cell is allowed, cells in flexible shapes are configured, and material handling cost based on the distance between the locations assigned to machines are calculated. Such an integrated CMS model with an extensive coverage of important manufacturing features has not been proposed before and this model incorporates several design features including alternative process routings, operation sequence, processing time, production volume of parts, duplicate machines, machine capacity, new machine purchasing, lot splitting, material flow between machines, intra-cell layout, inter-cell layout, multi-floor layout and flexible configuration. The objective is to minimize the total costs of intra-cell, inter-cell, and inter-floor material handling, new machines purchasing and machine processing. Two numerical examples are solved by the Lingo software to verify the performance of the proposed model and illustrate the model features. Sensitive analysis is also implemented on some model parameters. An improved genetic algorithm (GA) is proposed to derive near-optimal solutions for the integrated model because of its NP hardness. It is then tested using several problems with different sizes and settings to verify the computational efficiency of the developed algorithm in comparison to a classic simulated annealing algorithm and the Lingo software. The obtained results show the efficiency of proposed GA in terms of objective function value and computational time.     

Scheduling tasks and vehicles in a flexible manufacturing system

Due to their increasing applicability in modern industry, flexible manufacturing systems (FMSs), their design, and their control have been studied extensively in the recent literature. One of the most important issues that has arisen in this context is the FMS scheduling problem. This article is concerned with a new model of an FMS system, motivated by the practical application that takes into account both machine and vehicle scheduling. For the case of a given machine schedule, a simple polynomial-time algorithm is presented that checks the feasibility of a vehicle schedule and constructs it whenever one exists. Then a dynamic programming approach to construct optimal machine and vehicle schedules is proposed. This technique results in a pseudopolynomialtime algorithm for a fixed number of machines.     

An operational measure of routing flexibility in a multi-stage multi-product production system

The high degree of variety in customer demands causes mass production to become outdated and flexible production to be favored. Routing flexibility can be found in systems that implement general-purpose machines, alternative or identical machines, redundant machine tools, or the versatility of material handling systems. It is recognized that routing flexibility can be treated as a tool for enhancing system performance, such as lead time and inventory reduction. However, its implementation entails a huge cost of installation of flexible machines, automated tool changers and fixtures, and machine operators possessing multiple skills. Therefore, system managers must determine the appropriate level of routing flexibility for a specific system configuration in order to balance benefits and costs incurred. This paper presents a background to and a rational for a routing flexibility measure for a multi-stage flow shop. Instead of merely counting the number of available routes, this measure takes into account the loading balance between machines. Therefore, a manufacturing system with overloaded machines will have less routing flexibility as compared with one that is not overloaded, when both systems have the same number of available routes. An example for demonstrating the applicability of the proposed measure is also illustrated.     

Simultaneous scheduling of parts and automated guided vehicles in an FMS environment using adaptive genetic algorithm

Automated Guided Vehicles (AGVs) are among various advanced material handling techniques that are finding increasing applications today. They can be interfaced to various other production and storage equipment and controlled through an intelligent computer control system. Both the scheduling of operations on machine centers as well as the scheduling of AGVs are essential factors contributing to the efficiency of the overall flexible manufacturing system (FMS). An increase in the performance of the FMS under consideration would be expected as a result of making the scheduling of AGVs an integral part of the overall scheduling activity. In this paper, simultaneous scheduling of parts and AGVs is done for a particular type of FMS environment by using a non-traditional optimization technique called the adaptive genetic algorithm (AGA). The problem considered here is a large variety problem (16 machines and 43 parts) and combined objective function (minimizing penalty cost and minimizing machine idle time). If the parts and AGVs are properly scheduled, then the idle time of the machining center can be minimized; as such, their utilization can be maximized. Minimizing the penalty cost for not meeting the delivery date is also considered in this work. Two contradictory objectives are to be achieved simultaneously by scheduling parts and AGVs using the adaptive genetic algorithm. The results are compared to those obtained by conventional genetic algorithm.     

Simultaneous scheduling of parts and automated guided vehicles in an FMS environment using adaptive genetic algorithm

Automated Guided Vehicles (AGVs) are among various advanced material handling techniques that are finding increasing applications today. They can be interfaced to various other production and storage equipment and controlled through an intelligent computer control system. Both the scheduling of operations on machine centers as well as the scheduling of AGVs are essential factors contributing to the efficiency of the overall flexible manufacturing system (FMS). An increase in the performance of the FMS under consideration would be expected as a result of making the scheduling of AGVs an integral part of the overall scheduling activity. In this paper, simultaneous scheduling of parts and AGVs is done for a particular type of FMS environment by using a non-traditional optimization technique called the adaptive genetic algorithm (AGA). The problem considered here is a large variety problem (16 machines and 43 parts) and combined objective function (minimizing penalty cost and minimizing machine idle time). If the parts and AGVs are properly scheduled, then the idle time of the machining center can be minimized; as such, their utilization can be maximized. Minimizing the penalty cost for not meeting the delivery date is also considered in this work. Two contradictory objectives are to be achieved simultaneously by scheduling parts and AGVs using the adaptive genetic algorithm. The results are compared to those obtained by conventional genetic algorithm.     

Design of Components and Layout of Machines for Material Handling

Efficient material handling can reduce the amount of work in manufacturing operations. This paper discusses the design of components and the layout of machines from a material handling perspective. A way to reduce the material handling cost without compromising the component functionality is to choose satisfactory design options. The relationships between the design of the components and material handling are analysed to reduce the flow of material in a manufacturing system. In Model I, component routes are selected for a potential manufacturing system when only limited information regarding the layout of the machines is available. The selection of component routes is integrated with the determination of machine locations, the layout of single-row machines, and the layout of multi-row machines with equal areas, respectively, in Model II. Each problem is mathematically formulated and two algorithms are presented with illustrative examples.     

Stochastic coloured Petri nets for modelling and evaluation,and heuristic rule base for scheduling of FMS

This paper addresses scheduling of flexible manufacturing systems considering stochastic behaviour such as failure and repair of machines, and variation in processing times. Stochastic coloured Petri nets have been used for obtaining a compact model of the system. A heuristic rule base has been proposed for resolving conflicts in the allocation of jobs to machines. The superiority of the proposed approach has been exemplified with a case study.     

A cost-based algorithm for design of Cellular Manufacturing Systems

This paper describes a cost-based algorithm that deals with the design problems of Cellular Manufacturing Systems (CMS) associated exceptional parts and bottleneck machines. The developed algorithm employes explicitly the main elements of manufacturing costs, such as the fixed machine cost, the production cost, the setup cost, and the material handling cost. The algorithm is based on the minimization of sum of these costs, and considers three alternatives to solve exceptional issues. The first alternative is to try to eliminate the maximum number of intercellular movements from the presently configured manufacturing system by buying and installing extra bottleneck machines into the appropriate cells. The second alternative considers the alternative process plans available and tries to complete the job using the overtime basis in the small machine cells. The third alternative considers the possibility of subcontracting the processing operations of exceptional part(s) to outside vendors to reduce the overall cost for the manufacturing system. The total costs of the three cases are compared and the best alternative for any given problem is identified. In order to illustrate performance of the algorithm developed, a test example is provided.     

A constructive heuristic for the integrated scheduling of machines and multiple-load material handling equipment in job shops

This paper extends the traditional job shop scheduling problem (JSP) by incorporating the routing and scheduling decisions of the material handling equipment. It provides a generic definition and a mixed integer linear programming model for the problem considering the case of heterogeneous multiple-load material handling equipment. A constructive heuristic is developed for solving the problem. This heuristic is based on the well-known Giffler and Thompson’s algorithm for the JSP with modifications that account for the routing decisions of the material handling equipment and their effect on the start times of the manufacturing operations. Different dispatching rules are integrated into the heuristic, and experiments are conducted to study their effect on the makespan along with the determination of the computational time requirements of the developed heuristic.     

Multiple-Objective Scheduling for the Hierarchical Control of Flexible Manufacturing Systems

This paper presents a hierarchical approach to scheduling flexible manufacturing systems (FMSs) that pursues multiple performance objectives and considers the process flexibility of incorporating alternative process plans and resources for the required operations. The scheduling problem is solved at two levels: the shop level and the manufacturing system level. The shop level controller employs a combined priority index developed in this research to rank shop production orders in meeting multiple scheduling objectives. To overcome dimensional complexity and keep a low level of work-in-process inventory, the shop controller first selects up to three production orders with the highest ranking as candidates and generates all possible release sequences for them, with or without multitasking. These sequences are conveyed to the manufacturing system controller, who then performs detailed scheduling of the machines in the FMS using a fixed priority heuristic for routing parts of multiple types while considering alternative process plans and resources for the operations. The FMS controller provides feedback to the shop controller with a set of suggested detailed schedules and projected order completion times. On receiving these results, the shop controller further evaluates each candidate schedule using a multiple-objective function and selects the best schedule for execution. This allows multiple performance objectives of an FMS to be achieved by the integrated hierarchical scheduling approach.     

基于蚁群算法的模具制造动态调度研究

为解决模具制造动态调度问题，建立了动态调度系统。该系统利用蚁群算法和优先分配启发式算法相结合的调度算法，解决具有工件约束的模具零件的调度问题。该算法首先由蚁群算法确定模具零件各工序所用加工机床，然后利用优先分配启发式算法确定在同一台机床上加工的各零件的先后顺序。考虑动态调度的实时性，提出了局部更新和全局更新相结合的、基于滑动窗口机制的动态调度方法。对于发生频率高但对调度计划执行影响不大的扰动事件采用局部更新策略，反之则采用全局更新策略，在保证获得近优解的同时提高了动态调度的效率。     

An iterative approach to system setup problems in flexible manufacturing systems

System setup problems in flexible manufacturing systems deal with short-term planning problems such as part type selection, machine grouping, operation assignment, tooling, fixture and pallet allocation, and routing. In this article, we consider three of the subproblems: part type selection, machine grouping, and loading. We suggest a heuristic approach to solve the subproblems consistently with the objective of maximizing the expected production rate. The proposed procedure includes routines to generate all possible machine grouping alternatives for a given set of machines, to obtain optimal target workloads for each grouping alternative, and to allocate operations and tools to machine groups. These routines are executed iteratively until a good solution to the system setup problem is obtained. Computational experience is reported.     

An inter-machine material handling system for micro-manufacturing based on using a standard carrier

Lack of standardization is often a key problem area limiting the applications of any new automated micro-handling technology, due to that equipment makers may have to spend an excessive amount of time and resources to customize automation solutions. Carrier-based material handling systems provide product-independent solutions. Product independency is an essential requirement for re-using material handling systems, because they allow product change without mechanical changes in the transport devices. This paper describes a new automated inter-machine material handling system for micro-manufacturing integration, based on the standard carrier DIN-32561. The main task of the system is to transport (full/empty) carriers between different stations/machines in a micro-manufacturing plant, to integrate assembly and manufacturing. The authors designed a conveyor belt and an automated guided vehicle system to fit into a linear pick-and-place micro-manufacturing plant. Prototypes of the different components were then developed and tested.     

Combined column generation and constructive heuristic for a proportionate flexible flow shop scheduling

In a proportionate flow shop problem, jobs have to be processed through a fixed sequence of machines, and processing time for each job is equal on all machines. Such a problem has seldom been tackled. Proportionate flexible flow shop (PFFS) scheduling problems combine the properties of proportionate flow shop scheduling problems and parallel machine scheduling problems. This study presents a combined approach based on column generation (CG) for a PFFS problem with the criterion to minimize the objective of the total weighted completion time (TWCT). Minimizing TWCT in a PFFS problem significantly differs from the parallel-identical-machine scheduling problem, an optimal schedule in which jobs on each machine are in the weighted shortest processing time (WSPT) order. This combined approach adopts a CG approach to effectively handle job assignments to machines, and a constructive heuristic to obtain an optimal sequence for a single machine. Experimental results show the effectiveness of the combined approach in obtaining excellent quality solutions in a reasonable time, especially for large-scale problems.     

Performance Comparison of Some Classes of Flexible Flow Shops and Job Shops

Flexible manufacturing systems (FMSs) for two-stage production may possess a variety of operating flexibilities in the form of tooling capabilities for the machines and alternative routings for each operation. In this paper, we compare the throughput performance of several flexible flow shop and job shop designs. We consider two-stage assembly flow shops with m parallel machines in stage 1 and a single assembly facility in stage 2. Every upstream operation can be processed by any one of the machines in stage 1 prior to the assembly stage. We also study a similar design where every stage 1 operation is processed by a predetermined machine. For both designs, we present heuristic algorithms with good worst-case error bounds and show that the average performance of these algorithms is near optimal. The algorithms presented are used to compare the performance of the two designs with each other and other related flexible flow shop designs. It is shown, both analytically and experimentally, that the mode of flexibility possessed by a design has implications on the throughput performance of the production system.     

基于过程集成的闭环动态工艺规划系统

描述了一个在过程上实现工艺规划与车间规划集成的闭环动态工艺规划系统,建立了实用化CAPP系统的新模型,丰富了动态CAPP的概念。它能根据车间环境的状态,充分利用制造工艺和车间环境的柔性产生优化的工艺方案。系统在车间环境约束下采用专家系统技术进行非线性工艺规划,产生可选工艺路线和工序可选设备。在一个由工艺路线选择、设备动态优化选择和车间优化规划构成的闭环系统中,以高生产效率为目标,根据推广的关键路线分析的结果和一系列启发式知识动态地选择工艺路线和设备,最后获得有较高实践意义的结果。     

Vehicle dispatching for highly loaded semiconductor production considering bottleneck machines first

Semiconductor wafer fabrication lines can be characterized by re-entrant product flow, long production lead-time, large variety of production processes, and large capital investment. These distinctive characteristics make the flow control in the fab very complicated. Throughput rate and lead-time are among the most important performance measures. The throughput rate is usually determined by a bottleneck resource, and the lead-time depends on the machine utilization level and the amount of variability in the system. Due to the high efficiency of material handling and reduced particles, automated material handling systems such as automatic guided vehicles (AGVs), overhead hoist transporters (OHTs), and overhead shuttles (OHSs) are being widely used in wafer fabrication lines (wafer fabs) instead of human operators. Although a material handling system itself is seldom a bottleneck of production in a fab, it is important for that to effectively support the bottleneck machines to maximize the throughput and reduce production lead-time. This paper presents a vehicle dispatching procedure based on the concept of theory of constraints, in which vehicle dispatching decisions are made to utilize the bottleneck machines at the maximum level. Simulation experiments have been performed to compare the proposed vehicle dispatching procedure with existing ones under different levels of machine utilization, vehicle utilization, and local buffer capacity.