Dispatching rules for scheduling in assembly jobshops - Part 1

Research on jobshop scheduling has tended to concentrate on the development of dispatching rules for jobs that are independent, i.e. single-component jobs. However, in real-life situations, many jobs involve assembly operations that require scheduling of multiple components through the jobshop where both serial and parallel operations take place. In this two-part paper, we consider the problem of scheduling in assembly jobshops, i.e. jobshops that manufacture multi-level assembly jobs. The development of new and efficient dispatching rules with a view to address various measures of performance related to flowtime and staging delay of jobs is first undertaken. A new concept, called 'operation synchronization date' is introduced and made use of in the new dispatching rules. The best existing dispatching rules and the proposed dispatching rules are relatively evaluated by an exhaustive simulation study. The results indicate that the proposed rules emerge to be superior to the existing ones for most measures of performance.     

An investigation of cooperative dispatching for minimising mean flowtime in a finite-buffer-capacity dynamic flowshop

Scheduling in a dynamic flowshop that receives jobs at random and unforeseen points in time has traditionally been done by using dispatching rules. This study compares the performances of leading dispatching rules with a cooperative dispatching approach, for the objective of minimising mean flowtime in a flowshop, in which the buffers that hold in-process jobs between machines have finite capacities. Cooperative dispatching employs a consultative and consensus-seeking methodology for deciding which job to dispatch next on a machine. Computational experiments using randomly generated test problems for three different utilisation (congestion) levels are carried out for 5- and 10-machine flowshops, under a wide range of buffer capacities. The results highlight the sensitivity of some of the popular dispatching rules to buffer size. In contrast, cooperative dispatching emerges as a robust method that performs consistently well across the range of buffer sizes and machine utilisations tested. The reductions in mean flowtime obtained by cooperative dispatching, in comparison to the other dispatching rules, are particularly large in flowshops that operate with very tight buffer capacities and elevated levels of congestion     

Dispatching rules for scheduling in assembly jobshops - Part 2

In this part of the paper, we present the development and evaluation of dispatching rules for scheduling in jobshops manufacturing multi-level assembly jobs with the performance measures reated to tardiness. We present a new definition of 'operation due date' in the context of assembly jobs and use it in the development of dispatching rules. A simulation study is carried out to evaluate the performances of the existing and the proposed dispatching rules with respect to different measures of tardiness. We also measure their performances with respect to different measures of flowtime and staging delays. The results of the study indicate that the proposed rules perform better than the existing rules.     

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.     

Satisfying due-dates in a job shop with sequence-dependent family set-ups

This paper addresses job shop scheduling with sequence dependent family set-ups. Based on a simple, single-machine dynamic scheduling problem, state dependent scheduling rules for the single machine problem are developed and tested using Markov Decision Processes. Then, a generalized scheduling policy for the job shop problem is established based on a characterization of the optimal policy. The policy is combined with a 'forecasting' mechanism to utilize global shop floor information for local dispatching decisions. Computational results show that performance is significantly better than that of existing alternative policies.     

Dynamic job shop scheduling using variable neighbourhood search

In this paper a scheduling method based on variable neighbourhood search (VNS) is introduced to address a dynamic job shop scheduling problem that considers random job arrivals and machine breakdowns. To deal with the dynamic nature of the problem, an event-driven policy is selected. To enhance the efficiency and effectiveness of the scheduling method, an artificial neural network with a back propagation error learning algorithm is used to update parameters of the VNS at any rescheduling point according to the problem condition. The proposed method is compared with some common dispatching rules that have been widely used in the literature for the dynamic job shop scheduling problem. Results illustrate the high efficiency and effectiveness of the proposed method in a variety of shop floor conditions.     

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.     

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.     

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.     

Family-based scheduling of shops with functional layouts

Simulation studies of job shop scheduling have typically assumed that either setup times are zero (subsumed within the processing time), or that every part has such a unique setup that no setup advantages can be gained by better scheduling policies. These studies also assume that the shop has exactly one copy of every machine. Some researchers have proposed heuristics that explicitly consider setup times and parallel machines in the context of a one stage shop with static arrivals. In contrast, family-based scheduling centred around setup time reduction has been credited with achieving economic savings in batch production industries where GT is employed. We motivate this study by the case of an existing realworld semi-conductor testing facility that has family setups, parallel machines and dynamic job arrival. Using this setting, we investigate whether benefits can still be obtained by using a family-based scheduling philosophy in those environments which do not permit the physical creation of cellular layouts due to the presence of process related or other constraints. We propose and evaluate two new dispatching procedures in a functional job shop that is modelled after the semiconductor testing facility. Results show that a family-based scheduling philosophy centred around coordinating machine setups is advantageous at relatively high setup to processing time ratios, while classic job shop rules suffice otherwise. Based on these results, we present recommendations for managing such environments. We also suggest future research directions in this area.     

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.     

A hybrid genetic algorithm and tabu search for a multi-objective dynamic job shop scheduling problem

