Experimental investigation of FMS machine and AGV scheduling rules against the mean flow-time criterion

Although a significant amount of research has been carried out in the scheduling of flexible manufacturing systems (FMSs), it has generally been focused on developing intelligent scheduling systems. Most of these systems use simple scheduling rules as a part of their decision process. While these scheduling rules have been investigated extensively for a job shop environment, there is little guidance in the literature as to their performance in an FMS environment. This paper attempts to investigate the performances of machine and AGV scheduling rules against the mean flow-time criterion. The scheduling rules are tested under a variety of experimental conditions by using an FMS simulation model.     

Scheduling and routing algorithms for AGVs: A survey

Automated guided vehicles (AGVs) are now becoming popular in automated materials handling systems, flexible manufacturing systems and even container handling applications. In the past few decades, much research has been devoted to the technology of AGV systems and rapid progress has been witnessed. As one of the enabling technologies, scheduling and routing of AGVs have attracted considerable attention. Many algorithms for the scheduling and routing of AGVs have been proposed. However, most of the existing results are applicable to systems with a small number of AGVs, offering a low degree of concurrency. With a drastically increased number of AGVs in recent applications (e.g. in the order of a hundred in a container handling system), efficient algorithms are needed to resolve the increased contention of resources (e.g. path, loading and unloading buffers) among AGVs. This survey paper first gives an account of the emergence of the problem of AGV scheduling and routing. It then differentiates it from several related problems and classifies major existing algorithms for the problem. Finally, the paper points out fertile areas for future study of AGV scheduling and routing.     

A beam search-based algorithm and evaluation of scheduling approaches for flexible manufacturing systems

This paper presents a new algorithm for the flexible manufacturing system (FMS) scheduling problem. The proposed algorithm is a heuristic based on filtered beam search. It considers finite buffer capacity, routing and sequence flexibilities and generates machine and automated guided vehicle (AGV) schedules for a given scheduling period. A new deadlock resolution mechanism is also developed as an integral part of the proposed algorithm. The performance of the algorithm is compared with several machine and AGV dispatching rules using mean flow time, mean tardiness and makespan criteria. It is also used to examine the effects of scheduling factors (i.e., machine and AGV load levels, routing and sequence flexibilities, etc.) on the system performance. The results indicate that the proposed scheduling algorithm yields considerable improvements in system performance over dispatching rules under a wide variety of experimental conditions.     

考虑有限物流运输能力的智能车间AGV调度算法研究

以大批量生产模式智能车间为背景,针对单环布局下多自动导航小车 （AGV） 的调度问题进行研究。首先,对典型智能车间特点进行了分析,利用Plant Simulation仿真平台建立了基于实际生产场景的仿真模型;其次,提出了基于软时间窗的AGV调度规则和基于备选调度规则集的6个运行机制;最后,通过设计仿真实验对上述7个调度规则进行了分析和比较。实验结果表明,基于软时间窗AGV调度方法总体上表现更好。这为企业配置和调度AGV小车提供了决策支持。     

A simulation study on the performance of task-determination rules and delivery-dispatching rules for multiple-load AGVs

In this paper, the control problem of multiple-load automated guided vehicles (AGVs) is studied. A control process that identifies four problems faced by multiple-load AGVs is proposed. The first problem is the task-determination problem, in which a multiple-load AGV determines whether its next task is a pickup task or a delivery task. The second problem is the delivery-dispatching problem, in which a multiple-load AGV determines which delivery point it should visit next if its next task is a delivery task. The third problem is the pickup-dispatching problem, in which a multiple-load AGV determines which pickup point it should visit next if its next task is a pickup task. Finally, the fourth problem is the load-selection problem, which requires a multiple-load AGV to determine which load it should pick up from the output queue of a pickup point. This paper focuses on the first and second problems. Different task-determination rules and delivery-dispatching rules are proposed for these two problems. For the problems that are not the main focus of this study, rules found in the literature or real systems are adopted in this study. The objective of this study is twofold. First, we need to understand how well the proposed rules will perform in different performance measures, e.g. the system's throughput and the mean lateness of parts. Second, we need to understand the mutual effects that different types of rules have on each other, so that the best combination of rules can be identified. Computer simulations were conducted to test the performance of the proposed rules. It is hoped the knowledge learned from this study can be beneficial to real multiple-load AGV systems similar to the one studied here.     

