A study on the performance of scheduling rules in buffer-constrained dynamic flowshops

Most studies on scheduling in manufacturing systems using dispatching rules deal with jobshops, while there are only few reports dealing with dynamic flowshops. It is known that the performance of many dispatching rules in dynamic jobshops is different from that in dynamic flowshops. Moreover, many research reports assume that there are no buffer constraints in the shop, and even those reports dealing with buffer-constrained shops present the evaluation of existing dispatching rules for unconstrained shops in the context of buffer constraints with the consideration of a limited number of objectives of scheduling. In this study, we deal with the problem of scheduling in dynamic flowshops with buffer constraints. With respect to different time-based objectives, the best dispatching rules for scheduling in unconstrained shops have been identified from the existing literature. In addition, two new dispatching rules specially designed for flowshops with buffer constraints are proposed. All dispatching rules under consideration are evaluated in dynamic flowshops with buffer constraints on the basis of an extensive simulation study covering different levels of buffer constraints, shop load or utilization, and missing operations in flowshops. The proposed rules are found to perform better than the existing dispatching rules in buffer-constrained flowshops with respect to many measures of performance.     

Dynamic rules for due-date assignment

This paper presents two new dynamic due-date assignment rules which utilize shop congestion information. The new rules estimate job flowtime based on a sampling of recently completed jobs. These rules are compared with other established flowtime estimate models on the criterion of due-date performance via computer simulation. To evaluate the robustness of the rules, an experimental design with three different queue sequencing heuristics and two different shop balance levels was used. The results of this investigation clearly indicate that flowtimes from recently completed jobs provide very useful information for establishing effective due-dates in a job shop environment. In addition it is shown how the use of particular sequencing rules greatly increases the precision of flowtime estimates.     

Dispatching rules for scheduling in assembly jobshops - Part 1

Research on jobshop scheduling has tended to concentrate on the development of dispatching rules for jobs that are independent, i.e. single-component jobs. However, in real-life situations, many jobs involve assembly operations that require scheduling of multiple components through the jobshop where both serial and parallel operations take place. In this two-part paper, we consider the problem of scheduling in assembly jobshops, i.e. jobshops that manufacture multi-level assembly jobs. The development of new and efficient dispatching rules with a view to address various measures of performance related to flowtime and staging delay of jobs is first undertaken. A new concept, called 'operation synchronization date' is introduced and made use of in the new dispatching rules. The best existing dispatching rules and the proposed dispatching rules are relatively evaluated by an exhaustive simulation study. The results indicate that the proposed rules emerge to be superior to the existing ones for most measures of performance.     

Dispatching rules for scheduling in assembly jobshops - Part 2

In this part of the paper, we present the development and evaluation of dispatching rules for scheduling in jobshops manufacturing multi-level assembly jobs with the performance measures reated to tardiness. We present a new definition of 'operation due date' in the context of assembly jobs and use it in the development of dispatching rules. A simulation study is carried out to evaluate the performances of the existing and the proposed dispatching rules with respect to different measures of tardiness. We also measure their performances with respect to different measures of flowtime and staging delays. The results of the study indicate that the proposed rules perform better than the existing rules.     

Heuristic Algorithms for Multistage Flowshop Scheduling Problem

This paper describes three heuristic algorithms for seeking a quick and near optimal solution to the n-job M-machine flowshop scheduling problem where jobs are processed on all machines in the same order, and the objective is to minimize either the mean flowtime or the maximum flowtime (make-span). The proposed heuristic algorithms are extensions of the heuristic rules of the author and are comparatively more effective in finding the optimal or near optimal solution to the problem. Computational experience pertaining to the effectiveness of proposed heuristic algorithms is discussed, indicating that the solutions obtained by proposed heuristic algorithms are compared to the Campbell-Dudek-Smith algorithm.     

A heuristic for scheduling in flowshop and flowline-based manufacturing cell with multi-criteria

