Evaluation of simple dispatching rules for dynamic single-machine earliness/tardiness problem

Abstract. This paper investigates the effects of four simple dispatching rules on just-in-time production related performance measures of mean and maximum absolute lateness. The rules used are modified due date (MDD), shortest processing time (SPT), earliest due date (EDD), and first in first out (FIFO). A single machine is used under three utilization levels. Due-dates are set according to total work content rule. The results indicate that each rule performs well under certain conditions. The MDD rule is the best one to minimize mean absolute lateness. The EDD and FIFO rules do well in minimizing the maximum absolute lateness. Economic interpretation of these performance measures are also discussed.     

A comparative analysis of due date based job sequencing rules in a flow shop with multiple processors

The literature on job scheduling recognizes the importance of due date performance criteria such as mean tardiness and maximum tardiness. A number of studies test a large number of sequencing rules for these criteria in job shop and flow shop settings. The object of this present research is to examine the performance of some well-known priority rules in a flow shop with multiple processors. This study investigates the performance of ten priority rules in terms of mean and maximum tardiness. It examines the effects of problem characteristics, such as number of jobs, number of machines stages and number of parallel processors at each stage, and the performance of priority rules using regression analysis. The findings of the study suggest that the primary determinants of tardiness-based criteria are problem characteristics. In addition, both the regression analysis and the analysis of variance provide strong evidence of the strategy-effect. Finally, a detailed performance review of examined priority rules for various problem characteristics is presented.     

Customer Order Scheduling in a General Job Shop Environment*

The primary objective of this study is to examine the performance of order-based dispatching rules in a general job shop, where the environmental factors are shop utilization and due date tightness. An order is defined as a collection of jobs that are shipped as a group—an order—to the customer, only on completion of the last job of the order. We specifically compare dispatching rules from past job-based studies to some rules adapted to encompass order characteristics. Standard flow time and tardiness measures are used, but in addition, we introduce measures that combine average performance with variation in an attempt to capture the performance of a majority of the orders processed in the shop. Of the 16 dispatching rules tested, our results show that four of the simple rules dominate the others. We also found that order-based rules perform better than their job-based counterparts. The study makes use of multivariate statistical analysis, in addition to the usual univariate tests, which can provide additional insight to managers using multiple criteria in their decision process.     

A comparative analysis of two different approaches to scheduling in flexible flow shops

This work is an investigation about the relative effectiveness of two approaches to scheduling in flexible flow shops: one approach advocating the possible use of different dispatching rules at different stages of the flow shop, and the other suggesting the use of the same dispatching rule at all the stages of the flow shop. In the latter approach, the dispatching rule contains the information related to both process time and duedate. Both approaches aim at the minimization of measures related to flowtime and tardiness of jobs. This paper essentially is an attempt at exploring the relative effectiveness of these two approaches to scheduling.     

Workload Control and Order Release: A Lean Solution for Make‐to‐Order Companies

Protecting throughput from variance is the key to achieving lean. Workload control (WLC) accomplishes this in complex make‐to‐order job shops by controlling lead times, capacity, and work‐in‐process (WIP). However, the concept has been dismissed by many authors who believe its order release mechanism reduces the effectiveness of shop floor dispatching and increases work center idleness, thereby also increasing job tardiness results. We show that these problems have been overcome. A WLC order release method known as “LUMS OR” (Lancaster University Management School order release) combines continuous with periodic release, allowing the release of work to be triggered between periodic releases if a work center is starving. This paper refines the method based on the literature (creating “LUMS COR” [Lancaster University Management School corrected order release]) before comparing its performance against the best‐performing purely periodic and continuous release rules across a range of flow directions, from the pure job shop to the general flow shop. Results demonstrate that LUMS COR and the continuous WLC release methods consistently outperform purely periodic release and Constant WIP. LUMS COR is considered the best solution in practice due to its excellent performance and ease of implementation. Findings have significant implications for research and practice: throughput times and job tardiness results can be improved simultaneously and order release and dispatching rules can complement each other. Thus, WLC represents an effective means of implementing lean principles in a make‐to‐order context.     

Dynamic selection of dispatching rules for job shop scheduling