A real-time scheduling mechanism for a flexible manufacturing system: Using simulation and dispatching rules

This paper presents a real-time scheduling methodology which uses simulation and dispatching rules for flexible manufacturing systems. We develop a scheduling mechanism in which job dispatching rules vary dynamically based on information from discrete event simulation that is used for evaluating candidate dispatching rules. In this paper, we improve and extend a previous research on simulation-based real-time scheduling by suggesting a more systematic framework for the scheduling mechanism through refinement of functions of modules in the mechanism, and by presenting and analysing various scheduling strategies used to operate the mechanism. The strategies are formed by combining two factors that might influence the performance of the mechanism: type of simulation model which is used in the mechanism and points of time when new dispatching rules are selected. In order to compare performance of the scheduling strategies, computational experiments are performed and results are reported.     

Automated Two-machine Flowshop Scheduling: A Solvable Case

This paper considers new flowshop scheduling problems related to automated manufacturing systems in which n jobs are processed on two machines M_a and M_b in this order. The job transportation between two machines is done by a single automated guided vehicle (AGV), and is crucial because no machine has buffer storage for work-in-process (WIP) and hence a machine cannot release a finished job until the empty AGV becomes available at that machine, while the AGV cannot transfer an unfinished job to a machine until the machine is empty. O(n³) algorithms are given in this paper to find optimal sequences of n jobs that minimize their maximum completion time (i.e., makespan). Some numerical results are also given to evaluate the effect of computing optimal sequences.     

A hybrid modelling approach to the design of an AGV-based material handling system for an FMS

The problem of organizing and controlling the material handling activity in an AGV-based material handling system for a flexible manufacturing system involves several decisions such as the number of vehicles required for the system, the layout of the tracks, the dispatching rules for the vehicles and the provision of control zones and buffers. This paper demonstrates the use of a two-stage approach for solving the problem. The required number of vehicles is estimated using an analytical model in the first stage. In the next stage, the effects of AGV failures and AGV dispatching rules on the system performance are observed through simulation studies based on which the AGV dispatching rule can be chosen.     

Scheduling of Automated Guided Vehicles in a Decision Making Hierarchy

Scheduling efforts made without considering the special limitations of the material handling system might lead to infeasible results. An analytical model is proposed, first, to incorporate the automated guided vehicle (AGV) system into the overall decision making hierarchy. A mathematical formulation is developed to include interaction between the AGV module and other modules in the system by considering the restrictions of the material handling system. A micro-opportunistic approach is then proposed to solve the AGV scheduling problem. Finally, the proposed method is compared with a number of dispatching rules.     

A fuzzy-based approach to the liquid crystal injection scheduling problem in a TFT-LCD fab

In a thin film transistor-liquid crystal display (TFT-LCD) fab, the liquid crystal injection (LCI) process is to inject liquid crystal into the cell gaps on panels. Since its processing time is enormous (typically 12?h) compared to other processes, the LCI process is a bottleneck in the entire cell process. This study focuses on the LCI scheduling problem, which is divided into two sub-problems: automated guided vehicle (AGV) dispatching and LCI machine scheduling. A self-adjusted fuzzy (SAF) method is developed to solve the AGV dispatching problem. The SAF method is fuzzy based, and it is capable of adjusting the inference rules according to the status of the system to determine which cassette is to be transported first. A modified least slack time (MLST) method is proposed for the LCI machine scheduling problem. The MLST method assigns available LCI machines to first work on processing batches which will be finished beyond their due dates. If there are no such batches, the system releases a new batch, which is waiting in the input buffer with the least slack time, to the available LCI machine. Results indicate that the proposed SAF and MLST methods are able to finish a certain number of batches in a shorter time and reduce the tardiness of cassettes.     

