Evaluation of dispatching rules for cellular manufacturing

In this paper, the effects of various dispatching rules on the operation and performance of cellular manufacturing systems (CMS) are evaluated. When the study of a CMS considers the automated material handling, it is crucial to reduce the gridlock probability (i.e., the probability of an unsuccessful load transfer attempt occurring in the interface point between the intercell and intracell handling system). Preventing an unsuccessful load transfer is critical for the operation of the entire system as a blockage between the automated guided vehicle (AGV) and the overloaded cell results in a total system shutdown. The gridlock probability is influenced by the dispatching rule used to schedule the load transfers in the system. Therefore, in order to reduce this probability it is necessary to use a dispatching rule that will decrease the number of waiting loads in the transfer spurs. The main objective of the paper presented herein is to identify a dispatching rule that maintains the system operational at all times. A group of dispatching rules, including the first come first served (FCFS), shortest imminent operation (SI), longest imminent operation (LI), most remaining operations (MRO), shortest processing time (SPT), shortest remaining process time (SR), and a newly developed rule proposed by the authors, loads with the minimum number of processing first (MNP), are tested and evaluated with respect to whether the capacity of the transfer spurs of the cells is exceeded. This paper presents a simulation model of a cellular manufacturing system, which is used to further explore the effects of the dispatching rules on the system performance. The results show superior performance of the newly proposed MNP rule.     

Evaluation of dispatching rules for cellular manufacturing

In this paper, the effects of various dispatching rules on the operation and performance of cellular manufacturing systems (CMS) are evaluated. When the study of a CMS considers the automated material handling, it is crucial to reduce the gridlock probability (i.e., the probability of an unsuccessful load transfer attempt occurring in the interface point between the intercell and intracell handling system). Preventing an unsuccessful load transfer is critical for the operation of the entire system as a blockage between the automated guided vehicle (AGV) and the overloaded cell results in a total system shutdown. The gridlock probability is influenced by the dispatching rule used to schedule the load transfers in the system. Therefore, in order to reduce this probability it is necessary to use a dispatching rule that will decrease the number of waiting loads in the transfer spurs. The main objective of the paper presented herein is to identify a dispatching rule that maintains the system operational at all times. A group of dispatching rules, including the first come first served (FCFS), shortest imminent operation (SI), longest imminent operation (LI), most remaining operations (MRO), shortest processing time (SPT), shortest remaining process time (SR), and a newly developed rule proposed by the authors, loads with the minimum number of processing first (MNP), are tested and evaluated with respect to whether the capacity of the transfer spurs of the cells is exceeded. This paper presents a simulation model of a cellular manufacturing system, which is used to further explore the effects of the dispatching rules on the system performance. The results show superior performance of the newly proposed MNP rule.     

Vehicle Travel Time Models for AGV Systems under Various Dispatching Rules

The design and evaluation of AGV-based material handling systems are highly complex because of the randomness and the large number of variables involved. Vehicle travel time is a fundamental parameter for solving various flexible manufacturing system (FMS) design problems. This article presents stochastic vehicle travel time models for AGV-based material handling systems with emphasis on the empty travel times of vehicles. Various vehicle dispatching rules examined here include the nearest vehicle selection rule and the longest idle vehicle selection rule. A simulation experiment is used to evaluate and demonstrate the presented models.     

Simultaneous scheduling of machines and vehicles in an FMS environment with alternative routing

Scheduling of flexible manufacturing systems is a well-known NP-hard problem which is very complex, due to additional considerations like material handling, alternative routing, and alternative machines. Improvement in the performance of a flexible manufacturing system can be expected by efficient utilization of its resources, by proper integration and synchronization of their scheduling. Differential evolution is a powerful tool which proved itself as a better alternative for solving optimization problems like scheduling. In this paper, the authors addressed simultaneous scheduling of both machines and material handling system with alternative machines for the makespan minimization objective. The authors proposed a machine selection heuristic and a vehicle assignment heuristic which are incorporated in the differential evolution approach to assign the tasks, to appropriate machine and vehicle, and to minimize cycle time.     

CMS scheduling problem considering material handling and routing flexibility

Cell manufacturing as an application of group technology increases the flexibility and efficiency of the production. Cell scheduling problem, one of the subjects in cell manufacturing, has not been widely studied by researchers compared with other problems in cell manufacturing. In spite of great importance of material handling in cell scheduling, it has not been paid enough attention by researches. In this paper, a new mathematical model for cell scheduling problem considering material handling time and routing flexibility is proposed. The proposed model belongs to the mixed-integer nonlinear programs (MINLP). A linearization procedure is proposed to convert the MINLP to an integer program (IP) in order to develop more powerful optimization tools. Furthermore, a simulated annealing-based heuristic is developed to solve the large-size problems.     

A mathematical model and a heuristic approach for periodic material delivery in lean production environment