Although the academic contribution to job shop scheduling is abundant, its impact on practice has been minimal. The most preferred approach to job shop scheduling in the industry is dispatching rules. A major criticism against dispatching rules is that there is no single universal rule. The effective choice of dispatching rules depends on the scheduling criterion and existing job shop conditions. In this paper, the authors have proposed a scheduling method based on the analytic hierarchy process, that dynamically selects the most appropriate dispatching rule from several candidate rules. The selection is based on the existing job shop conditions. This method is applied to two formal job shop problems, and the results for single dispatching rules are inferior to the method proposed in this paper.     

A hybrid knowledge discovery model using decision tree and neural network for selecting dispatching rules of a semiconductor final testing factory

One of the most challenging production decisions in the semiconductor testing industry is to select the most appropriate dispatching rule which can be employed on the shop floor to achieve high manufacturing performance against a changing environment. Job dispatching in the semiconductor final testing industry is severely constrained by many resources conflicts and has to fulfil a changing performance required by customers and plant managers. In this study we have developed a hybrid knowledge discovery model, using a combination of a decision tree and a back-propagation neural network, to determine an appropriate dispatching rule using production data with noise information, and to predict its performance. We built an object-oriented simulation model to mimic shop floor activities of a semiconductor testing plant and collected system status and resultant performances of several typical dispatching rules, earliest-due-date (EDD) rule, first-come-first-served rule, and a practical dispatching heuristic taking set-up reduction into consideration. Performances such as work-in-process, set-up overhead, completion time, and tardiness are examined. Experiments have shown that the proposed decision tree found the most suitable dispatching rule given a specific performance measure and system status, and the back propagation neural network then predicted precisely the performance of the selected rule.     

A multiobjective genetic algorithm for job shop scheduling

In this paper, a Multi Objective Genetic Algorithm (MOGA) is proposed to derive the optimal machine-wise priority dispatching rules ( pdrs ) to resolve the conflict among the contending jobs in the Giffler and Thompson (GT) procedure applied for job shop problems. The performance criterion considered is the weighed sum of the multiple objectives minimization of makespan, minimization of total idle time of machines and minimization of total tardiness. The weights assigned for combining the objectives into a scalar fitness function are not constant. They are specified randomly for each evaluation. This in turn leads to the multidirectional search in the proposed MOGA, which in turn mitigates the solution being entrapped in local minima. The applicability and usefulness of the proposed methodology for the scheduling of job shops is illustrated with 28 benchmark problems available in the open literature.     

Dynamic scheduling of manufacturing job shops using extreme value theory

Most job shop scheduling approaches reported in the literature assume that the scheduling problem is static (i.e. job arrivals and the breakdowns of machines are neglected) and in addition, these scheduling approaches may not address multiple criteria scheduling or accommodate alternate resources to process a job operation. In this paper, a scheduling method based on extreme value theory (SEVAT) is developed and addresses all the shortcomings mentioned above. The SEVAT approach creates a statistical profile of schedules through random sampling, and predicts the quality or 'potential' of a feasible schedule. A dynamic scheduling problem was designed to reflect a real job shop scheduling environment closely. Two performance measures, viz. mean job tardiness and mean job cost, were used to demonstrate multiple criteria scheduling. Three factors were identified, and varied between two levels each, thereby spanning a varied job shop environment. The results of this extensive simulation study show that the SEVAT scheduling approach produces a better performance compared to several common dispatching rules.     

A comparative study of some priority dispatching rules under different shop loads

Priority dispatching rules and shop load affect job-shop performance. This paper evaluates ten different priority dispatching rules with respect to six different performance criteria under light, medium and heavy shop loads. Simulation was used as a tool to determine the rankings of the dispatching rules for a given shop load and performance criteria. A comparative study was conducted to investigate the performance of these rules. Two rules, ‘shortest processing time” and ‘least work remaining’, performed well under criteria related to the processing time. It was found that the rules that perform well in average and r.m.s. tardiness perform poorly under percentage-of-jobs-late criterion. The experimental results are conveyed with critical comments on the performance of the dispatching rules under different loading conditions of the shop.     

Overtime usage in a job shop environment