Scheduling vehicles in automated transportation systems Algorithms and case study

One of the major planning issues in large scale automated transportation systems is so-called empty vehicle management, the timely supply of vehicles to terminals in order to reduce cargo waiting times. Motivated by a Dutch pilot project on an underground cargo transportation system using Automated Guided Vehicles (AGVs), we developed several rules and algorithms for empty vehicle management, varying from trivial First-Come, First-Served (FCFS) via look-ahead rules to integral planning. For our application, we focus on attaining customer service levels in the presence of varying order priorities, taking into account resource capacities and the relation to other planning decisions, such as terminal management. We show how the various rules are embedded in a framework for logistics control of automated transportation networks. Using simulation, the planning options are evaluated on their performance in terms of customer service levels, AGV requirements and empty travel distances. Based on our experiments, we conclude that look-ahead rules have significant advantages above FCFS. A more advanced so-called serial scheduling method outperforms the look-ahead rules if the peak demand quickly moves amongst routes in the system. Received: June 21, 2000 / Accepted: January 22, 2001     

An application of discrete-event simulation to on-line control and scheduling in flexible manufacturing

The on-line control and scheduling of flexible manufacturing systems has been a major interest in the production research area since these systems first appeared. In this paper, a scheduling algorithm is described which employs discrete simulation in combination with straightforward part dispatching rules in a dynamic fashion. The result is that, instead of scheduling being planned ahead of time and then being applied to a rapidly changing system, a dispatching rule is determined for each short period just before the implementation time occurs. In the long run, the algorithm combines various dispatching rules in response to the dynamic status of the system. The algorithm is described in detail. The efficacy of the algorithm is discussed and demonstrated on a prototype system.     

Modelling of an automated guided vehicle system (AG VS) in a just-in-time (JIT) environment

Like other production systems, just-in-time (JIT) systems need to address the issue of material transport between workstations such as those served by automated guided vehicles (AGVs). Unlike other production systems, however, the JIT philosophy imposes strict requirements on inventory levels and supply-demand protocols which render conventional AGV delivery strategies ineffective and counter-productive. This paper describes the modelling of an AGV system (AGVS) in a JIT environment in a way that is consistent with JIT principles. The influence of a ‘JIT perspective’ is emphasized throughout the model by introducing threshold values for both input and output queues, performance measures that emphasize lower inventories in addition to transport efficiency, and a new dispatching rule that implements better inventory and transport control. The dispatching rule is shown to perform better in a JIT environment than previously developed AGV dispatching rules in both transport and logistic criteria.     

面向“货到人”拣选系统的一种随机调度策略

通过“货到人”拣选系统作业流程分析,提出了在分批下发订单任务的情况下的一种随机调度策略。以AGV (automated guided vehicle)完成所有任务的总时间最短为目标函数,以任务分配为决策变量,考虑进行调度时AGV所处的状态以及在完成任务过程中AGV在拣选台的排队等待时间,建立随机调度策略的数学规划模型。利用遗传算法进行求解,通过实例仿真,验证了随机调度策略较调度空闲AGV策略具有更高的拣选效率,同时解决了AGV调度与拣选序列问题,对AGV数量配置具有指导作用。     

Robot and machine scheduling with state-dependent part input sequencing in flexible manufacturing systems

In competitive global markets, it is important to meet customer demands on multiple priorities such as price, quality, customisation and quick delivery. This paper investigates the problems of part input sequencing and scheduling in flexible manufacturing systems in a mass customisation/mass personalisation (MC/MP) environment. Both robot and machine scheduling rules using a state-dependent part input sequencing algorithm are investigated. Simulation experiments and statistical analyses are carried out. Effective rules are identified. The results show interactions between robot scheduling and machine scheduling in the MC/MP environment. Further research suggestions are provided.     

Performance evaluation of dynamic scheduling approaches in vehicle-based internal transport systems

