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.     

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.     

Single-machine batch delivery scheduling with an assignable common due window

This paper addresses a batch delivery single-machine scheduling problem in which jobs have an assignable common due window. Each job will incur an early (tardy) penalty if it is early (tardy) with respect to the common due window under a given schedule. There is no capacity limit on each delivery batch, and the cost per batch delivery is fixed and independent of the number of jobs in the batch. The objective is to find the optimal size and location of the window, the optimal dispatch date for each job, as well as an optimal job sequence to minimize a cost function based on earliness, tardiness, holding time, window location, window size, and batch delivery. We show that the problem can be optimally solved in O(n⁸)$O(n^8)$ time by a dynamic programming algorithm under a reasonable assumption on the relationships among the cost parameters. A computational experiment is also conducted to evaluate the performance of the proposed algorithm. We also show that some special cases of the problem can be optimally solved by lower order algorithms.     

Evaluation of scheduling strategies for a dynamic job shop in a tool-shared,flexible manufacturing environment

A two-phase approach is used to examine the impact of job scheduling rules and tool selection policies for a dynamic job shop system in a tool-shared, flexible manufacturing environment. The first phase develops a generalized simulation model and analyses 'simple' job scheduling rules and tool selection policies under various operating scenarios. The results from this investigation are then used to develop and analyse various bi-criteria rules in the second phase of this study. The results show that the scheduling rules have the most significant impact on system performance, particularly at high shop load levels. Tool selection policies affect some of the performance measures, most notably, proportion of tardy jobs, to a lesser degree. Higher machine utilizations can be obtained at higher tool duplication levels but at the expense of increased tooling costs and lower tool utilization. The results also show that using different processing time distributions may have a significant impact on shop performance.     

An Experimental Comparison of Time-Based and Economic-Based Scheduling Methods to Maximize Net Present Value*

In the past, performance in dynamic-scheduling environments was primarily measured in terms of time or physical shop characteristics. Objectives such as mean tardiness, flow time, and work-in-process inventory were commonly used. Today, there is increasing interest in the use of more advanced economic performance measures. These measures have the more comprehensive objective of maximizing ownership wealth by economically scheduling jobs and tasks. This study presents a large-scale experiment testing time-based and economic-based scheduling methods in a dynamic job shop. These methods are evaluated on their ability to maximize net present value (NPV). The study considers the just-in-time (JIT) delivery environment. The job shop is hypothetical, but is based on models of real production situations. Results show that the use of very detailed economic information in a sophisticated manner generally improves economic performance. Where due dates are easy to achieve, however, time-based scheduling methods are at least as good as those based on economics. Also, where utilization is high and due dates tight, early cost information in release and dispatch is detrimental to schedule value.     

Single-machine scheduling with periodic due dates to minimize the total earliness and tardy penalty

We consider a single-machine scheduling problem such that the due dates are assigned to each job depending on its order, and the lengths of the intervals between consecutive due dates are identical. The objective is to minimize the total penalty for the earliness and tardiness of each job. The early penalty proportionally increases according to the earliness amount, while the tardy penalty increases according to the step function. We show that the problem is strongly NP-hard, and furthermore, polynomially solvable if the two types of processing times exist.

     

An Evaluation of Capacity Sensitive Order Review and Release Procedures in Job Shops

We investigate the performance of capacity-sensitive order review and release (ORR) procedures in job shop environments that have not been previously explored. Previous research has ignored the case of job shops which must perform to very tight due-dates because of time-sensitive customers. We propose and test a new capacity sensitive ORR procedure called path based bottleneck (PBB) in such environments, along with the modified infinite loading (MIL) procedure which has been shown to work well in several studies. We compare the performance of these two controlled release rules with that of immediate release rule under different conditions of capacity utilization and customer specified exogenous duedates. Our results indicate that PBB performs well in lowering total costs when due-dates are tight, while MIL is a better procedure with relatively loose to medium due-dates. We also show that in many cases, the shortest processing time (SPT) dispatching rule is a superior performer than a due-date based rule like critical ratio (CR); a conclusion which is contrary to the existing research in this area. In addition, the shop floor control policies recommended are shown to be sensitive to the cost structure of the firm. The managerial implications of this research in providing effective shop floor control in job shops operating under tight due-date conditions are also discussed.     

MINIMIZING ABSOLUTE AND SQUARED DEVIATION OF COMPLETION TIMES FROM DUE DATES

