Evolutionary search for difficult problem instances to support the design of job shop dispatching rules

Dispatching rules are simple scheduling heuristics that are widely applied in industrial practice. Their popularity can be attributed to their ability to flexibly react to shop floor disruptions that are prevalent in many real-world manufacturing environments. However, it is a challenging and time-consuming task to design local, decentralised dispatching rules that result in a good global performance of a complex shop.An evolutionary algorithm is developed to generate job shop problem instances for which an examined dispatching rule fails to achieve a good solution due to a single suboptimal decision. These instances can be easily analysed to reveal limitations of that rule which helps with the design of better rules. The method is applied to a job shop problem from the literature, resulting in new best dispatching rules for the mean flow time measure.     

Setting Job-Shop Due-Dates with Service-Level Constraints

The job-shop due-date assignment problem arises when a manager needs to ‘promise’ a delivery date to a customer. Previous methods yield due-dates which are either optimistic (unlikely to be achieved) or conservative (the promise will be met, but too easily, because the date given was very pessimistic). This paper investigates the due-date assignment problem with a customer ‘service-level’ constraint, the percentage of time that promised delivery dates are honoured. We formulate a rule to attain this service level, yet maintain as short a due-date lead time as possible. Unlike previous attempts, this due-date rule considers not only the job content and instantaneous shop congestion information, but also implicitly incorporates information on how the jobs will be scheduled (or ‘loaded’) once they are in the shop. We simulate a single-machine shop for various measures of performance under several dispatching priorities, comparing our due-date rule with one reported to yield satisfactory performance. Our rule meets all requirements and is found to be superior for most measures of performance.     

Using a family of critical ratio-based approaches to minimize the number of tardy jobs in the job shop with sequence dependent setup times

This paper addresses the job shop scheduling problem to minimize the number of tardy jobs, considering the sequence dependent setup time. This problem is taken as a sequencing problem, and a family of approaches with different levels of intricacy is proposed. The simplest form is a critical ratio-based dispatching rule, which leads to satisfactory solutions by taking into account the group information rather than only the individual information of jobs. Then, an enhanced approach consisting of an iterative schedule refining mechanism will be given. Its feature is to iteratively adjust the estimation of the remaining processing times of jobs in a dynamic and operation-specific manner. Finally, a genetic algorithm which takes the dispatching rule and the refining mechanism as the core is proposed. The performance of these approaches is carefully examined by a comprehensive experimental study.     

Optimization of setup times in the furniture industry

The aim of this paper is to develop a scheduling policy oriented towards minimizing setup times in the made-to-order furniture industry. The task is treated as a dynamic job shop scheduling problem, with the exception that customers?? orders collected over a?specified period of time are combined into a?production plan and released together. A?simulation of a production flow based on technological routes of real subassemblies was performed. The proposed method of calculating a setup time eliminates the need to determine machine setup time matrices. Among the tested priority rules the best performance was observed in the case of the hierarchical rule that combines similar setup, the earliest due date and the shortest processing time. This rule allowed the setup time per operation to be reduced by 58?% compared to a combination of the earliest due date with the shortest setup and processing time rule and by over 70?% compared to the single shortest processing time rule.     

New approaches to due date assignment in job shops

In this study, two new approaches for due date assignment in job shops are evaluated. Proposed approaches use statistical prediction techniques for dynamic prediction of job flowtimes in a job shop environment as the job arrives to the shop floor. Primary objective of this research is to compare the performance of the proposed due date assignment model (PDDAM) with several conventional due date assignment models (CDDAM). For this purpose, simulation models are developed and comparisons of the PDDAM and CDDAM are made in terms of the mean absolute percent error (MAPE), mean percent error (MPE) and mean tardiness (MT). Simulation experiments showed that for many test conditions, PDDAM dominates CDDAM. Therefore, case by case findings are summarized in the paper.     

The Robustness of Selected Job-shop Dispatching Rules with Respect to Load Balance and Work-flow Structure

Most of the published job-shop research has focused primarily on the identification of dispatching rules which perform well under a variety of shop conditions. Most of the research has assumed that the job shop was an open shop in the sense that a virtually unlimited number of job routeings was possible, as compared to a closed shop, which has much more standardized routeings. Also, most research has further assumed that the capacities at all machines are relatively even, and thus no permanent bottleneck exists. In this research, some of the best-known dispatching rules are studied to determine whether the rules are robust with respect to capacity balance and work-flow structure. In order to be useful in all types of job shop, a rule should perform well regardless of the balance of capacity and work-flow structure in the shop. Results indicate that most of the rules studied are not affected by either of the above factors.     

Analysis of Job Flow-Time in a Job Shop

This paper is concerned with analytical determination of the mean and standard deviation of the job flow-time in a job shop in which the F.C.F.S. dispatching rule is in use. A hypothetical job shop is constructed to generate simulation results for comparison with the analytical results. Consistency of the results reveals the validity of the analytical model. It is also shown that the model is quite robust at a low level of shop load. So the model can be applied to analyze certain types of actual shops.     