The problem of scheduling in flowshop and flowline-based manufacturing cell is considered with the bicriteria of minimizing makespan and total flowtime of jobs, The formulation of the scheduling problems for both the flowshop and the flowline-based manufacturing cell is first discussed. We then present the development of the proposed heuristic for flowshop scheduling. A heuristic preference relation is developed as the basis for the heuristic so that only the potential job interchanges are checked for possible improvement with respect to bicriteria, The proposed heuristic algorithm as well as the existing heuristic are evaluated in a large number of randomly generated large-sized flowshop problems. We also investigate the effectiveness of these heuristics with respect to the objective of minimizing total machine idletime. We then modify the proposed heuristic for scheduling in a cell, and evaluate its performance.     

A computational study of heuristics for two-stage flexible flowshops

We consider the scheduling of two-stage flexible flowshops. This manufacturing environment involves two machine centres representing two consecutive stages of production. Each machine centre is composed of multiple parallel machines. Each job has to be processed serially through the two machine centres. In each machine centre, a job may be processed on any of the machines. There are n independent jobs to be scheduled without preemption. The jobs can wait in between the two machine centres and the intermediate storage is unlimited. Our objective will be to minimize the maximum completion time of the jobs. We formulate the problem as a mixed integer program. Given this problem class is NP-hard in the strong sense, we present three lower bounds to estimate the optimal solution. We then propose a sequence-first, allocate-second heuristic approach for its solution. We heuristically decompose the problem by first creating a priority list to order the jobs and then assign the jobs to the available machines in each machine centre based on this order. We describe seven rules for the sequencing phase. The assignment phase consists of a heuristic which attempts to minimize each partial schedule length while looking ahead at the future assignment of the currently unscheduled jobs. The computational performance of the heuristic approach was evaluated by comparing the value of each heuristic variant to the best among the three lower bounds. Its effectiveness was tested on scenarios pertinent to flexible flowshop environments, such as cellular manufacturing, by conducting a computational study of over 3400 problems. Our computational results indicate that the most effective approach used Johnson's rule to provide the priority list for job assignment. This provided integrality gaps which on the average were less than 0·73%.     

A note on scheduling jobs with missing operations in permutation flow shops

Flowshop scheduling problems are usually handled as permutation flowshops because of computational complexity although the technical framework in realworld problems often allows that jobs pass each other. Having a missing operation of a job on a machine, this job passing becomes a natural way to process jobs unless the underlying system is not an inflexible flow-line. However, when scheduling, missing operations are usually handled as zero processing time operations not allowing for any job passing. It is shown that even permitting job passing for missing operations while keeping the permutation constraint improves total completion time only under rather specific circumstances. We propose 'partial permutation flowshop sequencing' to overcome these specific formal requirements with respect to the real-world problem setting.     

Scheduling in dynamic assembly job-shops with jobs having different holding and tardiness costs

Most studies on scheduling in dynamic job-shops assume that the holding cost of a job is given by the flowtime of the job and that the tardiness cost of a job is given by the tardiness of the job. In other words, unit holding and unit tardiness costs of a job are assumed. However, in reality, such an assumption need not hold, and it is quite possible that there are different costs for holding and tardiness for different jobs. In addition, most studies on job-shop scheduling assume that jobs are independent and that no assembly operations exist. The current study addresses the problem of scheduling in dynamic assembly job-shops (manufacturing multilevel jobs) with the consideration of different holding and tardiness costs for different jobs. An attempt is made to develop efficient dispatching rules by incorporating the relative costs of holding and tardiness of jobs in the form of scalar weights. The primary objective of scheduling considered here is the minimization of the total scheduling cost consisting of the sum of holding and tardiness costs. The performance of the scheduling rules in minimizing the individual components of total scheduling cost is also observed. The results of an extensive simulation study on the performance of different dispatching rules show that the proposed rules are effective in minimizing the means and maximums of the primary measure, and are quite robust with respect to different job structures and experimental settings.     

The stochastic flowshop makespan. Part I. Some general results for the buffered case

This, the first part of a two-part study, considers stochastic flowshops with infinite bufferage. There is a discussion of the modes into which the jobs may fall and expressions are developed for the associated probabilities and makespan-contributions. Various ‘symmetries’ are noted. Exact results are presented for cases up to and including three jobs through three machines when these service times are exponentially distributed and consideration is given to the varying of the distribution parameters. Part II, which follows in the next issue and which should be read in conjunction, deals with the unbuffered flowshop and discusses the well-known ‘bowl effect’     

