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.     

Setup-oriented dispatching rules – a survey

This paper provides a survey of dispatching rules that explicitly take into account setup times in their decision making. Rules are classified into the categories of purely setup-oriented, composite and family-based rules, and the most promising rules from the three categories are identified from the literature. These rules are then compared empirically on various job shop problems with sequence-dependent setup times for their performance regarding mean setup time, mean flow time, mean tardiness and proportion of tardy jobs. The setup times are modelled using setup time matrices, and five different types of matrices are applied to assess the influence of this factor on the relative performance of a setup-oriented dispatching rule. Experimental results indicate that the choice of the best rule is often dependent on the setup time matrix structure. While good family-based rules exist for reducing the mean setup time and mean flow time, they are clearly outperformed by effective composite rules for due date-related criteria. Moreover, the better rules all seem to rely on queue information rather than only job attributes.     

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.     

Performance of an ant colony optimisation algorithm in dynamic job shop scheduling problems

The goal of the current study is to identify appropriate application domains of Ant Colony Optimisation (ACO) in the area of dynamic job shop scheduling problem. The algorithm is tested in a shop floor scenario with three levels of machine utilisations, three different processing time distributions, and three different performance measures for intermediate scheduling problems. The steady-state performances of ACO in terms of mean flow time, mean tardiness, total throughput on different experimental environments are compared with those from dispatching rules including first-in-first-out, shortest processing time, and minimum slack time. Two series of experiments are carried out to identify the best ACO strategy and the best performing dispatching rule. Those two approaches are thereafter compared with different variations of processing times. The experimental results show that ACO outperforms other approaches when the machine utilisation or the variation of processing times is not high.     

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.     

Modelling and analysis of wafer fabrication scheduling via generalized stochastic Petri net and simulated annealing

Some of the important characteristics of the semiconductor wafer fabrication factories are re-entrant process flows, a dynamic and uncertain environment, stringent production control requirements, etc. that pose a major challenge to the scheduling decisions in integrated circuit wafer fabrication process. Keeping in view the high capital investment and quick response to the market changes, it is essential for the integrated circuit fabrication process to exercise effective control on its production operations so that production resources can be employed in a flexible and efficient manner. The present research has focussed on the development of a generalized stochastic Petri net model that faithfully captures dynamic behaviours such as re-entrant processing, machine failures, loading and unloading, etc., pertaining to wafer fabrication. A simulated annealing-based scheduling strategy using mean cycle time and tardiness as performance measures was also developed to obtain an efficient and robust schedule for a known hard problem. Analysis of variance was applied to examine the interaction effects of various scheduling rules and to identify the main as well as the interaction effects of dispatching rules, dispatching rules and set-up rules, and set-up rules and batching rules. Paired t-tests were applied to assess the performance of rule combinations for lot and batch scheduling. The proposed simulated annealing-based solution methodology was tested on a well-known data set adopted from the literature and its performance reveals that simulated annealing-based scheduling rules work better than existing rules in terms of the two performance measures mean cycle time and tardiness.     

New dispatching rules for shop scheduling: A step forward

This paper provides a set of new dispatching rules for the minimization of various performance measures such as mean, maximum and variance of flow time and tardiness in dynamic shops. A static rule which minimizes the number of tardy jobs is also proposed. To evaluate these proposed rules, their relative performance is analysed in open job shops and reported in comparison with the standard benchmark rules such as the SPT (shortest process time) and EDD (earliest due-date), popular rules like ATC (apparent tardiness cost) and MOD (modified operational due-date), and the best performing rules in current literature such as RR, PT + WINQ, PT + WINQ + SL and AT-RPT. Thereafter, a comparative analysis of the relative performance of these rules is carried out in job shops (with no machine revisitation of jobs) and flow shops (with missing operations on jobs) in dynamic environments. Based on the simulation study and analysis of results in different manufacturing environments viz. job shops and flow shops, observations and conclusions are made, highlighting some interesting aspects about the effect of routeing on the individual performance of rules.     

A comparative study of priority dispatching rules in a hybrid assembly/job shop

This paper reports on research conducted on the use of priority dispatching rules in a hybrid assembly/job shop which manufactures both single-component and multiple-component products. A simulation model was constructed and a large stale experiment performed. Statistical analysis of the simulation results indicated significant impact of both the priority rules tested, and the product-mix considered on shop performance.

Among the 12 priority rules tested, the SPT (shortest processing time) rule and the ASMF-SPT (assembly jobs first with SPT as tie-breaker) rule performed very well with respect to measures like lateness, flow time, tardiness, staging time, and percent of jobs tardy. These findings lead to further investigation of a combined priority rule, MIXED, which implements the ASMF-SPT rule at all machine centres that process components of assembly jobs, and the SPT rule at the remaining machine centres which process non-component jobs. The additional research results yielded evidence that the MIXED rule can reduce the staging time of the SPT rule, and yielded betrer results than the ASMF-SPT rule with regard to other performance measures.