This is a study of a single-machine scheduling problem with the objective of minimizing the sum of a function of earliness and tardiness called the earliness and tardiness (ET) problem. I will show that if priority weights of jobs are proportional to their processing times, and if earliness and tardiness cost functions are linear, the problem will be equivalent to the total weighted tardiness problem. This proves that the et problem is np -hard. In addition, I present a heuristic algorithm with worst case bound for the et problem based on the equivalence relation between the two. When earliness and tardiness cost functions are quadratic, I consider the problem for a common due date for all jobs and for different job due dates. In general, the et problem with quadratic earliness and tardiness cost functions and all job weights equal to one is np -hard. I show that in many cases, when weights of jobs are proportional to their processing times, the problem can be solved efficiently. In the published results on the et problem with quadratic earliness and tardiness cost functions other researchers have assumed a zero starting time for the schedule. I discuss the advantages of a nonzero starting time for the schedule.     

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.     

AN EXPERIMENTAL MODEL FOR INVESTIGATING THE SENSITIVITY OF JOB SHOP PERFORMANCE TO JOB RELEASE TIME DISTRIBUTION PARAMETERS

Work flows in a job shop are influenced by the load per release and time interval between release factors. We focus on the latter factor, job release times. Building on Elvers' work, this study evaluates the impact of different job release time distributions on shop performance. Using a computer simulation of a random job shop and a full factorial experimental design, we demonstrate that the type of distribution does affect performance–a finding consistent with results from job shops characterized by good shop floor control practices. These findings are explained by examining the shape and variance traits of the underlying job release time distributions.     

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 simulated annealing algorithm for job shop scheduling

In this paper, the job shop scheduling problem is considered with the objective of minimization of makespan time. We first reviewed the literature on job shop scheduling using meta-heuristics. Then a simulated annealing algorithm is presented for scheduling in a job shop. To create neighbourhoods, three perturbation schemes, viz. pairwise exchange, insertion, and random insertion are used, and the effect of them on the final schedule is also compared. The proposed simulated annealing algorithm is compared with existing genetic algorithms and the comparative results are presented. For comparative evaluation, a wide variety of data sets are used. The proposed algorithm is found to perform well for scheduling in the job shop.     

Single-machine scheduling with production and rejection costs to minimize the maximum earliness

In this paper, we consider the single-machine scheduling problem with production and rejection costs to minimize the maximum earliness. If a job is accepted, then this job must be processed on the machine and a corresponding production cost needs be paid. If the job is rejected, then a corresponding rejection cost has to be paid. The objective is to minimize the sum of the maximum earliness of the accepted jobs, the total production cost of the accepted jobs and the total rejection cost of the rejected jobs. We show that this problem is equivalent to a single-machine scheduling problem to minimize the maximum earliness with two distinct rejection modes. In the latter problem, rejection cost might be negative in the rejection-award mode which is different from the traditional rejection-penalty mode in the previous literatures. We show that both of two problems are NP-hard in the ordinary sense and then provide two pseudo-polynomial-time algorithms to solve them. Finally, we also show that three special cases can be solved in polynomial time.     

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.     

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.     

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.     

A DECISION THEORY APPROACH TO PRIORITY DISPATCHING FOR JOB SHOP SCHEDULING

Recent developments in the design of job shop scheduling systems have inspired a new approach to priority dispatching. The basis for the approach is in elementary decision theory: at each decision juncture define the alternative courses of action, evaluate the consequences of each alternative according to a given criterion, and choose the best alternative. The experimental results of a simulated single machine queueing system reinforce earlier findings that a decision theory approach represents a significant advance over conventional priority dispatching.     

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.     

EVALUATING ORDER RELEASE MECHANISMS IN A JOB SHOP WITH SEQUENCE-DEPENDENT SETUP TIMES

Job-release mechanisms in job-shop control are receiving increased recognition in recent research. However, there is considerable disagreement over the benefits of sophisticated job-release mechanisms, and they remain to be tested in various operating environments. In our study, we extend previous job-releasing research by examining several job-release mechanisms in a different operating environment-a sequence-dependent setup job shop. We tested these release mechanisms, originally developed for a machine-constrained job shop, in conjunction with two groups of sequencing rules-ordinary and setup-oriented sequencing rules. We measured shop performance in terms of total cost, the sum of inventory-holding and late-penalty costs. We developed a simulation model of a nine-machine job shop for our experiment.