Problems are encountered in a job shop which has a fixed capacity if the total work content of the jobs passing through the shop increases sufficiently. Even the use of effective priority dispatching rules and/or expediting does not adequately shorten the queues which develop if the total work content continually exceeds shop capacity. To avoid losing job orders because the orders are unduly delayed, the job shop might resort to overtime usage. This study examines the efficient and economic use of overtime to relieve the backlog problem and uses overtime as the basic criterion for evaluation of overtime usage. The study employs GPSS V programming language to simulate a hypothetical job shop. The shop is loaded to various proportions of its normal capacity and various levels of overtime are tested. Findings show that overtime should not be assigned indiscriminately but rather should be based on a shop's unique conditions of overtime cost, the priority rule being employed, and the level of capacity utilization. Marginal benefit-cost ratio curves are developed to determine whether overtime usage is economically reasonable. These curves may also be used to determine the maximum or limiting amount of overtime to use under specific shop conditions.     

Order Dispatching and Labor Assignment in Cellular Manufacturing Systems

Although order and labor dispatching in the job shop manufacturing setting have been investigated extensively over the last three decades, its representation of actual processes found in practice today is limited due to the move to cellular manufacturing (CM). Manufacturing cells have become an important approach to batch manufacturing in the last two decades, and their layout structure provides a dominant flow structure for the part routings. The flow shop nature of manufacturing cells adds a simplifying structure to the problem of planning worker assignments and order releases, which makes it more amenable to the use of optimization techniques. In this paper we exploit this characteristic and present two mathematical modeling approaches for making order dispatching and labor assignment/reassignment decisions in two different CM settings. The two formulations are evaluated in a dynamic simulation setting and compared to a heuristic procedure using tardiness as the primary performance measure. The formulations are superior to the heuristic approach and can be incorporated into detail scheduling systems that are being implemented by corporations employing enterprise resource planning (ERP) systems today.     

A note on a well-known dispatching rule to minimize total tardiness

The single machine tardiness problem is considered. We clarify and correct an earlier result related to the Modified Due Date (MDD) Rule of Baker and Bertrand and show that a heuristic does not always satisfy an optimal sequence. However, we present some interesting special cases of optimal sequences that do satisfy the MDD Rule. We believe this note is important because the MDD Rule is still considered to be one of the most efficient rules to minimize the single machine tardiness problem. Because of its dispatching nature and simplicity, the MDD Rule is found to be very practical. It is widely applied in both static and dynamic job shop and industrial settings where setup times if any are negligible or included in the job processing times and hence not an issue.     

Priority dispatching rules in job shops with assembly operations and random delays

The article reports the results of an experimental investigation into priority dispatching rules for a job shop with assembly operations. A job is made up of several parts, where parts are individual entities requiring several operations in different machine centres. The study was directed towards rules which attempt to co-ordinate the completion time of parts required in the same job. This mainly involves rules that utilise job status information such as operation float, number of parts completed, and number of operations remaining on each part. Results indicate that job status information improves most of the measures of performance used.     

A hybrid approach to sequencing jobs using heuristic rules and neural networks

A hybrid approach to solve job sequencing problems using heuristic rules and artificial neural networks is proposed. The problem is to find a job sequence for a single machine that minimizes the total weighted tardiness of the jobs. Two different cases are considered: (1) when there are no setups, and (2) when there are sequence-dependent setup times. So far, successful heuristic rules for these cases are: apparent tardiness cost (ATC) rule proposed by Vepsalainen and Morton for the former case, and an extended version of the ATC rule (ATCS) proposed by Lee, Bhaskaran, and Pinedo for the latter. Both approaches utilize some look-ahead parameters for calculating the priority index of each job. As reported by Bhaskaran and Pinedo, the proper value of the look-ahead parameter depends upon certain problem characteristics, such as due-date tightness and due-date range. Thus, an obvious extension of the ATC or the ATCS rule is to adjust the parameter values depending upon the problem characteristics: this is known to be a difficult task. In this paper, we propose an application of a neural network as a tool to ‘predict’ proper values of the look-ahead parameters. Our computational tests show that the proposed hybrid approach outperforms both the ATC rule with a fixed parameter value and the ATCS using the heuristic curve-fitting method.     

Replanning the Master Production Schedule for a Capacity-Constrained Job Shop