This paper studies the performance of static and dynamic scheduling approaches in vehicle-based internal transport (VBIT) systems and is one of the first to systematically investigate under which circumstances, which scheduling method helps in improving performance. In practice, usually myopic dispatching heuristics are used, often using look-ahead information. We argue more advanced scheduling methods can help, depending on circumstances. We introduce three basic scheduling approaches (insertion, combined and column generation) for the static problem. We then extend these to a dynamic, real-time setting with rolling horizons. We propose two further real-time scheduling approaches: dynamic assignment with and without look-ahead. The performances of the above five scheduling approaches are compared with two of the best performing look-ahead dispatching rules known from the literature. The performance of the various approaches depends on the facility layout and work distribution. However, column generation, the combined heuristic, and the assignment approach with look-ahead consistently outperform dispatching rules. Column generation can require substantial calculation time but delivers very good performance if sufficient look-ahead information is available. For large scale systems, the combined heuristic and the dynamic assignment approach with look ahead are recommended and have acceptable calculation times.     

Scheduling a dynamic flexible flow line with sequence-dependent setup times: a simulation analysis

This paper presents a simulation-based experimental study of scheduling rules for scheduling a dynamic flexible flow line problem considering sequence-dependent setup times. A discrete-event simulation model is presented as well as eight adapted heuristic algorithms, including seven dispatching rules and one constructive heuristic, from the literature. In addition, six new proposed heuristics are implemented in the simulation model. Simulation experiments are conducted under various conditions such as setup time ratio and shop utilisation percentage. One of the proposed rules performs better for the mean flow time measure and another one performs better for the mean tardiness measure. Finally, multiple linear regression based meta-models are developed for the best performing scheduling rules.     

A comparison of sequencing rules in static and dynamic hybrid flow systems

It is well known that efficient scheduling of jobs is essential for improving the economics of production in manufacturing organizations. As a result, extensive research has been conducted on scheduling, especially in job shop and flow shop settings. In contrast, little research has been done on hybrid flow systems, even though they are found in many industries, including beer processing, glass container production, pertroleum refining, plastic-coated cable production, and fertilizer production. Furthermore, the few studies that have dealt with hybrid systems have been limited by the assumptions made about their operating environments. Therefore, we conducted a study that extends the previous work on hybrid systems in two significant ways: (1) it included financially oriented scheduling rules and a new, related performance measure; and (2) the new rules were compared with the existing ones in a large simulation experiment under both static and dynamic (generally encountered in practice) hybrid flow shop environments. To date such comparisons have been made only under static environments. The results show that the relative performances of the scheduling rules differ as the assumptions regarding the operating environment are changed.     

A study on the performance of scheduling rules in buffer-constrained dynamic flowshops

Most studies on scheduling in manufacturing systems using dispatching rules deal with jobshops, while there are only few reports dealing with dynamic flowshops. It is known that the performance of many dispatching rules in dynamic jobshops is different from that in dynamic flowshops. Moreover, many research reports assume that there are no buffer constraints in the shop, and even those reports dealing with buffer-constrained shops present the evaluation of existing dispatching rules for unconstrained shops in the context of buffer constraints with the consideration of a limited number of objectives of scheduling. In this study, we deal with the problem of scheduling in dynamic flowshops with buffer constraints. With respect to different time-based objectives, the best dispatching rules for scheduling in unconstrained shops have been identified from the existing literature. In addition, two new dispatching rules specially designed for flowshops with buffer constraints are proposed. All dispatching rules under consideration are evaluated in dynamic flowshops with buffer constraints on the basis of an extensive simulation study covering different levels of buffer constraints, shop load or utilization, and missing operations in flowshops. The proposed rules are found to perform better than the existing dispatching rules in buffer-constrained flowshops with respect to many measures of performance.     

多知识库系统的调度

利用目标网方法将多知识库系统的模块调度表示成宏观推理网络,通过执行调度规则实现调度。讨论了模块调度的实现方法,并应用于故障诊断专家系统中。