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 STOCHASTIC DOMINANCE ORDERING OF SCHEDULING RULES

This paper applies stochastic dominance (SD) preference-ordering criteria to job shop scheduling rules. A simulation model of a hypothetical dual-constrained job shop is used to derive several measures of shop performance for a number of dispatching/due-date scheduling policies. The results presented suggest that previous research conclusions concerning the relative performance of dispatching scheduling rules may need to be reconsidered if production schedulers are risk-averse utility maximizers.     

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.     

Application of the Net Present Value Criterion in Random and Flow Shop Scheduling*

While the majority of the literature on shop scheduling has emphasized time-based performance criteria such as mean flow time, lateness, and tardiness, the primary goal of management should be the maximization of shop profitability. In this research the net present value (NPV) criterion is introduced to measure shop profitability. This measure combines aspects of job flow time and inventory holding costs into a single measure. A simulation model of a job shop is used to examine the performance of a variety of time- and value-based scheduling rules. These rules are evaluated with respect to the NPV criterion in both random and flow shop environments. The results suggest that priority rules that utilize monetary information about jobs yield a higher NPV than many time-based rules in most situations, with little sacrifice in job tardiness. A well-researched time-based rule, critical ratio, also provides excellent performance when the shop is heavily loaded.     

Determining overtime policies for a repair shop

Problems arise when a repair shop with a fixed capacity has to cope with fluctuations in the arrivals of failed assemblies. The effective use of priority scheduling rules and labor assignment rules will enable the repair shop to work efficiently but only to the extent of the repair capacity of the shop. Increasing the number of spares in stock to accommodate these short-term fluctuations would be costly in the long run. In order to maintain a certain level of service, the repair shop often needs to resort to overtime. This paper examines various overtime policies, namely, proactive and reactive overtime policies, under various failure distributions and budget constraints for spares. The findings show that reactive overtime policies generally perform better than proactive overtime policies under the conditions tested. Benefit-cost ratio curves are developed for these overtime policies which illustrate the stochastic interaction effects of the priority scheduling rule, spares budget, and failure arrival distribution.     

The sensitivity of job mix and load capacity bottlenecks on inventory and due date performance in a manufacturing system

Based on a benchmark job-lot manufacturing system a simulation study was carried out to compare the performance of just-in-time (JIT) shop control system Kanban with conventional job-shop control procedures. The shop control policies were tested under a good manufacturing environment and the effects of job mix and load capacity bottlenecks on various shop control policies were tested. From the simulation results, it is inferred that there are shop control procedures that perform better than the Kanban in a job shop. It has been observed that even with adequate capacity, bottleneck areas surface due to fluctuations in the shop load. Kanban is not appropriate in such a situation because capacity bottlenecks can significantly reduce the ell'ectiveness of a pull system. The disparateness in the processing requirements for jobs can seriously undermine the performance of the shop. This is the type of shop environment where the shop control procedures will be most effective. Although Kanban came out best when the load capacity bottlenecks and the disparateness of the job mix were removed, the selected shop control variable combinations closely approximated the Kanban result. Although many features of JIT can be implemented in any system, companies trying to adopt JIT should remember that Kanban requires a rigid system intolerant of any deviation.     

Time completion for various dispatching rules in job shops

This study investigates the relative priority of various job shop dispatching rules for various shop utilization levels under both deterministic and stochastic assumptions with regard to processing times. The primary criterion for evaluation is that of percentage on time completion. The results indicate that an assumption of accurately predetermining actual operation times in most cases is not likely to weaken the analysis and impact of research studies which are performed using such an assumption. Also conclusions indicate that the ranking of dispatching rules according to their effectiveness varies significantly with shop utilization levels.     

Heterogeneous dispatching rules in job and flow shops

