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.     

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.     

Dynamic selection of sequencing rules for a class-based unit-load automated storage and retrieval system

This paper studies dynamic selection of sequencing rules for a class-based unit-load automated storage and retrieval system (AS/RS). A multi-pass and genetic algorithm (MPGA) simulation system is developed and it divides storage and retrieval requests or dual commands into a series of blocks, and then conquers each block to find the most promising combination of sequencing rules. These rules are first come first served (FCFS), shortest total-travel time (STT) and shortest due time (SDT), and they can be chosen dynamically in any decision points in the system. An experiment shows that our approach with dynamic rules is much better than those approaches with any single rule used from the beginning to the end in the whole system. The results of this study provide a better way to control and manage the operation of AS/RS.     

Multicontextual dispatching rules for job shops with dynamic job arrival

The dynamic job shop problem is more challenging than the static job shop problem because dynamic job shops are disrupted by unforeseen events such as job arrivals and machine breakdowns. Each phase of a dynamic job shop problem presents a unique set of circumstances; multicontextual functions can describe the unique characteristics of a dynamic job shop at a specific time. The present work examines 11 basic dispatching rules and 33 composite rules made with multicontextual functions (MCFs) that describe machine idle time (MIT) and job waiting time (JWT). Simple procedures are presented that allow one or both of MIT and JWT to be combined with a single basic dispatching rule. This procedure produced 33 composite dispatching rules; the schedules from all 44 rules for a job shop with dynamic job arrival were compared with regard to make span and mean flow time. One composite rule, most work remaining with MCF₂, produced schedules with the shortest make spans in 21 out of 27 cases; another composite rule, most remaining operations (MRO) with MCF₃, produced schedules with the shortest mean flow times in 27 out of 27 cases. It was possible to combine JWT and MIT usefully only when the relevant dispatching rule did not depend on operation processing time; because MRO did not consider processing time, it benefitted from both JWT and MIT. Clients who demand short mean flow times might benefit from an implementation of MRO with MCF₃.     

Differentiated preemptive dispatching for automatic materials handling services in 300 mm semiconductor foundry

Highly automated materials handling in 300 mm semiconductor manufacturing is one of the biggest concerns to foundry practitioners because effective coordination among efficient manual operations has been the core competence in their 200 mm manufacturing successful stories. It is still very challenging to provide almost no-wait transport to hot lots (high priority lots) in an automatic materials handling production environment. This paper proposes an effective overhead hoist transport (OHT) dispatching rule, differentiated preemptive dispatching (DPD) policy, to reduce the possible blocking effects during the transportation of hot lots in a 300 mm OHT system. The dispatching objective is to minimize the delivery time of hot lots while minimizing the impact to the transport of normal lots. Simulation experiments based on realistic data from a local 300 mm foundry fab are conducted. Numerical results demonstrate that the DPD rule can effectively expedite the movements of hot lots. The proposed DPD rule is very useful to hot lots management and shop floor control functions, like scheduling and dispatching, in a 300 mm fab-wide automated production environment.     

Simple blocking prevention for bay type path-based automated material handling systems

This paper proposes a simple blocking prevention method for a path-based automated material handling system (AMHS) such as a semiconductor fabrication line. Here, blocking means the situation in which a vehicle stands and waits without doing anything because the vehicle in front of it is in the process of loading or unloading. Since a typical bay type path-based AMHS has a single path in each bay and no sidetracks, the blocking issue is inevitable in a large complex system with many vehicles. The proposed method is based on the swapping of load assignments between retrieval vehicles on the same path. Our simulation study on an example semiconductor line shows that the proposed method improves the AMHS productivity under various vehicle dispatching rules.     

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.     

考虑工序相关性的动态Job shop调度问题启发式算法

提出一类考虑工序相关性的、工件批量到达的动态Job shop 调度问题,在对工序相关性进行了定义和数学描述的基础上,进一步建立了动态Job shop 调度问题的优化模型。设计了一种组合式调度规则RAN(FCFS,ODD),并提出了基于规则的启发式算法以及该类动态Job shop 调度问题的算例生成方法。为验证算法和比较评估调度规则的性能,对算例采用文献提出的7种调度规则和RAN(FCFS,ODD)进行了仿真调度,对调度结果的分析表明了算法的有效性和RAN(FCFS,ODD)调度规则求解所提出的动态Job Shop 调度问题的优越性能。     