Scheduling jobs on parallel machines with sequence-dependent setup times

Consider a number of jobs to be processed on a number of identical machines in parallel. A job has a processing time, a weight and a due date. If a job is followed by another job, a setup time independent of the machine is incurred. A three phase heuristic is presented for minimizing the sum of the weighted tardinesses. In the first phase, as a pre-processing procedure, factors or statistics which characterize an instance are computed. The second phase consists of constructing a sequence by a dispatching rule which is controlled through parameters determined by the factors. In the third phase, as a post-processing procedure, a simulated annealing method is applied starting from a seed solution which is the result of the second phase. In the dispatching rule of the second phase there are two parameters of which the values are dependent on the particular problem instance at hand. Through extensive experiments rules are developed for determining the values of the two parameters which make the priority rule work effectively. The performance of the simulated annealing procedure in the third phase is evaluated for various values of the factors.     

An evaluation of due date,resource allocation,project release,and activity scheduling rules in a multiproject environment

This research examines the performance of due date, resource allocation, project release, and activity scheduling rules in a multiproject environment. The results show that workload sensitive due date rules always provide better due date estimates than workload insensitive due date rules. In contrast, the performance of due date sensitive resource allocation rules is severely affected by due date nervousness. When due date nervousness is not mitigated, the due date insensitive First In System First Served (FISFS) resource allocation rule performs better than the due date sensitive resource allocation rules. Project release rules can, however, mitigate the effect of due date nervousness. Using a simple project release rule, the results show that the due date sensitive Minimum Project Due Date resource allocation rule performs better than FISFS and two other due date sensitive resource allocation rules in many project environments.     

Lead time selection and the behaviour of work flow in job shops

Few studies in job shop scheduling consider dynamic shop load and work flow issues. However, these issues are of importance to management responsible for shop floor control. This research investigates relevant internal performance measures and their relationship to external measures. As well, a new dispatching mechanism that seeks to even out the distribution of jobs in queue is investigated. Results show that a shop load balance index, which takes both shop load levels and load variability into account, has a very strong relationship to the lead times required to maintain a desired level of delivery performance. It appears that good performance based on internal measures is consistent with good performance based on external measures.     

A modified tabu search algorithm for cost-based job shop problem

In this paper, a cost-based job shop problem (JIT-JSP) is proposed to model the multi-order processing procedure in a just-in-time (JIT) environment. The objective of JIT-JSP is to minimize three costs: work-in-process holding cost of half-finished orders, inventory holding cost of finished orders and backorder cost of unfulfilled orders. A modified tabu search (MTS) method is developed to improve the schedule quality by searching the neighbourhood of a feasible schedule iteratively. The MTS method is comprised of three components that help to ensure a more effective searching procedure: neighbourhood structure, memory structure and filter structure. Computational results show that the MTS method significantly improves the initial schedule generated by an arbitrarily selected dispatching rule.     

Job sequencing and due date assignment in a single machine shop with uncertain processing times

This paper considers due date assignment and sequencing for multiple jobs in a single machine shop. The processing time of each job is assumed to be uncertain and is characterized by a mean and a variance with no knowledge of the entire distribution. A heuristic procedure is developed to find job sequence and due date assignment to minimize a linear combination of three penalties: penalty on job earliness, penalty on job tardiness, and penalty associated with long due date assignment. Numerical experiments indicate that the performance of the procedure is stable and robust to job processing time distributions. In addition, the performance improves when the means and variances of job processing times are uncorrelated or negatively correlated or when the penalty of a long due date assignment is significant.     

Adaptive Control Model and Algorithms for the Dynamic Flowshop Scheduling Problem

1.IntroductionProductionschedulingcanbedefinedgenerallyastheallocationoftheresourcesinaproductionsystemovertimetoperformtheoperationsneededtotransformrawmaterialsilltoproducts.Aneffectiveandefficientschedulingsystemisnecessarytowellachievethepotentialsofaproductionfacility.Productionschedulingproblemsareextremelycomplex.Thecomplexityismainlyduetothefollowingtwofeaturesoftheproblem(Liu,1995).InterconnectedDecisions:Thecomponentsofaproductionsystem,e.g.,machines,ma-tenalhandlingdevicesandstora…     

A performance analysis of dispatching rules and a heuristic in static flowshops with missing operations of jobs