Bottleneck-based heuristics to minimize tardy jobs in a flexible flow line with unrelated parallel machines

This paper develops new bottleneck-based heuristics with machine selection rules to solve the flexible flow line problem with unrelated parallel machines in each stage and a bottleneck stage in the flow line. The objective is to minimize the number of tardy jobs in the problem. The heuristics consist of three steps: (1) identifying the bottleneck stage; (2) scheduling jobs at the bottleneck stage and the upstream stages ahead of the bottleneck stage; (3) using dispatching rules to schedule jobs at the downstream stages behind the bottleneck stage. A new approach is developed to find the arrival times of the jobs at the bottleneck stage, and two decision rules are developed to schedule the jobs on the bottleneck stage. This new approach neatly overcomes the difficulty of determining feasible arrival times of jobs at the bottleneck stage. In order to evaluate the performance of the proposed heuristics, six well-known dispatching rules are examined for comparison purposes. Six factors are used to design 729 production scenarios, and ten test problems are generated for each scenario. Computational results show that the proposed heuristics significantly outperform all the well-known dispatching rules. An analysis of the experimental factors is also performed and several interesting insights into the heuristics are discovered.     

Family based dispatching with batch availability

Family based dispatching rules seek to lower set-up frequencies by grouping (batching) similar types of jobs for joint processing. Hence shop flow times may be improved, as less time is spent on set-ups. Motivated by an industrial project we study the control of machines with batch availability, i.e. all the jobs of the same batch become available for processing and leave the machine together. So far the literature seems to have neglected this type of shop by restricting its focus on machines with item availability, i.e. assuming machine operations concern single jobs. We address this gap by proposing extensions to existing family based dispatching rules. Extended rules are tested by an extensive simulation study. Best performance is found for non-exhaustive rules, which allow for alternative choices of batch size. Performance gains are highest for low set-up to run-time ratios and/or high workloads.     

The Sensitivity of the Relative Effectiveness of Job Shop Dispatching Rules with Respect to Various Arrival Distributions

The study investigates the effects which various arrival rate distributions may have on the relative success of implementing various job shop heuristic dispatching rules. Sixteen different arrival rate distributions are tested on ten dispatching rules. General conclusions imply that the distribution with respect to shape and range of the arrival rate for incoming jobs is not a significant variable in evaluating the relative effectiveness of dispatching rules.     

Automated Two-machine Flowshop Scheduling: A Solvable Case

This paper considers new flowshop scheduling problems related to automated manufacturing systems in which n jobs are processed on two machines M_a and M_b in this order. The job transportation between two machines is done by a single automated guided vehicle (AGV), and is crucial because no machine has buffer storage for work-in-process (WIP) and hence a machine cannot release a finished job until the empty AGV becomes available at that machine, while the AGV cannot transfer an unfinished job to a machine until the machine is empty. O(n³) algorithms are given in this paper to find optimal sequences of n jobs that minimize their maximum completion time (i.e., makespan). Some numerical results are also given to evaluate the effect of computing optimal sequences.     

A beam search-based algorithm and evaluation of scheduling approaches for flexible manufacturing systems

This paper presents a new algorithm for the flexible manufacturing system (FMS) scheduling problem. The proposed algorithm is a heuristic based on filtered beam search. It considers finite buffer capacity, routing and sequence flexibilities and generates machine and automated guided vehicle (AGV) schedules for a given scheduling period. A new deadlock resolution mechanism is also developed as an integral part of the proposed algorithm. The performance of the algorithm is compared with several machine and AGV dispatching rules using mean flow time, mean tardiness and makespan criteria. It is also used to examine the effects of scheduling factors (i.e., machine and AGV load levels, routing and sequence flexibilities, etc.) on the system performance. The results indicate that the proposed scheduling algorithm yields considerable improvements in system performance over dispatching rules under a wide variety of experimental conditions.     

Solving the n-job 3-stage flexible flowshop scheduling problem using an agent-based approach

