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.     

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.     

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.     

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 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.     

Efficient jobshop dispatching rules: Further developments

Many dispatching rules for scheduling in dynamic jobshops have been proposed over many years. The research issues in jobshop scheduling seem to be still open in the sense that no single rule has been found to be the best under all shopfloor conditions even with respect to one single measure of performance. Added to this problem, there are several measures of performance, e.g. the minimizations of mean, maximum and variance of flowtime, percentage of tardy jobs, and mean, maximum and variance of tardiness of jobs. Recent studies have reported the development of more efficient dispatching rules than the popular rules, e.g. SPT, COVERT, MOD and ATC. This study is an attempt to improve some of the recently reported dispatching rules. An extensive simulation study reveals that the improved rules developed in the present study appear to be quite effective in minimizing mean flowtime, and maximum tardiness and variance of tardiness of jobs.     

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.     

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.     

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.     

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 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.     

多功能机床环境下的Job Shop问题研究

本文引入工序机的概念描述加工系统的资源,建立了面向多功能加工机床的Job Shop作业计划模型,用遗传算法对所建的模型进行优化。在遗传算法优化搜索的基础上,利用工件、工序机和实际机床之间的动态调度使作业计划更趋合理。最后给出数值试验结果。     

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.     

Fundamental Insights into Part Family Scheduling: The Single Machine Case

A simulation study was conducted to investigate the behavior of family scheduling procedures in a dynamic dispatching environment. Two scheduling rules that incorporate setup avoidance mechanisms (FCFS-F and SPT-F) and two that do not (FCFS and SPT) were applied to a single machine. The scheduling environment was varied by controlling several important factors: the machine utilization, the number of setup configurations (families), the size of the family setup times relative to the job run times, the frequency by which members of the part families were released for processing, and the distribution of job interarrival and job run times. The major results from the study are the following: (1) The degree of stability in the system is the most influential factor with respect to mean flow time and flow time variance. Under low variance service and interarrival time distributions, the impact of scheduling rule selection is minor. (2) Conversely, under unstable scheduling situations, family scheduling procedures can have a substantial impact. (3) Clear interaction effects are noticed between all factors. The environment most conducive to family scheduling is characterized by high resource utilization, low setup-to-run time ratio, few part families, and erratic job arrivals. (4) Under conditions favorable to family scheduling, setup avoiding procedures can be used to increase output while at the same time reduce the mean and variance of flow time. (5) The shortest processing time rule (SPT) performs well with respect to mean flow time when relative setup times are small. Overall, however, SPT-F generates the lowest mean flow time while FCFS-F produces the lowest flow time variance. This study shows that scheduling procedures that consider setups in their structure can outperform rules that do not under many different operating conditions. However, the magnitude of this advantage very much depends on the scheduling environment. The results also highlight the fact that it may be better to try to reshape the manufacturing environment than worry about selecting the correct scheduling rule. If the environment cannot be stabilized, then the choice of a setup avoiding procedure, allocation of families to machines, and setup reduction become important issues.     

A heuristic approach to n/ m job shop scheduling: fuzzy dynamic scheduling algorithms

n/m shop scheduling is a ‘ NP-Hard’ problem. Using conventional heuristic algorithms ( priority rules) only, it is almost impossible to achieve an optimal solution. Research has been carried out to improve the heuristic algorithms to give a near-optimal solution. This paper advocates a fuzzy logic based, dynamic scheduling algoridim aimed at achieving this goal. The concept of new membership functions is discussed in die algorithm as a link to connect several priority rules. The constraints to determine the membership function of jobs for a particular priority rule are established, and three membership functions are developed. In order to decide the weight vector of priority rules, an aggregate performance measure is suggested. The methodology for constructing the weight vector is discussed in detail. Experiments have been carried out using a simulation technique to validate the proposed scheduling algorithm.     

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.     

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.     

Operation-based flowtime estimation in a dynamic job shop

In the scheduling literature, estimation of job flowtimes has been an important issue since the late 1960s. The previous studies focus on the problem in the context of due date assignment and develop methods using aggregate information in the estimation process. In this study, we propose a new flowtime estimation method that utilizes the detailed job, shop and route information for operations of jobs as well as the machine imbalance information. This type of information is now available in computer-integrated manufacturing systems. The performance of the proposed method is measured by computer simulation under various experimental conditions. It is compared with the existing flowtime estimation methods for a wide variety of performance measures. The results indicate that the proposed method outperforms all the other flowtime estimation methods. Moreover, it is quite robust to changing shop conditions (i.e., machine breakdowns, arrival rate and processing time variations, etc.). A comprehensive bibliography is also provided in the paper.     

Real-time part dispatching within manufacturing cells using fuzzy logic

A new fuzzy logic dispatching method is presented ff which o ers an improvement over certain existing common dispatching rules with respect to the performance measures, number of late parts, maximum part lateness, average producff tion times and machine bu er levels. The fuzzy logic dispatcher incorporates a wider range of scheduling issues than those considered by most dispatching rules, considers certain control ff issues that e ect scheduling, contains mechanisms for optimization and also allows for the addition of more control or scheduling rules.