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.     

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.     

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.     

TWO DESIGN PRINCIPLES FOR KNOWLEDGE-BASED SYSTEMS*

This paper discusses two principles that have become increasingly important in the design of knowledge-based systems: domain-specific knowledge used to support opportunistic reasoning and hierarchical organization structure used to control and coordinate problem-solving activity. We propose a design framework that embodies these two principles and describe how this framework has been used to develop a knowledge-based job-shop scheduling system. This system, called OPIS 0, has undergone limited testing in an experimental environment modeled after an actual job shop. Its performance has been very good compared to ISIS and to the more traditional approach of constructing a schedule by dispatching jobs using the COVERT priority rule. The resulting design also shows potential for use in a decision support role.     

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

PCB assembly scheduling through kit concept

This paper presents the design and test of a new scheduling environment dedicated to the off-line scheduling of PCB assembly shops. The main idea introduced is the employment of the 'kit concept' as a scheduling tool, as opposed to the traditional batch scheduling. In the kit approach, the basic PCB aggregations are kits composed of different PCBs matching finished products requirements, instead of homogeneous batches of identical boards. By introducing the kit approach, PCB assembly schedule is intended to be focused more towards the assembly of final products than towards the internal PCB assembly shop constraints and requirements. A simulation model and data from a real assembly system are used to compare the kit approach with traditional batch processing. Experimental results show that the proposed kit approach jointly achieves remarkable improvements in the effectiveness and efficiency performances of the assembly system, as compared to the batch approach. However, it is determined also that these advantages can only be achieved if a sufficiently advanced scheduling system is used.     

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.     

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.     

Effects of Erroneous Estimation of Activity Durations on Scheduling and Dispatching a Single Project*

This research examines the effects of erroneous estimation of activity durations on two different approaches for executing a resource-constrained project. The two approaches are scheduling and dispatching. This research is conducted in two phases. Phase one examines the performance of scheduling and dispatching rules in a variety of project environments. These project environments are categorized by three different factors, namely, the order strength of the precedence relationship, the level of resource availability and the size of errors in estimating the activity durations. The results show that scheduling generally produces a shorter project completion time than the heuristic dispatching rules. The results also indicate that project environment affects only the relative performance differences of the scheduling and dispatching rules but not their ranking. Phase two examines the effect of rescheduling. The results show that frequent rescheduling improves the project completion time, while the timing of rescheduling has little impact on the improvement in the project completion time. The results also identify the project environments where rescheduling is beneficial.     

Multi-objective permutation flow shop scheduling problem: Literature review,classification and current trends

The flow shop scheduling problem is finding a sequence given n jobs with same order at m machines according to certain performance measure(s). The job can be processed on at most one machine; meanwhile one machine can process at most one job. The most common objective for this problem is makespan. However, many real-world scheduling problems are multi-objective by nature. Over the years there have been several approaches used to deal with the multi-objective flow shop scheduling problems (MOFSP). Hence, in this study, we provide a brief literature review of the contributions to MOFSP and identify areas of opportunity for future research.     

The permutation flow shop problem with just in time production considerations

This research presents a variation to the permutation flow shop problem where Just In Time (JIT) production requirements are taken into account. The model developed in this research employs dual objectives. In addition to the traditional objective of minimizing the production makespan, minimization of Miltenburg's material usage rate is also incorporated. In this model, multiple units of any product are permitted in the production sequence. However, the minimization of material usage rates attempts to prevent batch scheduling of products and allows unit flow of products as required in demand flow manufacturing. A solution method is proposed for determining an optimal production sequence via an efficient frontier approach and Simulated Annealing (SA). Test problems and specific performance criteria are used to assess the solutions generated by the proposed method. Experimental results presented in this paper show that the use of the efficient frontier and SA provide solutions that approach the optimal solution for the performance measures used in this research.     

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.     

THE IMPACT OF SIMPLE PRIORITY RULE COMBINATIONS ON DELIVERY SPEED AND DELIVERY RELIABILITY IN A HYBRID SHOP

This study examines the effects of using different priority rules at different stages of a multistage, flow-dominant shop. A simulation model is constructed of a manufacturing system comprised of three stages: gateway, intcrmcdiatc, and finishing. As is typical of a flow-dominant shop, the overall flow of the simulated system (gateway to intermediate to finishing) is consistent with a flow shop, but processing in the intermediate stage involves multiple work centers and resembles a job shop. Shop performance is observed when four well-known priority heuristics are applied in different combinations in the gateway, intermediate, and finishing stages of the process. Multiple performance measures addressing the strategic objectives of delivery speed and delivery reliability are recorded under two different shop load conditions. Results show that the measures of both delivery speed and delivery reliability are affected by the priority rule combinations, and that a tradeoff exists between average performance and consistency of performance. Certain priority rule combinations affect performance in predictable ways, allowing the user to assess tradeoffs between delivery speed and delivery reliability.     

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.     

Flow shop scheduling by transportation model

This paper describes the classical problem of scheduling n jobs on m machines in a flow shop. A schedule evaluation algorithm is presented, which for job-pairs, generates a schedule evaluation matrix. The matrix is the input data to a transportation problem, the solution of which gives near-optimal jobsequence and makespan. The performance of the algorithm is discussed.     

Shop floor characteristics influencing the use of advanced planning and scheduling systems

The purpose of this article is to investigate how the manufacturing process, the shop type and the data quality, i.e. the shop floor characteristics, influence the use of advanced planning and scheduling (APS) systems in production activity and control (PAC). The methodology implemented is a multiple case study at three case companies. Each company has different shop floor characteristics, but all use a scheduling module in an APS system, which supports production scheduling. A theoretical framework is developed suggesting how APS system are used in the PAC activities, and which major aspect to consider. The case analysis shows that the scheduling module in APS system, foremost supports sequencing and dispatching. In particular, the shop type is influenced by the decision of how often the APS runs and what freedom is given to the shop floor. The manufacturing process influences how the dispatch list is created. Contrary to the literature presuming that APS systems are most suitable in job shop processes, it is found that the manufacturing process is not a crucial factor when deciding whether APS systems are an appropriate investment. It is found that the level of data quality needed in the APS system depends to a large extent on how the dispatch list is used. For example, is the dispatch list used as a guideline, not a regulation, the need for accurate data in the module is reduced. This article extends the previous literature concerning APS systems by analysing how APS systems influence PAC as a whole and increase the understanding of the challenges of using APS systems in PAC.     

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.     

一种求解双目标flow shop排序问题的进化算法

提出一种求解双目标flow shop排序的递进多目标进化算法.算法采用改进的精英复制策略,在实现精英保留的前提下降低了计算复杂性;通过递进进化模式增加群体多样性,改善了算法收敛性;通过群体进化过程中对非劣解集进行竞争型可变邻域启发式搜索,增强了算法局部搜索性能.采用新算法和参照算法NSGA-II对31个标准双目标flow shop算例进行优化.研究结果表明,新算法在所有算例的求解中均获得了优于NSGA-II的非劣解集,验证了算法的有效性.     

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.