Learning dispatching rules using random forest in flexible job shop scheduling problems

In this paper, we address the flexible job-shop scheduling problem (FJSP) with release times for minimising the total weighted tardiness by learning dispatching rules from schedules. We propose a random-forest-based approach called Random Forest for Obtaining Rules for Scheduling (RANFORS) in order to extract dispatching rules from the best schedules. RANFORS consists of three phases: schedule generation, rule learning with data transformation, and rule improvement with discretisation. In the schedule generation phase, we present three solution approaches that are widely used to solve FJSPs. Based on the best schedules among them, the rule learning with data transformation phase converts them into training data with constructed attributes and generates a dispatching rule with inductive learning. Finally, the rule improvement with discretisation improves dispatching rules with a genetic algorithm by discretising continuous attributes and changing parameters for random forest with the aim of minimising the average total weighted tardiness. We conducted experiments to verify the performance of the proposed approach and the results showed that it outperforms the existing dispatching rules. Moreover, compared with the other decision-tree-based algorithms, the proposed algorithm is effective in terms of extracting scheduling insights from a set of rules.     

A multi-attribute dispatching rule for automated guided vehicle systems

This paper considers the dispatching problem associated with operations of automated guided vehicles (AGVs). A multi-attribute dispatching rule for dispatching of an AGV is developed and evaluated. The multi-attribute rule, using the additive weighting method, considers three system attributes concurrently: the remaining space in the outgoing buffer of a workstation, the distance between an idle AGV and a workstation with a job waiting for the vehicle to be serviced, and the remaining space in the input buffer of the destination workstation of a job. A neural network approach is used to obtain dynamically adjusting attribute weights based on the current status of the manufacturing system. Simulation analysis of a job shop is used to compare the multi-attribute dispatching rule with dynamically adjusting attribute weights to the same dispatching rule with fixed attribute weights and to several single attribute rules. Results show that the multi-attribute dispatching rule with the ability to adapt attribute weights to job shop operational conditions provides a better balance among the performance measures used in the study.     

The study of real time scheduling by an intelligent multi-controller approach

Earlier studies indicated that using multiple dispatching rules (MDRs) for the various zones in the system can enhance the production performance to a greater extent than using a single dispatching rule (SDR) over a given scheduling interval for all the machines in the system, since MDRs employ the multi-pass simulation approach for real-time scheduling (RTS). However, if a classical machine learning approach is used, an RTS knowledge base (KB) can be developed by using the appropriate MDRs strategy (this method is called an intelligent multi-controller in this paper) as obtained from training examples. The main disadvantage of using MDRs is that the classes (scheduling decision variables) to which training examples are assigned must be provided. Hence, developing an RTS KB using the intelligent multi-controller approach becomes an intolerably time-consuming task because MDRs for the next scheduling period must be determined. To address this issue, we proposed an intelligent multi-controller incorporating three main mechanisms: (1) simulation-based training example generation mechanism, (2) data pre-processing mechanism and (3) SOM-based real time MDRs selection mechanism. Under various performance criteria over a long period, the proposed approach yields better system performance than the machine learning-based RTS using the SDR approach and heuristic individual dispatching rules.     

Learning effective dispatching rules for batch processor scheduling

Batch processor scheduling, where machines can process multiple jobs simultaneously, is frequently harder than its unit-capacity counterpart because an effective scheduling procedure must not only decide how to group the individual jobs into batches, but also determine the sequence in which the batches are to be processed. We extend a previously developed genetic learning approach to automatically discover effective dispatching policies for several batch scheduling environments, and show that these rules yield good system performance. Computational results show the competitiveness of the learned rules with existing rules for different performance measures. The autonomous learning approach addresses a growing practical need for rapidly developing effective dispatching rules for these environments by automating the discovery of effective job dispatching procedures.     

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.     

A new paradigm for rule-based scheduling in the wafer probe centre

This paper addresses the scheduling problem in the wafer probe centre. The proposed approach is based on the dispatching rule, which is popularly used in the semiconductor manufacturing industry. Instead of designing new rules, this paper proposes a new paradigm to utilize these rules. The proposed paradigm formulates the dispatching process as a 2-D assignment problem with the consideration of information from multiple lots and multiple pieces of equipment in an integrated manner. Then, the dispatching decisions are made by maximizing the gains of multiple possible decisions simultaneously. Besides, we develop a genetic algorithm (GA) for generating good dispatching rules through combining multiple rules with linear weighted summation. The benefits of the proposed paradigm and GA are verified with a comprehensive simulation study on three due-date-based performance measures. The experimental results show that under the proposed paradigm, the dispatching rules and GA can perform much better than under the traditional paradigm.     

Dynamic scheduling system utilizing machine learning as a knowledge acquisition tool