Bottleneck-based heuristic dispatching rule for optimizing mixed TDD/IDD performance in various factories

Most research on scheduling problems focuses on increasing production efficiency. For instance, the shortest processing time (SPT) and earliest due date (EDD) dispatching rules perform well in minimizing mean flow time and reducing maximum tardiness, respectively. However, those indices ignore the financial impact (material cost and order price) on the factory. Previous studies focused mainly on cycle time and due date. However, the theory of constraint (TOC) considers not only the effect of time, but also financial factors. Therefore, TOC addresses the concepts of throughput-dollar-day (TDD) and inventory-dollar-day (IDD). The former index (TDD) represents penalties for tardy deliveries, while the latter index (IDD) refers to the material holding cost. Based on these two indices, this investigation creates a novel mixed TDD/IDD weighted value (Z _value) to replace the other traditional indices for taking measurements in various factories. This study also designs a heuristic dynamic scheduling algorithm (mixed TDD/IDD dispatching rule) for reducing the system Z _value. Some traditional dispatching rules are compared with the proposed rule in terms of TDD, IDD, and Z _value. Analytical results indicate that the mixed TDD/IDD dispatching rule is feasible and generally outperforms other conventional dispatching rules in terms of Z _value under various factories.     

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.     

New dispatching rules for scheduling in a job shop — An experimental study

We present two new dispatching rules for scheduling in a job shop. These rules combine the process-time and work-content in the queue for the next operation on a job, by making use of additive and alternative approaches. An extensive and rigorous simulation study has been carried out to evaluate the performance of the proposed dispatching rules compared with those by the SPT rule, the WINQ rule, a random rule based on the SPT and WINQ rules, and the best existing rule. The important aspects of the results of the experimental investigation are also discussed in detail.     

Analysis of dispatching rules in a stochastic dynamic job shop manufacturing system with sequence-dependent setup times

Stochastic dynamic job shop scheduling problem with consideration of sequence-dependent setup times are among the most difficult classes of scheduling problems. This paper assesses the performance of nine dispatching rules in such shop from makespan, mean flow time, maximum flow time, mean tardiness, maximum tardiness, number of tardy jobs, total setups and mean setup time performance measures viewpoint. A discrete event simulation model of a stochastic dynamic job shop manufacturing system is developed for investigation purpose. Nine dispatching rules identified from literature are incorporated in the simulation model. The simulation experiments are conducted under due date tightness factor of 3, shop utilization percentage of 90 % and setup times less than processing times. Results indicate that shortest setup time (SIMSET) rule provides the best performance for mean flow time and number of tardy jobs measures. The job with similar setup and modified earliest due date (JMEDD) rule provides the best performance for makespan, maximum flow time, mean tardiness, maximum tardiness, total setups and mean setup time measures.     

Producer’s behavior analysis in an uncertain bicriteria AGV-based flexible jobshop manufacturing system with expert system

Here, an approach for finding an optimal path in a flexible jobshop manufacturing system considering two criteria of time and cost is proposed. A network is configured in which the nodes are considered to be the shops with arcs representing the paths among the shops. An automated guided vehicle functions as a material handling device through the manufacturing network. To account for uncertainty, time is considered to be a triangular fuzzy number and apply an expert system to infer the cost. The expert system based on fuzzy rule backpropagation network to configure the rules for estimating the cost under uncertainty is proposed. A multiple linear regression model is applied to analyze the rules and find the effective rules for cost estimation. The objective is to find a path minimizing an aggregate weighted unscaled time and cost criteria. A fuzzy dynamic programming approach is presented for computing a shortest path in the network. Then, a comprehensive economic and reliability analysis is worked out on the obtained paths to find the optimal producer’s behavior. Finally, an application of the model is illustrated by a numerical example. The results show the effectiveness of our approach for finding an optimal path in a manufacturing system under uncertainty.     

基于强化学习的模式驱动调度系统研究

目前,还没有一种调度规则能够根据系统环境状态的改变来进行自适应调整.对此,提出一种基于智能体的模式驱动调度系统,由智能体和仿真环境两个主要部分构成.其中,智能体将利用强化学习(Q学习算法)进行训练,以提高其动态选择合适调度规则的能力.仿真结果表明,这种模式驱动调度系统能够很好地根据系统环境状态的改变选择出对应的最优调度规则,且其调度性能优于单一调度规则,适合于系统环境不断变化的动态调度.     