The most interesting finding, however, was the small variation in flow time distribution resulting from use of the MIXED rule when there were more assembly jobs. In an MRP environment, it is especially desirable to have a priority dispatching rule resulting in minimum variation in individual flow times which allows the replenishment lead times to be estimated with greater accuracy.     

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.     

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.     

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.     

An efficient priority rule for scheduling job shops to minimize mean tardiness

The ability to respond quickly to customer demands is a key factor in successfully competing in today's globally competitive markets. Thus, meeting due dates could be the most important goal of scheduling in many manufacturing and service industries. Meeting due dates can naturally be translated into minimizing job tardiness. In this paper we present a priority rule for dynamic job shop scheduling that minimizes mean job tardiness. The rule is developed based on the characteristics of existing dispatching rules. With job due dates set by the generalized total work content rule, the computational results of simulation experiments show that the proposed dispatching rule consistently, and often, significantly outperforms a number of well-known priority rules in the literature. The proposed rule is also robust being the best or near-best rule for reducing the mean flowtime, for all the shop load levels and due date tightness factors tested.     

The choice of dispatching rules in a shop using internally set due-dates with quoted leadtime and tardiness costs

Setting due-dates poses a dilemma for the manufacturing manager. If the duedates extend the quoted leadtimes to ensure delivery reliability, the shop incurs the customer's ire for having such long leadtimes. If they shorten its quoted leadtimes, it faces the prospect of incurring the customer's wrath for poor delivery reliability. This study examines the trade-offs involved in choosing a dispatching rule in a shop that can set due-dates subject to penalties for the length of the quoted leadtime and tardiness. The results of this study indicate that the shortest processing time rule works well for modest tardiness penalties. As the penalty for tardiness increases, dispatching rules such as first-come, first-serve and first-in-system first-serve, work well. The earliest due-date rule generally does not perform well in this study because of the interaction between the earliest duedate rule and the parameters of the due-date assignment rule. The paper concludes with the discussion of possible extensions of this work.     

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.     

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.     

The impact of priority rule combinations on lateness and tardiness

Several recent studies have explored the concurrent deployment of different priority rules at different processing stages of a manufacturing system. This study investigates the same issue by combining three popular simple priority rules with a combinatorial rule. In a three-stage flow shop, these rules are combined into 64 combination schemes and their performance compared under two shop load levels with two due date setting methods. The performance criteria considered are: mean lateness; mean tardiness; maximum tardiness; and per cent of tardy jobs. The results indicate that the rule combinations are a better strategy than their pure forms when various performance measures are jointly evaluated. Particularly, selected combinations of the Modified Shortest Processing Time, Shortest Processing Time, and the Earliest Due Date rules appear to be very effective. While the extent of shop load level shows little impact on the relative performance of the schemes, the endogenous method of due date setting consistently yields better results than the exogenous method.     

A comparative analysis of the COVERT job sequencing rule using various shop performance measures

The COVERT job shop dispatching rule was tested extensively twenty years ago with impressive results, however, since then it has been included in only one comparative analysis with other sequencing rules, and, reported instances of its application have been infrequent. In this paper, the COVERT rule is examined in detail relative to its applicability, its sensitivity to various operating parameters and performance measures, and its performance compared to several other sequencing rules including truncated SPT rules, dynamic slack rules and modified duedate rules. The performance of COVERT is examined for a variety of tardiness measures. The examination is conducted within the context of a simulation model of a machine-constrained job shop with serial jobs and random routings. The results indicate that COVERT performs well as a sequencing rule and in most instances was superior to the other sequencing rules tested both directly and across varying degrees of due-date tightness.     

An adaptive scheduling algorithm for a parallel machine problem with rework processes

The development of a scheduling methodology for a parallel machine problem with rework processes is presented in this paper. The problem is to make a schedule for parallel machines with rework probabilities, due-dates, and sequence dependent setup times. Two heuristics are developed based on a dispatching algorithm and problem-space-based search method. In order to evaluate the efficacy of the proposed algorithms, six performance indicators are considered: total tardiness, maximum lateness, mean flow-time, mean lateness, the number of tardy jobs, and the number of reworks. This paper shows how these algorithms can adaptively capture the characteristics of manufacturing facilities for enhancing the performance under changing production environments. Extensive experimental results show that the proposed algorithms give very efficient performance in terms of computational time and each objective value.     

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.     

Throughput/inventory dollar-days: TOC-based measures for supply chain collaboration

As the semiconductor industry moves away from vertical integration, performance measures play an increasingly important role to ensure effective collaboration. This paper demonstrates that the theory of constraints (TOC)-based measures, Throughput and Inventory Dollar-Days (T/IDD), induce autonomous supply chain (SC) links to function as a synergistic whole and thereby, improve the performance of the whole SC network significantly. We model an SC network of a well-known TOC case study using discrete event simulation and discuss managerial implications of these measures via a set of scenarios. The scenarios explain how these measures – without sharing sensitive financial data – allow members of an SC network to monitor both the effectiveness (TDD) and efficiency (IDD) of SC members and lead them to create win-win solutions following well-known TOC-based planning and control concepts. We conclude this paper by discussing some limitations of the proposed research and provide directions for future theoretical research.