One of the important design elements for a good production system is material handling. In cases where it is not well-designed, it can be the bottleneck in the system. Moreover, it can cause a lot of wastes such as waiting time, idle time, and excessive transportation and cost. In this study, material handling in lean-based production environments is taken into account. Depending on the lean structure of the production systems such as being pull-based, smooth, and repetitive, delivering the materials to the stations periodically becomes important. At this point, milk-run trains are highly used in real applications since they enable the handling of required amount of materials on a planned basis. With this study, it is aimed to develop a specific model for milk-run trains which travel periodically in the production environment on a predefined route in equal cycle times with the aim of minimizing work-in-process and transportation costs. Since the milk-run trains having equal cycle times start their tours at the same time intervals, it becomes simple to manage them. For this reason, they are used in lean production systems where level scheduling is performed. The developed model is based on mixed-integer linear programming, and since it is difficult to find the optimum solution due to the combinatorial structure of the problem, a novel heuristic approach is developed. A numerical example is provided so as to show the applicability of the mathematical model and the heuristic approach.     

Workflow balancing in parallel machines through genetic algorithm

Workflow balancing helps to remove the bottlenecks present in a manufacturing system. A genetic algorithm (GA) is used to solve the parallel machine scheduling problem of the manufacturing system with the objective of workflow balancing. The performance of GA is compared with three workflow balancing strategies namely random (RANDOM), shortest processing time (SPT) and longest processing time (LPT). The relative percentage of imbalance (RPI) is adopted among parallel machines for evaluating the performance of these heuristics. The GA shows better performance for the combination of various job sizes and machines. A computer program has been coded on an IBM/PC compatible system in the C++ language for experimentation to a standard manufacturing system environment in operation.     

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.     

An efficient heuristic for scheduling batches of parts in a flexible flow system

Flexible manufacturing systems (FMSs) are a class of automated systems that can be used to improve productivity in batch manufacturing. Four stages of decision making have been defined for an FMS—the design, planning, scheduling, and control stages. This research focuses on the planning stage, and specifically in the area of scheduling batches of parts through the system.The literature to date on the FMS planning stage has mostly focused on the machine grouping, tool loading, and parttype selection problems. Our research carries the literature a step further by addressing the problem of scheduling batches of parts. Due to the use of serial-access material-handling systems in many FMSs, the batch-scheduling problem is modeled for a flexible flow system (FFS). This model explicitly accounts for setup times between batches that are dependent on their processing sequence.A heuristic procedure is developed for this batch-scheduling problem—the Maximum Savings (MS) heuristic. The MS heuristic is based upon the savings in time associated with a particular sequence and selecting the one with the maximum savings. It uses a two-phase method, with the savings being calculated in phase I, while a branch-and-bound procedure is employed to seek the best heuristic solution in phase II. Extensive computational results are provided for a wide variety of problems. The results show that the MS heuristic provides good-quality solutions.     

Optimal random storage allocation for an AS/RS in an FMS

A flexible manufacturing system (FMS) comprises, automated machine tools, automated material handling, and an automated storage and retrieval system (AS/RS) as essential components. Optimal performance of each element of this system would improve the productivity and efficiency of the total FMS. In this context, this paper attempts to link the operation of the AS/RS with the production schedule and suggests two different classes of algorithms, namely, heuristics and genetic algorithms to improve the performance of the AS/RS operation by allocating the materials with minimum movement of the shuttle.     

The control of a flexible manufacturing system by short-term goal identification

The control of manufacturing systems is characterised by the need to make a compromise between conflicting goals. Traditional research concentrates on steady-state optimisation of single objectives that are not necessarily relevant to decision making in a production environment. The advent of flexible manufacturing systems (FMSs) with automated material handling and limited buffer space highlights the need to provide computationally-efficient solutions to work out scheduling and dispatch problems for real-time applications. The authors have adopted a knowledge-based approach to achieve effective real-time FMS control. In the context of the current system status and planned system activities, short-term goals are identified which lead to appropriate jobdispatch decisions. This approach has been implemented in a prototype control system written in Prolog. To obtain knowledge in this area of scarce expertise, a “define-build-learn” cycle was adopted. First, functional concepts are defined and built into the control system, then the corresponding system characteristics are studied and the results used for further cycles of concept definition and building. This paper describes the development of this operational system.     

Solving a multi-objective overlapping flow-shop scheduling

In flow-shop manufacturing scheduling systems, managers attempt to minimize makespan and manufacturing costs. Job overlaps are typically unavoidable in real-life applications as overlapping production shortens operation throughput times and reduces work-in-process inventories. This study presents an ant colony optimization (ACO) heuristic for establishing a simple and effective mechanism to solve the overlap manufacturing scheduling problem with various ready times and a sequentially dependent setup time. In the proposed approach, the scheduling mechanism and ACO heuristics are developed separately, thereby improving the performance of overlapping manufacturing flow by varying parameters or settings within the ACO heuristics and allowing for flexible application of manufacturing by altering scheduling criteria. Finally, the experimental results of the scheduling problem demonstrate that the ACO heuristics have good performance when searching for answers.     