This paper reports the results of a study of the use of heterogeneous dispatching rules for the scheduling of work in a job shop. The methodology employed included discrete event simulation, using rule combinations determined by prior genetic algorithm searches and generalization using neural networks. Eight dispatching rules were considered, including first in first out (FIFO), earliest due date ( EDD), shortest processing time (SPT), slack/ number of operations (SLK), critical ratio (CR), modified due date (MDD), modified operation due date (MOD), and apparent tardiness cost (ATC). A three-machine job shop was studied, in which three work organizations were employed, pure flow (fixed sequence), pure job shop ( random sequence), and a hybrid shop where flow is random but with unequal probabilities. Three levels of machine loading were used and average tardiness was used as the performance measure. In most cases, modified due date and apparent tardiness cost were the best rules. The application of the best rules effected the results primarily when applied to bottleneck machines or the first machine in a pure flow shop. Nearly any other rule was acceptable on non-botdeneck machines except FIFO and CR, which consistently perform poorly. No major advantage of mixing rules was found.     

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.     

A COMPARISON OF ORDER-RELEASE AND DISPATCH RULES FOR THE DYNAMIC WEIGHTED EARLY/TARDY PROBLEM

The early/tardy problem is one of the most vexing pieces of the complex production scheduling decision process. So far most of the research has been on single-machine environments. Hence, we considered the weighted early/tardy scheduling problem in a simulated dynamic multimachine job shop. We analyzed controlled job-release and dispatch rules using time and cost information at a variety of stationary and nonstationary utilization rates, due-date allowances, and early/tardy cost levels. We found a newly developed method for controlling the release for all job operations using early/tardy cost information, superior to other release mechanisms overall in both our stationary and nonstationary analyses. We found immediate release useful at many high utilization conditions and a gateway-only release method best in many low utilization conditions. A modified version of a single-machine early/tardy dispatch method was clearly superior to the dispatch rules for almost all the simulated shop conditions.     

Scheduling with Sequencing Flexibility*

This study examines the effects of sequencing flexibility on the performance of rules used to schedule operations in manufacturing systems. The findings show that taking advantage of even low levels of sequencing flexibility in the set of operations required to do a job results in substantial improvement in the performance of scheduling rules with respect to mean flowtime. Differences in the mean flowtime measure for various rules also diminish significantly with increasing sequencing flexibility. Performance improvements additionally result for such due-date related performance measures as mean tardiness and the proportion of jobs tardy. At high levels of sequencing flexibility, some nonparametric scheduling rules outperform the shortest processing time rule in terms of the mean flowtime criterion. Rules based on job due dates also outperform rules based on operation milestones in terms of tardiness related criteria at high levels of sequencing flexibility. The implications of these findings for the design of manufacturing systems and product design are noted.     

Optimal and Heuristic Models for Lot Splitting in a Flow Shop

This paper investigates optimal lot-splitting policies in a multiprocess flow shop environment with the objective of minimizing either mean flow time or makespan. Using a quadratic programming approach to the mean flow time problem, we determine the optimal way of splitting a job into smaller sublots under various setup times to run time ratios, number of machines in the flow shop, and number of allowed sublots. Our results come from a deterministic flow shop environment, but also provide insights into the repetitive lots scheme using equal lot splits for job shop scheduling in a stochastic environment. We indicate those conditions in which managers should implement the repetitive lots scheme and where other lot-splitting schemes should work better.     

Alternate Routing Strategies in Batch Manufacturing: An Evaluation

Batch manufacturing firms are experiencing significant changes because of technological developments in work center design, such as flexible manufacturing systems (FMS) and planning/control tools like computer-aided process planning (CAPP). These new developments provide production managers with some solutions to a number of complex problems. For example, numerical-controlled (NC) machine center installations are effective in providing quality parts because of tight tolerance specifications built into the equipment. However, these highly efficient centers create bottlenecks that constrain shop throughput, since production planners tend to rely too much on them. To help improve manufacturing planning, we introduce an important element to the batch production scheduling component of CAPP's mission—evaluating possible alternate routes. Production scheduling encompasses job route selection as well as machine center assignment (loading), job releasing, and setting due dates. In this paper, three routing strategies requiring different levels of shop floor information are tested and evaluated using computer simulation. Shop performance is measured by total cost and traditional measures of job flow time, lateness, and tardiness.     

AN EVALUATION OF SEQUENCING RULES FOR AN ASSEMBLY SHOP