In this paper, a general methodology of agent-based manufacturing systems scheduling, incorporating game theoretic analysis of agent cooperation is presented to solve the n-job 3-stage flexible flowshop scheduling problem. The flowshops are flexible in the sense that a job can be processed by any of the identical machines at each stage. Our objective is to schedule a set of n jobs so as to minimize the makespan. We perform error bound analysis using the lower bound estimates developed in the literature as a datum for comparing the agent-based scheduling solutions with other heuristic solutions. The results of the evaluation show that the agent-based scheduling approach outperforms existing heuristics for the majority of the testing problems.     

Family based dispatching in manufacturing networks

Intrinsic to family based dispatching is the grouping of similar types of jobs in front of a machine for joint processing. Machine flow times may be improved in this way, as less time is spent on set-ups. Our observations in practice, however, suggest that family based dispatching may result in a bulky arrival pattern for successor manufacturing stages, thereby causing additional delay. So far, literature seems to neglect this effect. To explore this issue we develop queuing theoretical approximations of flow times for a simple two-stage shop. It appears that the optimal batch size for the shop is typically smaller than the optimal batch size for the batch machine. Furthermore, we propose extensions to existing dispatching rules by using information on successor stages. Existing and new extended rules are tested by an extensive simulation study. In line with the queuing theoretical analysis the outcomes indicate that exhaustive rules – assuming batch size to be equal to family queue length – are clearly outperformed by non-exhaustive rules – allowing for smaller batches. Moreover, results show that the inclusion of local information on successor stages in rule decision making improves shop flow times.     

A comparative study of priority dispatching rules in a hybrid assembly/job shop

This paper reports on research conducted on the use of priority dispatching rules in a hybrid assembly/job shop which manufactures both single-component and multiple-component products. A simulation model was constructed and a large stale experiment performed. Statistical analysis of the simulation results indicated significant impact of both the priority rules tested, and the product-mix considered on shop performance.

Among the 12 priority rules tested, the SPT (shortest processing time) rule and the ASMF-SPT (assembly jobs first with SPT as tie-breaker) rule performed very well with respect to measures like lateness, flow time, tardiness, staging time, and percent of jobs tardy. These findings lead to further investigation of a combined priority rule, MIXED, which implements the ASMF-SPT rule at all machine centres that process components of assembly jobs, and the SPT rule at the remaining machine centres which process non-component jobs. The additional research results yielded evidence that the MIXED rule can reduce the staging time of the SPT rule, and yielded betrer results than the ASMF-SPT rule with regard to other performance measures.

The most interesting finding, however, was the small variation in flow time distribution resulting from use of the MIXED rule when there were more assembly jobs. In an MRP environment, it is especially desirable to have a priority dispatching rule resulting in minimum variation in individual flow times which allows the replenishment lead times to be estimated with greater accuracy.     

Launching and dispatching strategies for multi-criteria control of closed manufacturing systems with flexible routeing capability

In this paper, we study the problems of launching and dispatching of parts in closed manufacturing systems with flexible routeing. For the manufacturing systems being operated against multiple performance criteria, we postulate that controlling different aspects of the operational control strategy to meet one single performance criterion would improve overall system performance. It is suggested that to achieve production rates, launching rules be utilized and to affect flowtime, dispatching rules be manipulated. Also, for measurement of routeing flexibility, an entropic measure of flexibility is refined. The entropy-based rule is then compared with the dispatching rules commonly used in the industry. Control strategies are developed for a test system and it is shown that a hierarchical control strategy works best when multiple performance criteria are of interest.     

Dynamic adjustment of dispatching rule parameters in flow shops with sequence-dependent set-up times

Decentralised scheduling with dispatching rules is applied in many fields of production and logistics, especially in highly complex manufacturing systems. Since dispatching rules are restricted to their local information horizon, there is no rule that outperforms other rules across various objectives, scenarios and system conditions. In this paper, we present an approach to dynamically adjust the parameters of a dispatching rule depending on the current system conditions. The influence of different parameter settings of the chosen rule on the system performance is estimated by a machine learning method, whose learning data is generated by preliminary simulation runs. Using a dynamic flow shop scenario with sequence-dependent set-up times, we demonstrate that our approach is capable of significantly reducing the mean tardiness of jobs.