Dynamic selection of scheduling rules during real operations has been recognized as a promising approach to the scheduling of the production line. For this strategy to work effectively, sufficient knowledge is required to enable prediction of which rule is the best to use under the current line status. In this paper, a new learning algorithm for acquiring such knowledge is proposed. In this algorithm, a binary decision tree is automatically generated using empirical data obtained by iterative production line simulations, and it decides in real time which rule to be used at decision points during the actual production operations. The configuration of the developed dynamic scheduling system and the learning algorithm are described in detail. Simulation results on its application to the dispatching problem are discussed with regard to its scheduling performance and learning capability.     

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.     

Simulation analysis of dispatching rules for an automated interbay material handling system in wafer fab

Here, the performance evaluation of a double-loop interbay automated material handling system (AMHS) in wafer fab was analysed by considering the effects of the dispatching rules. Discrete event simulation models based on SIMPLE++ were developed to implement the heuristic dispatching rules in such an AMHS system with a zone control scheme to avoid vehicle collision. The layout of an interbay system is a combination configuration in which the hallway contains double loops and the vehicles have double capacity. The results show that the dispatching rule has a significant impact on average transport time, waiting time, throughput and vehicle utilization. The combination of the shortest distance with nearest vehicle and the first encounter first served rule outperformed the other rules. Furthermore, the relationship between vehicle number and material flow rate by experimenting with a simulation model was investigated. The optimum combination of these two factors can be obtained by response surface methodology.     

A learning-based methodology for dynamic scheduling in distributed manufacturing systems

To enhance productivity in a distributed manufacturing system under hierarchical control, we develop a framework of dynamic scheduling scheme that explores routeing flexibility and handles uncertainties. We propose a learning-based methodology to extract scheduling knowledge for dispatching parts to machines. The proposed methodology includes three modules: discrete-event simulation, instance generation, and incremental induction. First, a sophisticated simulation module is developed to implement a dynamic scheduling scheme, to generate training examples, and to evaluate the methodology. Second, the search for training examples (good schedules) is successfully fulfilled by the genetic algorithm. Finally, we propose a tolerance-based learning algorithm that does not only acquire general scheduling rules from the training examples, but also adapts to any newly observed examples and thus facilitates knowledge modification. The experimental results show that the dynamic scheduling scheme significantly outperforms the static scheduling scheme with a single dispatching rule in a distributed manufacturing system.     

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.     

Using dispatching rules for job shop scheduling with due date-based objectives

This paper addresses the job shop-scheduling problem with due date-based objectives including the tardy rate, mean tardiness and maximum tardiness. The focused approach is the dispatching rules. Eighteen dispatching rules are selected from the literature, and their features and design concepts are discussed. Then a dispatching rule is proposed with the goal of achieving a good and balanced performance when more than one objective is concerned at the same time. First, three good design principles are recognized from the existing rules. Second, it introduces a due date extension procedure to solve a problem of negative allowance time. Third, a job candidate reduction mechanism is developed to make the rule computationally efficient. Lastly, a comprehensive simulation study is conducted with the 18 existing rules as the benchmarks. The experimental results verify the superiority of the proposed rule, especially on the tardy rate and mean tardiness.     

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.     

Input control and dispatching rules in a dynamic CONWIP flow-shop

The purpose of this paper is to study the input control and dispatching rules that might be used in a flow shop controlled by a constant work-in-process system (CONWIP) within a make-to-stock environment. The CONWIP system was originally conceived for a single card-count control and a FCFS dispatching rule, although in this paper it is shown that its performance can be increased by using other input controls as well as different dispatching rules.     

Heuristic dispatching rule to maximize TDD and IDD performance

Although mean flow time and tardiness have been used for a long time as indicators in both manufacturing plants and academic research on dispatching rules, according to Theory of Constraints (TOC), neither indicator properly measures deviation from production plans. TOC claims that using throughput dollar-day (TDD) and inventory dollar-day (IDD) can induce the factory to take appropriate actions for the organization as a whole, and that these can be applied to replace various key performance indices used by most factories. However, no one has studied dispatching rules based on TDD and IDD performance indicators. The study addresses two interesting issues. (1) If TDD and IDD are used as performance indicators, do those dispatching rules that yield a better performance in tardiness and mean flow time still yield satisfactory results in terms of TDD and IDD performance? (2) Does a dispatching rule exist to outperform the current dispatching rules in terms of TDD and IDD performance? First, a TDD/IDD-based heuristic dispatching rule is developed to answer these questions. Second, a computational experiment is performed, involving six simulation examples, to compare the proposed TDD/IDD-based heuristic-dispatching rule with the currently used dispatching rules. Five dispatching rules, shortest processing time, earliest due date, total profit, minimum slack and apparent tardiness cost, are adopted herein. The results demonstrate that the developed TDD/IDD-based heuristic dispatching rule is feasible and outperforms the selected dispatching rules in terms of TDD and IDD.     

A hybrid computer simulation-artificial neural network algorithm for optimisation of dispatching rule selection in stochastic job shop scheduling problems

