Selection of dispatching rules on multiple dispatching decision points in real-time scheduling of a semiconductor wafer fabrication system

Semiconductor wafer fabrication involves one of the most complex manufacturing processes ever used. To control such complex systems, it is a challenge to determine appropriate dispatching strategies under various system conditions. Dispatching strategies are classified into two categories: a vehicle-initiated dispatching policy and a machine-initiated dispatching policy. Both policies are important to improve the system performance, especially for the real time control of the system. However, there has been little research focusing on combining them under various situations for the semiconductor manufacturing system. In addition, it is shown that no single dispatching strategy consistently dominates others in all situations. Therefore, the goal of this study is to develop a scheduler for selection of dispatching rules for dispatching decision variables in order to obtain the desired performance measures given by a user for each production interval. For the proposed methodology, simulation and competitive neural network approaches are used. The results of the study indicate that applying our methodology to obtaining a dispatching strategy is an effective method considering the complexity of semiconductor wafer fabrication systems.     

A deep learning approach for the dynamic dispatching of unreliable machines in re-entrant production systems

This research combines deep neural network (DNN) and Markov decision processes (MDP) for the dynamic dispatching of re-entrant production systems. In re-entrant production systems, jobs enter the same workstation multiple times and dynamic dispatching oftentimes aims to dynamically assign different priorities to various job groups to minimise weighted cycle time or maximise throughput. MDP is an effective tool for dynamic production control, but it suffers from two major challenges in dynamic control problems. First, the curse of dimensionality limits the computational performance of solving large MDP problems. Second, a different model should be built and solved after system configuration is changed. DNN is used to overcome both challenges by learning directly from optimal dispatching policies generated by MDP. Results suggest that a properly trained DNN model can instantly generate near-optimal dynamic control policies for large problems. The quality of the DNN solution is compared with the optimal dynamic control policies through the standard K-fold cross-validation test and discrete event simulation. On average, the performance of the DNN policy is within 2% of optimal in both tests. The proposed artificial intelligence algorithm illustrates the potential of machine learning methods in manufacturing applications.     

Dynamic production control with dispatching within pre-emption

This paper deals with a production control problem for the testing and rework cell in a dynamic and stochastic computer integrated manufacturing (CIM) system. This research first defines dispatching within pre-emption for an extended form of pre-emption. A dynamic controller called competitive decision selector (CDS) is then modified and extended as CDSplus to handle three different production control decisions; dispatching, pre-emption, and dispatching within pre-emption. It observes the status of the system and jobs at every decision point, and makes its three different decisions in real time. The CDSplus dynamic control shows better performance than static control rules with respect to the number of tardy jobs.     

An integrated system for controlling shop loading and work flow

Effective management of loading and work flow is becoming increasingly important in manufacturing. However, research has not addressed the associated dynamic internal performance issues as effectively as possible. This paper investigates an integrated approach to input and shop floor control under conditions of controlled delivery performance. Several new mechanisms are developed, including a method of dynamically adjusting buffer sizes based on system loads. Lead time and several measures related to the level and distribution of work in the system are used to evaluate performance. Results show that performance can be improved by taking loading and work flow issues into consideration when input release, dispatching and buffer space decisions are being made.     

Statistical analysis of factors influencing the performance of the timeout-based testing model

Time-out collaboration protocol is a mechanism to maximize system performance, with a service discipline (or a dispatching rule) collaborated, by disabling the access of a job to the resource when the job keeps the resource idle for too long and then by giving one of the other waiting jobs the access to the resource. This paper formally defines a generic testing model with a single tester shared by multiple types of jobs and with the repair process. This research performs statistical analysis of the timeout collaboration protocol by considering several factors simultaneously and identifies two key factors that affect the performance of different timeout thresholds in the testing model. It is shown that two extreme timeout threshold values ( T 0 = 0 and X ) outperform intermediate values (0 < T 0 <; X ) with respect to overall mean flow time. This research provides insights into applying the timeout mechanism that originated from communication problems to production systems.     

Co-evolutionary genetic algorithm for multi-machine scheduling: Coping with high performance variability

Optimizing dispatching policy in a networked, multi-machine system is a formidable task for both field experts and operations researchers due to the problem's stochastic and combinatorial nature. This paper proposes an innovative variation of co-evolutionary genetic algorithm (CGA) for acquiring the adaptive scheduling strategies in a complex multi-machine system. The task is to assign each machine an appropriate dispatching rule that is harmonious with the rules used in neighbouring machines. An ordinary co-evolutionary algorithm would not be successful due to the high variability (i.e. noisy causality) of system performance and the ripple effects among neighbouring populations. The computing time for large enough populations to avoid premature convergence would be prohibitive. We introduced the notion of derivative contribution feedback (DCF), in which an individual rule for a machine takes responsibility for the first-order change of the overall system performance according to its participation in decisions. The DCFCGA effectively suppressed premature convergence and produced dispatching rules for spatial adaptation that outperformed other heuristics. The required time for knowledge acquisition was also favourably compared with an efficient statistical method. The DCF-CGA method can be utilized in a wide variety of genetic algorithm application problems that have similar characteristics and difficulties.     