A neural network for dispatching rule selection in a job shop

This paper investigates an intelligent system that selects dispatching rules to apply locally for each machine in a job shop. Randomly generated problems are scheduled using optimal permutations of three different dispatching rules on five machines. A neural network is then trained to associate between a statistical characterization of the job mix in each of these problems, with the best combination of dispatching rules to use. Once trained, the neural network is able to recommend for new problems a dispatching rule to use on each machine. Two networks are trained separately for minimizing makespan and the mean flowtime in the job shop. Test results show that the combinations of dispatching rules suggested by the trained networks produce better results, for both objectives, than the alternative of using a single rule common to all machines.     

Dispatching of overhead hoist vehicles in a fab intrabay using a multimission-oriented controller

The semiconductor manufacturing system has become one of the most important manufacturing systems in recent years. Intrabay automation for wafer transport is in high demand in a 300 mm foundry fab. The control of the transport system plays an important roles in manufacturing efficiency and the satisfaction of production strategy. In general, efficiency is the most important issue that has appeared in most research of automated transport systems. However, how to dynamically adjust the transport policy to meet the production strategy and to increase the transport efficiency as well seems to be more crucial to modern semiconductor manufacturing systems. In this paper, a fuzzy-logic-based multimission-oriented overhead vehicle dispatcher is developed. The vehicle dispatching rule is assigned in real-time according to the statistics of the manufacturing performance. In this manner, the dispatching rules can be adjusted according to possible high-risk lots so that most of the production strategies can be satisfied. If all of the lots meet the prescribed production strategies, then the nearest-job-first rule can be used to offer higher transport efficiency. In addition, the proposed vehicle dispatcher is also capable of deadlock-free operation, collision avoidance, and blockage prevention. Finally, this paper uses AutoMod simulation software to construct and evaluate the manufacturing models. By evaluating the simulation results, the proposed intelligent multimission-oriented vehicle dispatcher performs better performance than the others, and all of the production strategies are satisfied .     

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.     

An adaptive approach to dynamic scheduling in knowledgeable manufacturing cell

To overcome deficiency in the global capacity of a single dispatching rule, it is vital to select a dispatching rule in real time for dynamic scheduling. Among the studies addressing the method for selecting dispatching rules, few have no requirements for domain knowledge or accurate training example, which is hard to acquire from the real production system. In this paper, a new learning algorithm, along with the presentation of an adaptive scheduling control policy, is proposed to obtain the dynamic scheduling knowledge effectively, and different dispatching rules are selected to schedule the jobs in the machine buffer according to the current transient state of the system. Case studies are given to illustrate the validity of the scheduling control policy.     

Production-flow-value-based job dispatching method for semiconductor manufacturing

In a wafer manufacturing system, the value added to a particular product at a station may differ significantly from that added to a different product at the same station. If an enterprise concentrates mainly on generating profits, throughput becomes a poor performance measurement for a manufacturing system. Job dispatching rules based on maximum throughput no longer guarantee maximizing profit. Hence, profitability would be a good alternative measurement. The main purpose of this study is to develop a production-flow-value-based job dispatching rule (PFV) by the theory of constraints (TOC) for wafer fabrication. This study derives a TOC cost estimation method and a profitability estimate of a WIP-wafer lot. Jobs are then prioritized based on their profitability. Thus the PFV job dispatching rule is developed. For comparison, two job dispatching rules, MCR and MBS, are also arbitrarily selected to perform simulations. The simulation results reveal that the proposed PFV maximizes the production flow value, while MCR and MBS do not.     

半导体生产线动态调度方法研究

为了满足半导体生产线多目标优化要求,提出了多目标优化动态调度规则。它由正常状态调度规则、瓶颈设备较低在制品水平的调度规则、非瓶颈设备较高在制品水平的调度规则、多批加工设备调度规则以及紧急工件调度规则五种类型的调度规则组成。使用具有半导体生产线本质特征的简化模型,将多目标优化动态调度规则与先入先出法、最早交货期法、临界值法进行了比较,结果表明,多目标优化动态调度规则能够改善半导体生产线的整体性能,更好地优化模型的生产率、加工周期与在制品水平,最终提高准时交货率。