In most real manufacturing environments, schedules are usually inevitable with the presence of various unexpected disruptions. In this paper, a rescheduling method based on the hybrid genetic algorithm and tabu search is introduced to address the dynamic job shop scheduling problem with random job arrivals and machine breakdowns. Because the real-time events are difficult to express and take into account in the mathematical model, a simulator is proposed to tackle the complexity of the problem. A hybrid policy is selected to deal with the dynamic feature of the problem. Two objectives, which are the schedule efficiency and the schedule stability, are considered simultaneously to improve the robustness and the performance of the schedule system. Numerical experiments have been designed to test and evaluate the performance of the proposed method. This proposed method has been compared with some common dispatching rules and meta-heuristic algorithms that have been widely used in the literature. The experimental results illustrate that the proposed method is very effective in various shop-floor conditions.     

Adaptive scheduling of batch servers in flow shops

Batch servicing is a common way of benefiting from economies of scale in manufacturing operations. Good examples of production systems that allow for batch processing are ovens found in the aircraft industry and in semiconductor manufacturing. In this paper we study the issue of dynamic scheduling of such systems within the context of multi-stage flow shops. So far, a great deal of research has concentrated on the development of control strategies, which only address the batch stage. This paper proposes an integral scheduling approach that also includes succeeding stages. In this way, we aim for shop optimization, instead of optimizing performance for a single stage. Our so-called look-ahead strategy adapts its scheduling decision to shop status, which includes information on a limited number of near-future arrivals. In particular, we study a two-stage flow shop, in which the batch stage is succeeded by a serial stage. The serial stage may be realized by a single machine or by parallel machines. Through an extensive simulation study it is demonstrated how shop performance can be improved by the proposed strategy relative to existing strategies.     

A particle swarm optimisation for the no-wait flow shop problem with due date constraints

This paper considers the no-wait flow shop scheduling problem with due date constraints. In the no-wait flow shop problem, waiting time is not allowed between successive operations of jobs. Moreover, a due date is associated with the completion of each job. The considered objective function is makespan. This problem is proved to be strongly NP-Hard. In this paper, a particle swarm optimisation (PSO) is developed to deal with the problem. Moreover, the effect of some dispatching rules for generating initial solutions are studied. A Taguchi-based design of experience approach has been followed to determine the effect of the different values of the parameters on the performance of the algorithm. To evaluate the performance of the proposed PSO, a large number of benchmark problems are selected from the literature and solved with different due date and penalty settings. Computational results confirm that the proposed PSO is efficient and competitive; the developed framework is able to improve many of the best-known solutions of the test problems available in the literature.     

A model to examine the effect of loading conditions on scheduling rules in a job shop environment

Although a great deal of research has been carried out in the field of job scheduling this has generally been directed towards examining the benefits of particular rules and presenting improved algorithms. This paper examines how real job shop problems can be modelled and available scheduling rules examined for particular capacity loading conditions. A model of a medium-size production job shop is developed and it is shown that, for their particular shop layout and job mix, the performance and ranking of particular rules with respect to certain criteria, change with shop conditions. The model developed can easily be applied to a wide range of job shop situations and once performance charts have been produced for those scheduling rules available, they can be used to aid the existing scheduling system whether manual or computer based.     

An integrated scheduling and material-handling approach for complex job shops: a computational study

We suggest an extension of the shifting bottleneck heuristic for complex job shops that takes the operations of automated material-handling systems (AMHS) into account. The heuristic is used within a rolling horizon approach. The job-shop environment contains parallel batching machines, machines with sequence-dependent setup times, and re-entrant process flows. Jobs are transported by an AMHS. Semiconductor wafer fabrication facilities (wafer fabs) are typical examples for manufacturing systems with these characteristics. Our primary performance measure is total weighted tardiness (TWT). The shifting bottleneck heuristic (SBH) uses a disjunctive graph to decompose the overall scheduling problem into scheduling problems for single machine groups and for transport operations. The scheduling algorithms for these scheduling problems are called subproblem solution procedures (SSPs). We consider SSPs based on dispatching rules. In this paper, we are also interested in how much we can gain in terms of TWT if we apply more sophisticated SSPs for scheduling the transport operations. We suggest a Variable Neighbourhood Search (VNS) based SSP for this situation. We conduct simulation experiments in a dynamic job-shop environment in order to assess the performance of the suggested algorithms. The integrated SBH outperforms common dispatching rules in many situations. Using near to optimal SSPs leads to improved results compared with dispatching based SSPs for the transport operations.     

基于规则和仿真的多机并行作业车间生产调度研究

资源分派和能力分派是作业车间生产调度中的重要问题,路径选择规则和分派规则是解决上述问题的有效途径。采用基于规则的仿真研究多机并行作业车间资源分派和能力分派问题,分析工件加工时间、到达率以及机器加工速率对调度结果的影响,以平均完工时间、平均延迟交货率以及平均资源利用率为评价指标,通过对4种路径选择规则和6种分派规则的仿真试验,确定不同性能指标下最佳的调度规则。仿真研究表明:调度规则的选用取决于车间资源配置和调度目标,应避免仅凭借经验或偏好选择规则的调度方法。     

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.     

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.     

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.