The infrastructure of the timed EOPNs-based multiple-objective real-time scheduling system for 300 mm wafer fab

Modern semiconductor wafer fabrication systems are changing from 200?mm to 300?mm wafer processing, and with the dual promises of more chips per wafer and economy of scale, leading semiconductor manufacturers are attracted to developing and implementing 300?mm wafer fabs. However, in today's dynamic and competitive global market, a successful semiconductor manufacturer has to excel in multiple performance indices, such as manufacturing cycle time and on-time delivery, and simultaneously optimize these objectives to reach the best-compromised system achievement. To cope with this challenge, in this paper, the infrastructure of a timed EOPNs-based multiple-objective real-time scheduling system (MRSS) is proposed to tackle complex 300?mm wafer fabs. Four specific performance objectives pursued by contemporary semiconductor manufacturers are integrated into a priority-ranking algorithm, which can serve as the initial scheduling guidance, and then all wafer lots will be dynamically dispatched by the real-time state-dependent dispatching system. This dispatching control system is timed EOPN-based and adopts a heterarchical organization that leads to a better real-time performance and adaptability. As the foundation of real-time schedule, the timed EOPNs modelling approach is expounded in detail, and the prototype of the MRSS simulation system is also provided.     

Dynamic adjustment of dispatching rule parameters in flow shops with sequence-dependent set-up times

Decentralised scheduling with dispatching rules is applied in many fields of production and logistics, especially in highly complex manufacturing systems. Since dispatching rules are restricted to their local information horizon, there is no rule that outperforms other rules across various objectives, scenarios and system conditions. In this paper, we present an approach to dynamically adjust the parameters of a dispatching rule depending on the current system conditions. The influence of different parameter settings of the chosen rule on the system performance is estimated by a machine learning method, whose learning data is generated by preliminary simulation runs. Using a dynamic flow shop scenario with sequence-dependent set-up times, we demonstrate that our approach is capable of significantly reducing the mean tardiness of jobs.     

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.     

Launching and dispatching strategies for multi-criteria control of closed manufacturing systems with flexible routeing capability

In this paper, we study the problems of launching and dispatching of parts in closed manufacturing systems with flexible routeing. For the manufacturing systems being operated against multiple performance criteria, we postulate that controlling different aspects of the operational control strategy to meet one single performance criterion would improve overall system performance. It is suggested that to achieve production rates, launching rules be utilized and to affect flowtime, dispatching rules be manipulated. Also, for measurement of routeing flexibility, an entropic measure of flexibility is refined. The entropy-based rule is then compared with the dispatching rules commonly used in the industry. Control strategies are developed for a test system and it is shown that a hierarchical control strategy works best when multiple performance criteria are of interest.     

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.     

Capacitated dynamic lotsizing heuristics for serial systems

This paper deals with multi-item capacitated lotsizing in a serial production environment under dynamic demand conditions. The primary objective of this research is to investigate the performance of simple level-by-level heuristics. A problem classification is proposed to distinguish between easy problems and harder ones for which no simple heuristics can be developed. It is shown how simple algorithms can be constructed for the easier problems using a level-by-level approach. These heuristics are the first of their kind for this problem. They are compared with the optimal solution for a set of test problems. The results show that for some problem classes strategies which are frequently used in practice may result in rather poor schedules.     

Scheduling dynamic block assembly in shipbuilding through hybrid simulation and spatial optimisation

Scheduling block assembly in shipyard production poses great difficulties regarding the accurate prediction of the required spatial resource and effective production control for achieving managerial objectives due to the dynamic spatial layout and the stochastic nature of the production system. In this study, this dynamic space-constrained problem is viewed as two sequential decisions, namely rule-based dispatching and a static spatial configuration. A novel hybrid planning method is developed to employ discrete-event simulation as look-ahead scheduling to evaluate the system performance under various control policies. To rationalise block placement and improve long-term area utilisation, a discrete spatial optimisation problem is formulated and solved using an enumeration-based search algorithm, followed by the application of a series of heuristic positioning strategies. By imitation of the dynamic dispatching and spatial operation, a statistical analysis of the resultant performance can be conducted to select the best-performing priority rules. A case study with an experimental investigation is performed for a local shipyard to demonstrate the applicability of the proposed method.     

Using genetic algorithms (GA) and a coloured timed Petri net (CTPN) for modelling the optimization-based schedule generator of a generic production scheduling system

The semiconductor manufacturing industry is one of the most complicated manufacturing systems in the world. Considering its complex problem nature, such as the unrelated parallel machine environment, dynamic job arrival, non-pre-emption, inseparable sequence-dependent set-up time, multiple-resource requirements, general precedence constraint, and job recirculation, this study proposed the optimization-based schedule generator (OptSG) for solving the generalized scheduling problems arising from the semiconductor manufacturing environment. The separation of the problem structure and problem configuration in OptSG contributes to the structural independence, making OptSG robust and convenient in analysis and problem-solving in real settings with changing properties. Meanwhile, an MILP model was proposed as a benchmark to estimate the validity of OptSG. Inseparable sequence-dependent set-up time and multiple-resource requirements that have not been addressed simultaneously in the literature were considered in this model. By using different evaluation criteria, including makespan, total completion time and maximum tardiness, experiments were conducted to compare the solutions of the MILP model, OptSG and dispatching rule-based heuristics (DRBH). The results validated the solution quality of OptSG.     