An experimental investigation of the performance of dispatching rules and a heuristic for scheduling in static flowshops with missing operations is undertaken in this study. The measure of performance is the minimization of total flow time of jobs. Permutation schedules are generated by using the heuristic for scheduling. General schedules, which can be permutation or non-permutation schedules, are obtained by using dispatching rules. Four dispatching rules, including a new dispatching rule, are considered. Two types of flowshops are studied: one with no missing operations of jobs and another with missing operations of jobs. In the latter type of flowshops, jobs with varying number of missing operations are considered. An extensive investigation of the performance of the dispatching rules and the heuristic is carried out. It is observed that the heuristic minimizes total flow time of jobs more than dispatching rules up to a certain level of missing operations of jobs in flowshops, after which dispatching rules perform better. The performance of the heuristic and the dispatching rules in terms of minimizing the makespan as a secondary measure is also reported.     

Two-Machine Flow Shop Scheduling with Nonregular Criteria

We consider a two-machine flow shop problem with a common due date where the objective is to minimize the sum of functions which penalize early as well as tardy completion of jobs. Since the problem is NP-hard in the strong sense, we investigate some general properties of optimal schedules for the problem, we develop lower and upper bounds, derive dominance criteria, and propose an enumerative algorithm for finding an optimal schedule. The performance of the proposed algorithm together with the influence of the individual components is thoroughly discussed.     

Deterministic/stochastic assumptions in job shops

The study investigates the effects which possibly unrealistic assumptions of accurately predicting operation times may have on relative performance of various job shop dispatching rules as compared with using an assumption of not being able to accurately predetermine such times. The experimental design includes factors dealing with the amount of accuracy in the estimated operation times, job dispatching heuristic rules, and shop loading categories. The stochastic operation times represent two different degrees of inaccuracy; one level reflects an estimated ‘normal’ amount of inaccuracy associated with an experienced predictor (shop foreman) while the other level doubles the amount of variance associated with the ‘normal’ predictor's error. These two stochastic levels are compared to a deterministic level where predetermined operation times are absolutely accurate. Five different heuristic rules are evaluated under six different shop loading levels. General conclusions indicate that an assumption of accurately predetermining actual operation times is not likely to weaken the analysis and impact of the research studies which have been performed using such an assumption. However, a specific conclusion indicates that, for at least one shop loading category, researchers should be careful when extending conclusions based on one operation time assumption to situations involving the other assumption.     

Improving delivery reliability by a new due-date setting rule

We study the dynamic due-date setting problem where the objective is to improve delivery performance. Since the problem is NP-hard, we propose a simple, new, general, heuristic due-date setting procedure called the SL rule. For the classical M/M/1 queuing model, we analytically determine the optimum parameter for the proposed rule to achieve best due-date performance. We then show that the optimized SL rule outperforms the work-content-based TWK rule in terms of fraction tardy, mean tardiness, and mean earliness. Additional numerical and simulation analysis for a range of conditions, covering different shop workload levels and priority regimes, confirms that the proposed rule produces best due-date performance, compared to the work-content-based rule, under most of the conditions studied.     

The role of preparedness in ambulance dispatching

Response time in the emergency medical service is an important performance measure and ambulance dispatching is one of the most important factors affecting the response time. The most commonly used dispatching rule is to send the closest available unit to the call site. However, though dispatching the closest unit enables the service to achieve the minimal response time for the current call, the response times for the next incoming calls may increase if the area where the closest ambulance is currently located has a high call rate, that is the area becomes ill-prepared. A dispatching algorithm based on the preparedness concept was recently proposed. Rather than greedily minimizing each current response time, the dispatching algorithm takes account of future calls by a quantitative definition of preparedness. This study investigates the role of preparedness by examining the performance of the preparedness-based dispatching algorithm as well as by evolving the algorithm in several ways in order to magnify the effectiveness of preparedness consideration. As a result of these efforts, it is found that the consideration of preparedness in ambulance dispatching can provide significant benefits in reducing response time but only when appropriately used.     

An O(n) algorithm for the variable common due date,minimal tardy jobs bicriteria two-machine flow shop problem with ordered machines

We consider the ordinary NP- hard two-machine flow shop problem with the objective of determining simultaneously a minimal common due date and the minimal number of tardy jobs. We present an O(n²) algorithm for the problem when the machines are ordered, that is, when each job has its smaller processing time on the first (second) machine. We also discuss the applicability of the proposed algorithm to the corresponding single-objective problem in which the common due date is given.     

Soft computing optimization methods applied to logistic processes

This paper discusses the methodologies that can be used to optimize a logistic process of a supply chain described as a scheduling problem. First, a model of the system based on a real-world example is presented. Then, a new objective function called Global Expected Lateness is proposed, in order to describe multiple optimization criteria. Finally, three different optimization methodologies are proposed: a classical dispatching rule, and two soft computing techniques, Genetic Algorithms (GA) and Ant Colony Optimization (ACO). These methodologies are compared to the dispatching policy in the real-world example. The results show that dispatching heuristics are outperformed by the GA and ACO meta-heuristics. Further, it is shown that GA and ACO provide statistically identical scheduling solutions and from the optimization performance point of view, it is equivalent to use any of the meta-heuristics.