This research examines the use of both frozen and replanning intervals for planning the master production schedule (MPS) for a capacity-constrained job shop. The results show that forecast error, demand lumpiness, setup time, planned lead time, and order size have a greater impact on the mean total backlog, total inventory, and number of setups than the frozen and replanning intervals. The study also shows that a repetitive lot dispatching rule reduces the importance of lot sizing, and a combination of repetitive lot dispatching rule and single-period order size consistently produces the lowest mean total backlog and total inventory. The results also indicate that rescheduling the open orders every period produces a lower mean total backlog and total inventory when the forecast errors are large relative to the order sizes. This result suggests that the due date of an open order should be updated only when a significant portion of the order is actually needed on the new due date.     

Total tardiness minimization on unrelated parallel machine scheduling with auxiliary equipment constraints

This research deals with scheduling jobs on unrelated parallel machines with auxiliary equipment constraints. Each job has a due date and requires a single operation. A setup for dies is incurred if there is a switch from processing one type of job to another type. For a die type, the number of dies is limited. Due to the attributes of the machines and the fitness of dies to each, the processing time for a job depends on the machine on which the job is processed, each job being restricted to processing on certain machines. In this paper, an effective heuristic based on threshold-accepting methods, tabu lists, and improvement procedures is proposed to minimize total tardiness. An extensive experiment is conducted to evaluate the computational characteristics of the proposed heuristic. Computational experiences demonstrate that the proposed heuristic is capable of obtaining optimal solutions for small-sized problems, and significantly outperforms an ATCS procedure and a simulated annealing method for problems in larger sizes.     

A FRAMEWORK FOR MACHINE SCHEDULING PROBLEMS WITH CONTROLLABLE PROCESSING TIMES

This is a study of single and parallel machine scheduling problems with controllable processing time for each job. The processing time for job j depends on the position of the job in the schedule and is a function of the number of resource units allocated to its processing. Processing time functions and processing cost functions are allowed to be nonlinear. The scheduling problems considered here have important applications in industry and include many of the existing scheduling models as special cases. For the single machine problem, the objective is minimization of total compression costs plus a scheduling measure. The scheduling measures include makespan, total flow time, total differences in completion times, total differences in waiting times, and total earliness and tardiness with a common due date for all jobs. Except when the total earliness and tardiness measure is involved, each case the problem is solved efficiently. Under an assumption typically satisfied in just-in-time systems, the problem with total earliness and tardiness measure is also solved efficiently. Finally, for a large class of processing time functions; parallel machine problems with total flow time and total earliness and tardiness measures are solved efficiently. In each case we reduce the problem to a transportation problem.     

GLOBAL JOB SHOP SCHEDULING WITH A GENETIC ALGORITHM

This paper describes a global job shop scheduling procedure that uses a genetic algorithm to find a good schedule. Unlike previously considered algorithms, this procedure has been implemented in the scheduling system for a manufacturing facility and has led to improved scheduling. This facility is a semiconductor test area. The test area is a job shop and has sequence-dependent setup times at some operations. The concern of management is to meet their customer due dates and to increase throughput. This requires the coordination of many resources, a task beyond the ability of simple dispatching rules. We discuss a centralized procedure that can find a good schedule through the use of a detailed scheduling model and a genetic algorithm that searches over combinations of dispatching rules. We discuss our effort in developing a system that models the shop, creates schedules for the test area personnel, and makes a number of contributions to test area management.     

Shop Performance Implications of Using Cells,Partial Cells,and Remainder Cells*

This paper considers the application of cellular manufacturing (CM) to batch production by exploring the shop floor performance trade‐offs associated with shops employing different levels of CM. The literature has alluded to a continuum that exists between the purely departmentalized job shop and the completely cellular shop. However, the vast majority of CM research exists at the extremes of this continuum. Here, we intend to probe performance relationships by comparing shops that exist at different stages of CM adoption. Specifically, we begin with a hypothetical departmentalized shop found in the CM literature, and in a stepwise fashion, form independent cells. At each stage, flow time and tardiness performance is recorded. Modeling results indicate that, depending on shop conditions and managerial objectives, superior shop performance may be recorded by the job shop, the cell shop, or by one of the shops between these extreme points. In fact, under certain conditions, shops that contain partially formed cells perform better than shops that use completely formed cells. Additional results demonstrate that in order to achieve excellent performance, managers investigating specific layouts need to pay especially close attention to changes in machine utilization as machine groups are partitioned into cells.