Industrial systems are constantly subject to random events with inevitable uncertainties in production factors, especially in processing times. Due to this stochastic nature, selecting appropriate dispatching rules has become a major issue in practical problems. However, previous research implies that using one dispatching rule does not necessarily yield an optimal schedule. Therefore, a new algorithm is proposed based on computer simulation and artificial neural networks (ANNs) to select the optimal dispatching rule for each machine from a set of rules in order to minimise the makespan in stochastic job shop scheduling problems (SJSSPs). The algorithm contributes to the previous work on job shop scheduling in three significant ways: (1) to the best of our knowledge it is the first time that an approach based on computer simulation and ANNs is proposed to select dispatching rules; (2) non-identical dispatching rules are considered for machines under stochastic environment; and (3) the algorithm is capable of finding the optimal solution of SJSSPs since it evaluates all possible solutions. The performance of the proposed algorithm is compared with computer simulation methods by replicating comprehensive simulation experiments. Extensive computational results for job shops with five and six machines indicate the superiority of the new algorithm compared to previous studies in the literature.     

Simulation comparison of collaboration protocol-based testing models

This paper uses a stimulation modelling approach to investigate two collaboration protocols: timeout and frequent request collaboration protocols. The models presented here are very generic and can be adopted in general testing environments with a single tester shared by many types of jobs and with the repair process. This research presents different results from earlier studies, while addressing their misleading simplifying assumptions that are a common pitfall in practice. The two collaboration protocols are redefined based on the results. The timeout protocol improved system performance by collaborating with the SPT rule in the gamma repair time distributions with left biased shape. This collaboration is simple to implement and does not require the parameter estimation that is often a drawback of most heuristics for the combination of dispatching rules. The frequent service request (FSR) dispatching rule showed as good performance as the SPT rule with respect to overall mean flow time in this problem. Research is being continued to further investigate the properties of the timeout collaboration protocol with various factors.     

Heavy traffic analysis of a single vehicle loop in an automated storage and retrieval system

We consider an automated storage/retrieval system in which cargo moves between the storage/retrieval machines and the system entrance/exit stations through a single automated vehicle loop. Past studies indicated that the cargo waiting time in the loop is affected by the dispatching rules, which govern the sequence of the cargo to be handled. In this paper, we show that the loop configuration, which has received little research attention, also has a big impact on the cargo waiting time. When the first-come-first-served dispatching rule is used, we derive the relationship between the number of stations and the ratio of the average cargo retrieval time to the average cargo storage time. When the first-encountered-first-served dispatching rule is used, we show that even the arrangement of the input channel and the output channel of a station can have significant impact on the cargo waiting time. Furthermore, we derive a formula for the vehicle visit rate for each station under heavy traffic conditions. This formula helps to explain the phenomenon that the waiting times at different stations can be very different even when the loop is symmetrically designed and the cargo arrival rates to the stations are similar. In addition to analytical models, we use simulations to evaluate the performance of different loop configurations. Our research suggests that a substantial improvement can be achieved by making proper adjustments to the loop configuration.     

Due date assignment using artificial neural networks under different shop floor control strategies

Due date assignment (DDA) is the first important task in shop floor control. Due date-related performance is impacted by the quality of the DDA rules. Assigning order due dates and delivering the goods to the customer on time will enhance customer service and provide a competitive advantage. A new methodology for lead-time prediction, artificial neural network (ANN), is adopted to model new due date assignment rules. An ANN-based DDA rule, combined with simulation technology and statistical analysis, is presented. Whether or not the ANN-based DDA rule can outperform the conventional and Reg-based DDA rules taken from the literature is examined. The interactions between the DDA, order review/release (ORR), and dispatching rules significantly impact upon one another, and it is therefore very important to determine a suitable DDA rule for the various combinations of ORR and dispatching rules. From the simulation and statistical results, the ANN-based DDA rules perform better in due date prediction. The ANN-based DDA rules have a smaller tardiness rate than the other rules. ANN-based DDA rules have a better sensitivity and variance. Therefore, if system information is not difficult to obtain, the ANN-based DDA rule can perform a better due date prediction. This paper provides suggestions for DDA rules under various combinations of ORR and dispatching rules. ANN-Sep is suitable for most of these combinations, especially when ORR, workload regulation (WR) and two boundaries (TB), rules are adopted.     

Evaluation of the Shortest Processing Time Scheduling Rule with Truncation Process

This paper discusses the development of a scheduling rule and summarizes the results of the evaluation of its performance with respect to some tardiness related criteria. Studies done on job shop scheduling indicated that the simple dispatching rules which mostly perform well with respect to a criterion of performance may have undesirable results with respect to other criteria. In this paper, a scheduling rule with truncation process called SPT-T is introduced and studied. Simulation results showed that the shortcomings of simple dispatching rules are remedied by using the SPT-T scheduling rule.