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.     

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.     

On-line dispatching rules for vehicle-based internal transport systems

On-line vehicle dispatching rules are widely used in many facilities such as warehouses and manufacturing facilities to control vehicles’ movements. Single-attribute dispatching rules, which dispatch vehicles based on only one parameter, are usually used. However, multi-attribute dispatching rules prove to be better in general. In this paper, we study the impact of reassigning moving vehicles on some good dispatching rules, both single- and multi-attribute, in the literature. Results suggest that reassigning moving-to-park vehicles has a significant positive effect on reducing the average load waiting time. We evaluate the dispatching rules’ performance using the experimental design of a real-life case study. The performance criteria are: minimizing the average load waiting time, keeping the maximum load waiting time as short as possible and utilizing better vehicles. The results show that the combined dispatching rules which integrates multi-attribute dispatching and vehicle reassignment yields the best performance overall.     

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.     

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.     

Interaction between dispatching and next station selection rules in a dedicated flexible manufacturing system

The interaction between nine dispatching and four next station selection rules in a relatively large dedicated FMS is investigated. The FMS contains 16 workstations with local buffers, nine load/unload stations, and produces six different part types. A simulation model is used, and analysed as a steady-state model. Flowtime is taken as the main criterion. It is found that WINQ (select the station whose input buffer contains the smallest amount of work) dominates, performing significantly better than the other next station selection rules considered across all dispatching rules, with few significant differences between dispatching rules when combined with WINQ. SIO/TOT (select the job with the smallest ratio obtained by dividing the processing time of the imminent operation by the total processing time for the part) performs marginally better than the other dispatching rules, particularly SIO (select the job with the shortest imminent processing time). Reasons for when a next station selection rule is more important than a dispatching rule, and vice versa, are discussed.     

Regression-based due date assignment rules for improved assembly shop performance

Many simulation studies have evaluated sequencing rules and due date assignment methods for scheduling job shops. More recently researchers have studied multistage, or assembly, shops. Typically, due dates have been set by using a fixed multiple of the critical path length. This paper evaluates the effects on shop performance due to using a regression-based approach for setting due dates. The findings show that marked improvement in the performance of dispatching rules can occur when the proposed due date setting procedure is used.     

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.     

Capacity-constrained scheduling for a logic IC final test facility

A capacity-constrained scheduling using the concept of the theory of constraints for a semiconductor Logic IC final test operation is presented. The scheduling of the IC final test considers unrelated parallel machines with multiple constraint problems. A broad product mix, variable lot sizes and yields, long and variable set-up times, as well as limited test equipment capacity characterize the operations in this test facility. Discrete event simulation models based on e-M-Plant? are developed to implement the capacity-constrained scheduling algorithm. A comparison is also made with other rules, which are combinations of the rules such as first come first serve and earliest due date for the order scheduling, and the rules such as minimum set-up time, shortest processing time and shortest set-up time plus processing time for the dispatching test equipment. The simulation results show that the proposed capacity-constrained scheduling outperforms other rules for the committed volume performance in many different operational conditions. Directions for future research are also presented.     

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.     

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.     

API-based two-dimensional dispatching decision-making approach for semiconductor wafer fabrication with operation due date–related objectives

This paper presents an adjacent pairwise interchanges (API)-based two-dimensional dispatching decision-making approach for semiconductor wafer fabrication with operation due date-related objectives. Each time when a machine becomes idle, the proposed dispatcher chooses a target processing job from the competing jobs and assigns it a start time. Giving the operation due date information of each competing job, we formulate this dispatcher as the mean absolute deviation problem to keep the jobs finished around their operation due dates in a proactive way. Dominance properties of this problem are established using proof by APIs. Then, a heuristic comprised of job selection within candidate set, movement of job cluster and local search is designed to solve this problem more efficiently. Numerical experiments validate the efficiency of the proposed heuristic in a single-machine environment as well as in a simulated wafer fab abstracted from practice. In comparison with four most referenced due date-related dispatching rules, the simulation study reveals the benefits brought by the two-dimensional dispatching decision with different due date tightness taken into account.     

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.     

On the beat of the drum: improving the flow shop performance of the Drum–Buffer–Rope scheduling mechanism