Research relating to sequencing rules in simple job shops has proliferated, but there has not been a corresponding proliferation of research evaluating similar sequencing rules in more complex assembly job shops. In a simple job shop, all operations are performed serially; but an assembly shop encompasses both serial and parallel operations. As a result of the increased complexity of assembly shops, the results associated with the performance of sequencing rules in simple job shops cannot be expected for an assembly shop. In this paper, 11 sequencing rules (some of which are common to simple job shops and some decigned specifically for assembly shops) are evaluated using a simulation analysis of a hypothetical assembly shop. The simulation results are analyzed using an ANOVA procedure that identifies significant differences in the results of several performance measures. Sensitivity analysis also is performed to determine the effect of job structure on the performance of the sequencing rules.     

Due Date Assignment,Job Order Release,and Sequencing Interaction in Job Shop Scheduling*

Depending on the techniques employed, the due date assignment, release, and sequencing procedures in job shop scheduling may depend on one another. This research investigates the effects of these interactions with a simulation model of a dynamic five-machine job shop in which early shipments are prohibited. Performance of the system is measured primarily in terms of the total cost (work-in-process cost, finished goods holding cost, and late penalty) incurred by the shop, but a number of non-cost performance measures are also reported. The results support existence of a three-way interaction between the due date, release, and sequencing procedures as well as interaction between shop utilization and procedure combination. Statistical tests are used to identify those rules that perform best both overall and in combination with other rules.     

An Investigation of Scheduling Policies in a Dual-Constrained Manufacturing Cell*

In previous group scheduling studies, labor has essentially been ignored by assuming that enough labor is assigned to each machine in the cell. In reality, however, management usually does not have the resources to employ a laborer at each machine in the cell (i.e., machines need to share labor). Both labor scheduling and group scheduling heuristics need to be administered to manage the cell effectively. This study develops and examines scheduling procedures for a dual-constrained (i.e., machine and labor) manufacturing cell. Eleven decision rules are developed and tested under 16 different experimental conditions. The experimental factors used are interarrival time distribution, cell load, setup-to-run-time ratio, and transfer-to-run-time ratio. Results show that interarrival time distribution and cell load have the greatest impact on the performance of the cell. This suggests that effective production planning aimed at reducing job arrival variation and leveling the cell load can substantially improve cell performance. Among the experimental factors, setup and transfer-to-run-time ratio factors had the strongest influence on the rankings of the decision rules. These rankings were fairly robust across all experimental conditions and performance measures. The results also indicated that the inclusion of labor as a contraint in the cell had a significant impact on the performance of several group scheduling heuristics. Finally, it was shown that the best performing decision rules consider both transfer time and subfamily setup times.     

Interactive Job Shop Scheduling: An Experiment

An experiment is discussed in which three computer-aided, interactive job shop scheduling approaches are compared using an interactive job shop scheduling simulator (JOB) developed for the project. All three approaches use a combination of computer and human capabilities to develop job shop schedules, but differ in terms of the timing and degree of human involvement required. The three scheduling approaches are (1) the successive approach, (2) the interactive approach, and (3) the semi-interactive approach. The successive approach is characterized by the computer scheduling all work orders without any human intervention. The interactive approach is distinguished by the human scheduling one work order at a time until all work orders are scheduled. The schedule is developed interactively by the person who must simultaneously consider work-order scheduling needs and machine group load capacities. The semi-interactive approach may be viewed as a combination of the successive and interactive approaches. Work orders are automatically scheduled one at a time using the successive approach criteria, but with prespecified machine-group load thresholds. As long as the load threshold is not exceeded, the successive approach is used to schedule work orders. When a threshold is exceeded, the algorithm (successive approach) pauses and human rescheduling (interactive approach) is required to rectify the overload situation. A second (reallocation) phase, identical for all three approaches, is used to overcome any scheduling problems generated in phase one. Experimental results based on nine different performance criteria (including scheduling time, makespan, machine group utilization, and work-in-process inventory) and 45 experimental runs indicate that there are differences between the results produced by the three scheduling approaches. The interactive approach yields the best overall scheduling results, but the other two approaches are clearly better than the interactive approach in some situations. The success of the interactive approach indicates that it is usually best for the human scheduler to become involved early in the computer-based job shop scheduling process.     

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.     

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.     

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.