Effects of routing flexibility, sequencing flexibility and scheduling decision rules on the performance of a flexible manufacturing system

This paper focuses on a simulation-based experimental study of the interaction among routing flexibility, sequencing flexibility and part sequencing rules in a typical flexible manufacturing system (FMS). Two scenarios are considered for experimentation. Three routing flexibility levels, five sequencing flexibility levels and four scheduling rules for part sequencing decision are considered for detailed investigation. The performance of the FMS is evaluated using various measures related to flow time and tardiness of parts. The simulation results are subjected to statistical analysis. The analysis of results reveals that deterioration in system performance can be minimized substantially by incorporating either routing flexibility or sequencing flexibility or both. However, the benefits of either of these flexibilities diminish at higher flexibility levels. Part sequencing rules such as earliest due date and earliest operation due date provide better performance for all the measures at higher flexibility levels.     

Flow time analyses of a simulated flexible job shop by considering jockeying

It has been essential to include flexibility in manufacturing policy making since variability in demand and products are considerably increasing. However, it is important to know and to monitor the proper level and type of flexibility that is required to obtain full benefits from it. This paper analyses the effects of flexibility on flow time performance of a simulated job shop. For that purpose, several scenarios are developed under four flexibility levels with two different machine selection rule and three types of dispatching rules. Furthermore, effect of jockeying as a queuing policy on the flow time performance is also investigated through simulation modeling. Results indicated that full flexibility is a preferable state for most of the cases. However, in some cases, chain configurations perform similar results since it combines the benefits of pooling and specialization. In addition, it is observed that a queue control mechanism like jockeying is an effective way to improve performance even though it may increase complexity of controlling policy.     

New dispatching rules to minimize rejection and tardiness costs in a dynamic flexible flow shop

This paper studies a flexible flow shop system considering dynamic arrival of jobs and the ability of acceptance and rejection of new jobs. The problem objective is to determine a schedule that minimizes sum of the tardiness and rejection costs of jobs. A 0–1 mixed integer model of the problem is formulated. Since this problem class is NP-hard, four dispatching rules have been developed to solve the problem approximately. Moreover, a discrete event simulation model of the flexible flow shop system is developed for the purpose of experimentation. Four dispatching rules from the literature and four new dispatching rules proposed in this paper are incorporated in the simulation model. Simulation experiments have been conducted under various experimental conditions characterized by factors such as shop utilization level, due date tightness and number of stages in flexible flow shop. The results indicate that proposed dispatching rules provide better performance under problem assumptions.     

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.     

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.     

Real-time scheduling with deadlock avoidance in flexible manufacturing systems

The dynamic nature of manufacturing makes rescheduling essential in today's complex production environment, particularly in flexible and re-configurable systems. Research on optimising schedules, which includes deadlock avoidance, is rather limited. Furthermore, the deadlock problem is mostly ignored in research on rescheduling. A rescheduling algorithm, that uses time petri-nets and the minimal siphons concept, was developed to deal with sources of disturbance such as machine breakdowns in real-time. The algorithm guarantees a deadlock-free new schedule. The existence of alternative routes, availability of material handling facilities and the limitation of buffer capacities were taken into consideration. The developed algorithm modifies only the affected portion of the original schedule, rather than rescheduling all jobs, in order to limit changes to the original schedule and reduce the impact on the response time.The effect of flexible routing, machine breakdowns, machine downtime, routing criterion and the use of the dispatching rule on the performance of manufacturing systems was studied. The systems performance was measured by the average flow time, the makespan and the average machine utilisation. The results indicate that utilising the system routing flexibility in real-time rescheduling, while avoiding deadlocks, improves system performance. Moreover, routing the interrupted operation to an alternative machine, based on the minimum expected completion time rather than the least utilised machine criterion, resulted in better performance.     

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 routing flexibility of a flexible manufacturing system using simulation modelling and analysis

Routing flexibility is a major contributor of the flexibility of a flexible manufacturing system (FMS). The present paper focuses on the evaluation of the routing flexibility of an FMS with the dynamic arrival of part types for processing in the system. A typical FMS configuration is chosen for detailed study and analysis. The system is set at five different levels of routing flexibility. Operations of part types can be processed on alternative machines depending upon the level of routing flexibility present in the system. Two cases have been considered with respect to the processing times of operations on alternative machines. A discrete-event simulation model has been developed to describe the operation of the chosen FMS. The performance of the system under various levels of routing flexibility is analyzed using measures such as mean flow time, mean tardiness, percentage of tardy parts, mean utilisation of machines, mean utilisation of automatic-guided vehicles, and mean queue length at machines. The routing flexibility for producing individual part types has been evaluated in terms of measures such as routing efficiency, routing versatility, routing variety and routing flexibility. The routing flexibility of the system has been evaluated using these measures. The flexibility levels are ranked based on the routing flexibility measure for the system. The ranking thus obtained has been validated with that derived using fuzzy logic approach.     