One of the main elements of the theory of constraints is its Drum–Buffer–Rope (DBR) scheduling (or release) mechanism that controls the release of jobs to the system. Jobs are not released directly to the shop floor – they are withheld in a backlog and released in accordance with the output rate of the bottleneck (i.e. the drum). The sequence in which jobs are considered for release from the backlog is determined by the schedule of the drum, which also determines in which order jobs are processed or dispatched on the shop floor. In the DBR literature, the focus is on the urgency of jobs and the same procedure is used both for backlog sequencing and dispatching. In this study, we explore the potential of using different combinations of rules for sequencing and dispatching to improve DBR performance. Based on controlled simulation experiments in a pure and general flow shop we demonstrate that, although the original procedure works well in a pure flow shop, it becomes dysfunctional in a general flow shop where job routings vary. Performance can be significantly enhanced by switching from a focus on urgency to a focus on the shortest bottleneck processing time during periods of high load.     

Family based dispatching with batch availability

Family based dispatching rules seek to lower set-up frequencies by grouping (batching) similar types of jobs for joint processing. Hence shop flow times may be improved, as less time is spent on set-ups. Motivated by an industrial project we study the control of machines with batch availability, i.e. all the jobs of the same batch become available for processing and leave the machine together. So far the literature seems to have neglected this type of shop by restricting its focus on machines with item availability, i.e. assuming machine operations concern single jobs. We address this gap by proposing extensions to existing family based dispatching rules. Extended rules are tested by an extensive simulation study. Best performance is found for non-exhaustive rules, which allow for alternative choices of batch size. Performance gains are highest for low set-up to run-time ratios and/or high workloads.     

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.     

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.     

Integrating load-based order release and priority dispatching

Workload control (WLC) is a well-established production control concept for job shops that put primary emphasis on load-based order release. Recent advances in load-based order release research have led to an improved delivery performance at reduced shop floor workloads. But although order release is the primary focus of WLC research, it must be coupled with priority dispatching on the shop floor if order progress is to be regulated. Prior simulation research suggests that load-based order release methods should only be coupled with simple dispatching rules because other, more powerful rules can conflict with the functioning of the release method. Yet, recent empirical research suggests that powerful priority dispatching rules – such as due date-oriented dispatching rules – are in fact needed for a high level of delivery performance to be obtained in practice. This paper focuses on overcoming the conflict between order release and dispatching, so load-based order release can be combined with due date-oriented dispatching. Preliminary analysis reveals that part of the conflict is because existing due date-oriented dispatching rules overcompensate for schedule deviations that occur when orders are either released earlier or later than planned. Two alternative new dispatching rules based on an improved method of determining operation due dates are then developed to better account for schedule deviations and overcome the conflict with load-based order release. Further improvements in delivery performance are obtained, while the large workload reductions achieved by recently developed load-based order release methods are retained.     

泛在电力物联网实施策略研究

建设泛在电力物联网是实现能源转型目标的必要手段。从电力系统发展历程和面临的问题出发,论述了泛在电力物联网的意义,提出了实施策略和可能遇到的问题。为实现能源转型,风电光电等可再生能源装机容量不断增加。这些能源的随机性给电力系统的功率平衡造成巨大压力,有时不得不弃掉一部分风电光电。为了维持电力系统的稳定运行、提高风电光电的利用率,必须对可控负荷和分散式发电进行控制。因此,需要用互联网连接可控负荷和分散式发电,形成泛在电力物联网。常规发电厂、大型风电场、光电站等已经和电力系统连接了,调度可以直接控制。因此,泛在电力物联网主要任务是连接负荷和分散式发电,尤其是可控负荷。电动汽车是可控负荷中最容易实现可控的,其次是热水器、电热锅炉和空调等。利用泛在电力物联网,协同控制风电光电、可控负荷、分散式发电等,可以提高风电光电利用率,实现能源转型目标。     

Effects of flexibility and scheduling decisions on the performance of an FMS: simulation modelling and analysis

This paper focuses on a simulation-based experimental study of the effects of routing flexibility, sequencing flexibility, and part sequencing rules on the performance of a typical FMS. Three routing flexibility levels, five sequencing flexibility levels, and four scheduling rules for part sequencing decision are considered for detailed investigation. The system work load characterised by the mean interarrival time of parts has been set at different levels. 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. Multiple regression-based metamodels have been developed using the simulation results. The analyses of results reveal that deterioration in system performance can be minimised substantially by incorporating either routing flexibility or sequencing flexibility or both. However, the benefits of either of these flexibilities diminish at higher flexibility levels. When flexibility exists, part sequencing rules such as the earliest due date and earliest operation due date provide a better performance for all the measures.