Dynamic dispatching for interbay material handling by using modified Hungarian algorithm and fuzzy-logic-based control

Semiconductor Wafer Fabrication System (SWFS) is one of the most complicate discrete processing systems in the world. As the wafer size grows from 200 to 300 mm and then to 450 mm in recent years, the interbay automated material handling system (AMHS) has been widely adopted. How to improve the overall efficiency of interbay material handling has therefore become a critical and urgent problem to be solved. However, the large-scale, dynamic and stochastic production environment significantly substantiates the complexity of the scheduling problem. Aiming to meet the demands of adaptive adjusting, efficient scheduling and multiple-objective optimization, a dynamic dispatching method based on modified Hungarian algorithm is proposed. The system parameters, including cassette due date, cassette waiting time, and system load are simultaneously considered, and furthermore the multi-parameters’ weight coefficients are adjusted dynamically by using the fuzzy-logic-based control. Discrete event simulation models are constructed with the eM-Plant software to evaluate the proposed approach. Experimental results show that the proposed dynamic dispatching method improves the system efficiency in terms of mean delivery time, mean waiting time and so on. Meanwhile, the proposed dispatching method has a better comprehensive performance such as the robustness compared to conventional vehicle dispatching approaches.     

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.     

Analysis of the number of automated guided vehicles required in flexible manufacturing systems

In this paper we examine some of the general principles and analysis methods that are used to design an automated material handling system. The paper focuses on one type of automated handling system that seems especially suitable for automation in discrete-product manufacturing. These types of automated handling systems are called automated guided vehicle systems. These systems are most applicable for the automation of low-and medium-volume handling situations, where the routeing of materials is more individualised. For guided vehicles, a new quantitative method for analysing these systems is developed in the paper. Examples are presented to demonstrate the method.     

KBSES: A knowledge-based system for equipment selection

In this paper, a knowledge-based system KBSES for the selection of production equipment, i.e. machine tools and material handling carriers in an automated manufacturing system, is presented. Existing expert systems which have been applied to the selection of material handling carriers are briefly reviewed. A new model for the selection of production equipment is presented. The knowledge-based system developed has a tandem architecture and closely interacts with a set of models and algorithms. The components of the system are discussed. An illustrative example is included. Directions for further research are also provided.     

Reliability analysis of flexible manufacturing systems

High productivity is the primary goal of flexible manufacturing systems (FMSs) in which semi-independent workstations are integrated using automated material-transport systems and hierarchical local networks. Availability of various subsystems and of the system as a whole is a prerequisite for achieving functional integration as well as high throughput. An FMS also has inherent routing and operation flexibilities that provide it with a certain degree of fault tolerance. A certain volume of production can thus be maintained in the face of subsystem (i.e., machines, robots, material handling system, etc.) failures. In this article, we propose two reliability measures, namely, part reliability (PR) and FMS reliability (FMSR) for manufacturing systems and present algorithms to evaluate them. We also consider the dynamic or time-dependent reliability analysis as a natural generalization of the static analysis. The methods outlined use an algorithm that generates process-spanning graphs (PSGs), which are used to evaluate the reliability measures.     

Integrated optimization of production planning and scheduling for a kind of job-shop

This paper addresses an integrated job-shop production planning and scheduling problem with setup time and batches. It not only considers the setup cost, work-in-process inventory, product demand, and the load of equipment, but also the detailed scheduling constraints. That is a way different from the traditional hierarchical production planning method. The hierarchical methods do not consider the detailed scheduling constraints, so it cannot guarantee to obtain a feasible production plan. Here the integrated problem is formulated as a nonlinear mixed integer program model. And in order to simultaneously optimize the production plan and the schedule, an improved hybrid genetic algorithm (HGA) is given. In the model, the detailed scheduling constraints are used to compute the accurate load of a device in order to obtain a feasible production plan. The heuristic scheduling rules such as the shortest processing time (SPT) and the longest processing time (LPT) are used to generate a better initial solution. Also, a subsection coding strategy is offered to convert the planning and scheduling solution into a chromosome. At last, a comparison is made between the hybrid algorithm and a hierarchical production planning and scheduling method, showing that the hybrid algorithm can solve the problem effectively.     

面向配做的柔性生产线调度

配做是精密加工中常用的方法,它增加了调度约束和调度的难度。为解决这一难题,在对各种调度约束标准化的基础上,进行了适于配做的调度操作标准化技术和启发式调度算法的研究,保证了调度解的正确性并实现了调度解的快速生成,在此基础上进行了调度解优化技术和调度评估方法的研究,最终实现了人机协同的调度、评估一体化,为配做生产提供了有效的调度工具。