Effectiveness of flexible routing control

Flexibility in part process representation and in highly adaptive routing algorithms are two major sources for improvement in the control of flexible manufacturing systems (FMSs). This article reports the investigation of the impact of these two kinds of flexibilities on the performance of the system. We argue that, when feasible, the choices of operations and sequencing of the part process plans should be deferred until detailed knowledge about the real-time factory state is available.To test our ideas, a flexible routing control simulation system (FRCS) was constructed and a programming language for modeling FMS part process plans, control strategies, and environments of the FMS was designed and implemented. In addition, a scheme for implementing flexible process routing called data flow dispatching rule (DFDR) was derived.The simulation results indicate that flexible processing can reduce mean flow time while increasing system throughput and machine utilization. We observed that this form of flexibility makes automatic load balancing of the machines possible. On the other hand, it also makes the control and scheduling process more complicated and calls for new control algorithms.     

The Effects of Scheduling Rules and Routing Flexibility on the Performance of a Random Flexible Manufacturing System

The increased use of flexible manufacturing systems to efficiently provide customers with diversified products has created a significant set of operational challenges for managers. Many issues concerning procedures and policies for the day-to-day operation of these systems still are unresolved. Previous studies in this area have concentrated on various problems by isolating or simplifying the systems under study. The primary objective of this study is to extend previous research by examining the effects of scheduling rules and routing flexibility on the performance of a constrained, random flexible manufacturing system (FMS). Other experimental factors considered are shop load, shop configuration, and system breakdowns. Within the bounds of this experiment, the results indicate that, in the presence of total routing flexibility, the effects of shop load, system breakdowns, and scheduling rules are significantly dampened. In particular, when total routing flexibility exists, the choice of scheduling rules is not critical. We also show that the behavior of scheduling rules in a more constrained FMS environment (i.e., where system breakdowns occur and material handling capability is limited) is consistent with the findings of previous research conducted under less constrained environments. Finally, results indicate that the shop configuration factor has little or no impact on a system's flow-time performance.     

Dynamic Scheduling for a Flexible Manufacturing System - The Pre-emptive Approach

This paper presents a simulation model of a flexible manufacturing system (FMS) which minimises three performance criteria simultaneously, i.e. mean flow-time, mean tardiness, and mean earliness. The dispatching rule will be changed at a frequency that is varied by the quantity of output produced by the system. Therefore, the dynamic system is an event-trigger rather than triggered by changing the rule at regular time intervals, which is passive. Three indices are used to represent the three criteria being monitored, and the indices are ranked in descending order. The larger the index, the worse is the condition of the criterion in the system. An appropriate rule will be selected for the next operation in order to tackle that criterion with the largest index. This mechanism is called the pre-emptive method. Furthermore, the indices can be biased by the decision maker so that a particular criterion can have larger weighting. Results show that a solution (range of frequency) can always be obtained for changing the dispatching rule so that the system is better than one which just uses fixed FMS scheduling rules.     

Dynamic flexible job shop scheduling with alternative process plans: an agent-based approach

This paper studies a flexible job shop problem considering dynamic events such as stochastic job arrivals, uncertain processing times, and unexpected machine breakdowns. Also, the considered job shop problem has routing flexibility and process flexibility. A multi-agent scheduling system has been developed for solution with good quality and robustness. A pheromone-based approach is proposed for coordination among agents. The proposed multi-agent approach is compared with five dispatching rules from literature via simulation experiments to statistical analysis. The simulation experiments are performed under various experimental settings such as shop utilization level, due date tightness, breakdown level, and mean time to repair. The results show that the proposed agent-based approach performs well under all problem settings.     

Evaluation of the impact of information delays on flexible manufacturing systems performance in dynamic scheduling environments

The significance of the adverse effects of information delays (IDs) on flexible manufacturing system (FMS) performance is getting increasing attention from manufacturing systems managers, planners, schedulers, Enterprise Resource Planning software developers, and researchers because of their potential to disrupt production schedules. In this paper, we examine the extent of the adverse impact that IDs have on FMS performance. The FMSs are assumed to operate in a “review period” mode; i.e., the control decisions (e.g., sequencing and dispatching) are taken based on information monitored at predetermined intervals of time called “review periods”. The performance deterioration occurs due to the obsolescence of system status information. Key empirical findings based on extensive simulation experiments are: (1) IDs significantly degrade FMS performance for due date-based measures (mean tardiness and percent of jobs tardy); (2) IDs also degrade FMS performance for non-due date-based measures (mean flowtime and average machine utilization), albeit to a less severe degree; (3) routing flexibility, often regarded as a significant factor to influence FMS performance, is superseded by status review information delay.     

Ant colony optimization for job shop scheduling using multi-attribute dispatching rules