A methodology for planning and controlling workload in a job-shop: a four-way decision-making problem

There has been extensive research on workload and input–output control with the objective of improving manufacturing operations in job-shops. In this paper, a multiple decision-making scheme is proposed to plan and control operations in a general job-shop, and to improve delivery and workload related performance measures. The job-shop characteristics reinforce the need for designing a global system that controls both the jobs entering (order acceptance, due date setting and job release) and the work-in-process (dispatching), leading to an improvement of operational measures. Previous research has concentrated on scheduling a set of orders through the shop floor, according to some decision mechanism, in order to optimise some measure of performance (usually total lead time). This means that, since only a part of the decision-making system is being optimised, the resulting decision may be sub-optimal. In this paper it is shown that the performance of the different decision rules changes when they are considered simultaneously. Hence, a higher level approach, where the four decisions (order acceptance, due date setting, job release and dispatching) are considered at the same time, should be adopted to improve job-shop operational performance.     

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.     

Improving the applicability of workload control (WLC): the influence of sequence-dependent set-up times on workload controlled job shops

Simulation has demonstrated that the workload control (WLC) concept can improve performance in job shops, but positive empirical results are scarce. A key reason for this is that the concept has not been developed to handle a number of practical considerations, including sequence-dependent set-up times. This paper investigates the influence of sequence-dependent set-up times on the performance of a workload-controlled job shop. It introduces new set-up-oriented dispatching rules and assesses the performance impact of controlled order release. Simulation results demonstrate that combining an effective WLC order release rule with an appropriate dispatching rule improves performance over use of a dispatching rule in isolation when set-up times are sequence dependent. The findings improve our understanding of how this key implementation challenge can be overcome. Future research should investigate whether the results hold if set-up time parameters are dynamic and set-up times are not evenly distributed across resources.     

Dynamic state-dependent dispatching for wafer fabrication

A dynamic state-dependent dispatching (DSDD) heuristic for a wafer fabrication plant is presented. The DSDD heuristic dynamically uses different dispatching rules according to the state of a production system. Rather than developing new rules, the DSDD heuristic combines and modifies existing rules. This heuristic first classifies workstations into dynamic bottlenecks and non-dynamic bottlenecks. Dynamic bottleneck workstations apply a revised two-boundary dispatching rule when their queue length exceeds the average obtained from simulation using constant lot-release policy and first-in, first-out dispatching rule. Otherwise, the shortest expected processing time until next visit dispatching rule is used. A revised FGCA (FGCA+) dispatching rule is used for all non-dynamic bottlenecks workstations. Simulation results demonstrate that the DSDD heuristic obtains the best performance among the compared six dispatching rules in terms of average and standard deviation of cycle time and work-in-process.     

Data-mining-based dynamic dispatching rule selection mechanism for shop floor control systems using a support vector machine approach

The purpose of this paper is to develop a data-mining-based dynamic dispatching rule selection mechanism for a shop floor control system to make real-time scheduling decisions. In data mining processes, data transformations (including data normalisation and feature selection) and data mining algorithms greatly influence the predictive accuracy of data mining tasks. Here, the z-scores data normalisation mechanism and genetic-algorithm-based feature selection mechanism are used for data transformation tasks, then support vector machines (SVMs) is applied for the dynamic dispatching rule selection classifier. The simulation experiments demonstrate that the proposed data-mining-based approach is more generalisable than approaches that do not employ a data-mining-based approach, in terms of accurately assigning the best dispatching strategy for the next scheduling period. Moreover, the proposed SVM classifier using the data-mining-based approach yields a better system performance than obtained with a classical SVM-based dynamic dispatching rule selection mechanism and heuristic individual dispatching rules under various performance criteria over a long period.     

Aligning workload control theory and practice: lot splitting and operation overlapping issues

This paper addresses the problem of lot splitting in the context of workload control (WLC). Past studies on WLC assumed that jobs released to the shop floor proceed through the different stages of processing without being split. However, in practice, large jobs are often split into smaller transfer sublots so that they can move more quickly and independently through the production process and allow operations overlapping relating to the same job. This paper assesses the performance of different lot splitting policies for job release and dispatching strategies under lot splitting. A new dispatching rule was designed to specifically take advantage of lot splitting and operations overlapping in the context of WLC. Discrete-event simulation is used to assess system performance in relation to the ability to provide shorter delivery times and on time deliveries. Results highlight the importance of releasing the sublots of the same job together and demonstrate that combining an effective lot splitting policy with an appropriate dispatching rule can enhance the performance of production systems.