This paper proposes a heuristic method based on ant colony optimization to determine the suboptimal allocation of dynamic multi-attribute dispatching rules to maximize job shop system performance (four measures were analyzed: mean flow time, max flow time, mean tardiness, and max tardiness). In order to assure high adequacy of the job shop system representation, modeling is carried out using discrete-event simulation. The proposed methodology constitutes a framework of integration of simulation and heuristic optimization. Simulation is used for evaluation of the local fitness function for ants. A case study is used in this paper to illustrate how performance of a job shop production system could be affected by dynamic multi-attribute dispatching rule assignment.     

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.     

A flexible artificial neural network–fuzzy simulation algorithm for scheduling a flow shop with multiple processors

One of the most popular approaches for scheduling manufacturing systems is dispatching rules. Different types of dispatching rules exist, but none of them is known to be globally the best. A flexible artificial neural network–fuzzy simulation (FANN–FS) algorithm is presented in this study for solving the multiattribute combinatorial dispatching (MACD) decision problem. Artificial neural networks (ANNs) are one of the commonly used metaheuristics and are a proven tool for solving complex optimization problems. Hence, multilayered neural network metamodels and a fuzzy simulation using the α-cuts method were trained to provide a complex MACD problem. Fuzzy simulation is used to solve complex optimization problems to deal with imprecision and uncertainty. The proposed flexible algorithm is capable of modeling nonlinear, stochastic, and uncertain problems. It uses ANN simulation for crisp input data and fuzzy simulation for imprecise and uncertain input data. The solution quality is illustrated by two case studies from a multilayer ceramic capacitor manufacturing plant. The manufacturing lead times produced by the FANN–FS model turned out to be superior to conventional simulation models. This is the first study that introduces an intelligent and flexible approach for handling imprecision and nonlinearity of scheduling problems in flow shops with multiple processors.     

工艺规划柔性评价及其在生产调度中的应用

多工艺规划是提高制造系统运行柔性的有效方法。在规则调度中，系统运行柔性与各决策点所选的加工操作有关。定义了多工艺规划柔性概念；研究了多工艺规划间的相互关系及其对系统运行柔性的影响；讨论了多工艺规划柔性评价指标；提出一种操作优先级判据，实现了多工艺规划中不同操作的优先级排序，并用于规则调度。仿真实验表明，根据该判据，调度系统在每一决策点能优先选择使系统运行柔性较大的加工操作，从而提高系统的运行性能。     

Effects of Dispatching and Routeing Decisions on the Performance of a Flexible Manufacturing System

This paper is concerned with the effects of dispatching and routeing decisions on the performance of a flexible manufacturing system (FMS). Three routeing policies, no alternative routeings, alternative routeings dynamic, and alternativerouteings planned are first considered with four dispatching rules with infinite buffer capacity. However, in real-life, the size of the local buffers in FMSs may be limited by the size of the part types. Therefore, further experiments to investigate the above three routeing policies with the four dispatching rules with finite buffer capacity are also conducted in order to study the impact of limited buffer capacity on system performance. In addition, the effect of changing part mix ratios is discussed with both infinite and finite buffer capacity. The performance measures considered are makespan, average machine utilisation, average flow-time, and average delay at local input buffers. The simulation results indicate that for infinite buffer capacity, the alternative routeings planned policy, combined with the shortest total processing time dispatching rule, gives the best results for all the above performance measures. For finite buffer capacity, the alternative routeings dynamic policy gives the best results in three performance measures, except for average delay at local input buffers. Further, the effect of changing part mix ratios is not significant. ID="A1"Correspondance and offprint requests to: Dr F. T. S. Chan, Department of Industrial and Manufacturing Systems Engineering, The University of Hong Kong, Pokfulam Road, Hong Kong. E-mail: ftschan@hkucc.hku.hk     

带准备时间的柔性流水车间多序列有限缓冲区排产优化问题

针对带准备时间的柔性流水车间多序列有限缓冲区排产优化问题,提出一种改进的紧致遗传算法（Improved compactgenetic algorithm,ICGA）与局部指派规则结合的方法来解决该问题。全局优化过程采用改进的紧致遗传算法,为了克服紧致遗传算法（Compact genetic algorithm,CGA）易早熟收敛的问题,提出一种基于高斯映射的概率模型更新方式,在保持紧致遗传算法快速收敛特性的前提下,扩展了种群中个体的多样性,增强了算法进化活力。为减少生产阻塞和降低准备时间对排产过程的影响,设计了多种局部启发式规则来指导工件进出多序列有限缓冲区的分配和选择过程。采用某客车制造企业中的实例数据进行测试,测试结果表明,改进的紧致遗传算法与局部指派规则配合使用,能够有效解决带准备时间的柔性流水车间多序列有限缓冲区排产优化问题。     

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₃.