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.     

A global MILP model for FMS scheduling

Flexible manufacturing systems (FMS) require intelligent scheduling strategies to achieve their principal benefit — combining high flexibility with high productivity. A mixed-integer linear programming model (MILP) is presented here for FMS scheduling. The model takes a global view of the problem and specifically takes into account constraints on storage and transportation. Both of these constrained resources are critical for practical FMS scheduling problems and are difficult to model. The MILP model is explained and justified and its complexity is discussed. Two heuristic procedures are developed, based on an analysis of the global MILP model. Computational results are presented comparing the performance of the different solution strategies. The development of iterative global heuristics based on mathematical programming formulations is advocated for a wide class of FMS scheduling problems.     

Sequential decision procedures for batching and balancing in FMSs

Batching and balancing constitute two of the several scheduling and resource allocation problems important over different time scales in FMS operations. The time scale for batching and balancing is of the order of days to weeks — which puts it between long-term planning and part selection, of the order of months to years, and real-time part entry and dispatching, of the order of minutes. All these scheduling and resource allocation problems have been addressed at the Charles Stark Draper Laboratoty by a common methodology. We have used a sequential decision algorithm, each decision based on optimization of a probabilistic performance criterion designed to trade off whatever and however many competing attributes may be important in the particular problem. This paper discusses the common methodology, and its application to FMS batching and balancing in particular. Our computer program BATCH/BAL which implements the algorithms given here has been the starting point for all the other sequential decision programs subsequently developed at our laboratory.This paper is based in part on work supported by the United States Army Tank Automotive Command under Contract DAAE07-83-C-R084 with the Charles Stark Draper Laboratory, Inc., and in part on work supported under Internal Research and Development at Draper.     

Evaluation of entropy-based dispatching in flexible manufacturing systems

Traditionally, part dispatching has been done using static rules, rules that fail to take advantage of the dynamic nature of today’s manufacturing systems. In modern manufacturing systems, machines carry multiple tools so parts have the option of being machined at more than one machine. This flexibility, termed routing flexibility in the literature, opens up new possibilities for shop floor planners for the scheduling and dispatching of parts.     

An evaluation of value based dispatching rules in a flow shop

Although investment in inventory has been of primary concern in job shops, little attention has been paid to using value-based dispatching rules in an effort to attain satisfactory on-time performance while reducing inventory investment. This paper compares performance based on both time and value measures of three usual time-based rules with six rules which directly incorporate value information in setting priorities. The results indicate that the value-based rules perform their intended function quite well with only slight sacrifice in on-time performance in light to moderately loaded shops. In addition, some of these values rules outperform the best time-based rules on both dimensions in heavily loaded shops.     

Beam search heuristics for quadratic earliness and tardiness scheduling

In this paper, we present beam search heuristics for the single machine scheduling problem with quadratic earliness and tardiness costs, and no machine idle time. These heuristics include classic beam search procedures, as well as filtered and recovering algorithms. We consider three dispatching heuristics as evaluation functions, in order to analyse the effect of different rules on the performance of the beam search procedures. The computational results show that using better dispatching heuristics improves the effectiveness of the beam search algorithms. The performance of the several heuristics is similar for instances with low variability. For high variability instances, however, the detailed, filtered and recovering beam search (RBS) procedures clearly outperform the best existing heuristic. The detailed beam search algorithm performs quite well, and is recommended for small- to medium-sized instances. For larger instances, however, this procedure requires excessive computation times, and the RBS algorithm then becomes the heuristic of choice.     

Job shop scheduling with beam search

Beam Search is a heuristic method for solving optimization problems. It is an adaptation of the branch and bound method in which only some nodes are evaluated in the search tree. At any level, only the promising nodes are kept for further branching and remaining nodes are pruned off permanently. In this paper, we develop a beam search based scheduling algorithm for the job shop problem. Both the makespan and mean tardiness are used as the performance measures. The proposed algorithm is also compared with other well known search methods and dispatching rules for a wide variety of problems. The results indicate that the beam search technique is a very competitive and promising tool which deserves further research in the scheduling literature.     

Queueing network modelling of flexible manufacturing system using mean value analysis

In the present investigation, we develop queueing model for the performance prediction of flexible manufacturing systems (FMSs) with a multiple discrete material-handling devices (MHD). An iterative method has been suggested using mean value analysis (MVA) for the state-dependent routing. Two queueing network models are considered to determine the material-handling device interference. In the first one, we model the interference from the MHD by inflating the station service times but neglect queueing at the MHD. In another network, the queueing for the MHD is taken into consideration. The performance of FMS configuration is obtained by iterating between two networks. The suggested algorithms demonstrate better results than the algorithm used by earlier workers for single MHD. Some performance indices viz. throughput, mean service time, mean waiting time, etc. are obtained. Numerical results are provided to highlight the effect of the system parameters on performance indices, which are further evaluated by using neuro-fuzzy controller system to validate the tactability of soft computing approach.     

An efficient method to determine the optimal configuration of a flexible manufacturing system

A frequently encountered design issue for a flexible manufacturing system (FMS) is to find the lowest cost configuration, i.e. the number of resources of each type (machines, pallets, ...), which achieves a given production rate. In this paper, an efficient method to determine this optimal configuration is presented. The FMS is modelled as a closed queueing network. The proposed procedure first derives a heuristic solution and then the optimal solution. The computational complexity for finding the optimal solution is very reasonable even for large systems, except in some extreme cases. Moreover, the heuristic solution can always be determined and is very close (and often equal) to the optimal solution. A comparison with the previous method of Vinod and Solberg shows that our method performs very well.     

A decision theory based scheduling procedure for single-machine weighted earliness and tardiness problems

We consider the dynamic single-machine scheduling problem where the objective is to minimize the sum of weighted earliness and weighted tardiness costs. A single pass heuristic, based on decision theory, is developed for constructing schedules. The heuristic permits schedules with idle time between jobs and behaves like a dispatching procedure. The performance of the new heuristic is examined using 116 published problems for which the optimum solution is known. Its performance is also investigated using 540 randomly generated problems covering a variety of conditions by comparing it to two well known dispatching procedures, adapted for dynamic early/tardy problems. The results indicate that the heuristic performs very well.     

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.     

An investigation into the relationship of heuristic performance with network-resource characteristics

Constrained resource project management heuristics are analyzed and their performance is assessed related to well defined project types. Such results have shown that using the overall performance measure of a given heuristic can, in some situations, be misleading.An efficient heuristic, which combines resource and criticality factors is also proposed. Computational experiments on a set of 6120 networks varying in size from 45–666 activities, 3 resources, and under different network parameters are reported. The proposed heuristic outperforms the best existing dispatching rules in certain project classes and also on problem sets appearing in the literature.     

A new dispatching rule based genetic algorithm for the multi-objective job shop problem

Hyper-heuristics or “methodologies to choose heuristics” are becoming increasingly popular given their suitability to solve hard real world combinatorial optimisation problems. Their distinguishing feature is that they operate in the space of heuristics or heuristic components rather than in the solution space. In Dispatching Rule Based Genetic Algorithms (DRGA) solutions are represented as sequences of dispatching rules which are called one at a time and used to sequence a number of operations onto machines. The number of operations that each dispatching rule in the sequence handles is a parameter to which DRGA is notoriously sensitive. This paper proposes a new hybrid DRGA which searches simultaneously for the best sequence of dispatching rules and the number of operations to be handled by each dispatching rule. The investigated DRGA uses the selection mechanism of NSGA-II when handling multi-objective problems.     

Multiple Container Packing: A Case Study of Pipe Packing

While the problem of packing single containers and pallets has been thoroughly investigated very little attention has been given to the efficient packing of multiple container loads. Normally in practice a multiple container load is packed by a single container algorithm used in a greedy fashion. This paper introduces the issues involved in multiple container loading. It lays out three different strategies for solving the problem: sequential packing using a single container heuristic, pre-allocating items to the containers and choosing container loads using simultaneous packing models. The principal simultaneous models are pattern selection IP models. We present an application of packing pipes in shipping containers using two pattern selection IP models, a pattern selection heuristic, a sequential greedy algorithm and a pre-allocation method. The experimental results use randomly generated data sets. We discuss several useful insights into the methods and show that for this application the pattern selection methods perform best.     

A technique for on-line sensitivity analysis of flexible manufacturing systems

The recent perturbation analysis approach to discrete event systems is applied to flexible manufacturing systems (FMS). While analytic (queueing) models are useful in preliminary design of such systems, they are not accurate enough at the detailed design/operation stage. Thus, experimentation on detailed simulations or on the actual system has been the way to optimize system performance. Perturbation analysis allows us to derive the sensitivity of system performance, with respect to several design/operating parameters, by observing a single experiment (and without having to actually alter the parameters — often a costly operation). Thus, observation of one experiment can give accurate directions for the improvement of several parameter values. Here we give a simulation example illustrating how perturbation analysis could be used on-line on an FMS to improve its performance, including reducing its operating cost. Experimental results are also presented validating the estimates obtained from this technique.Work supported by U.S. Office of Naval Research Contracts N00014-75-C-0648 and N00014-79-C-0776, and NSF Grant ENG78-15231, at Harvard University.A preliminary version of this paper appeared in the Proc. 1st ORSA/TIMS Conf. on Flexible Manufacturing Systems, August 1984. This version includes two appendices, which relate to implementation of the technique described in the main body of the paper.     

Numerical performance of approximate queuing formulae with application to flexible manufacturing systems

This paper calls attention to two of the more successful queuing approximation formulae — one by Kramer and one by Marchal. The analytic solution of a range of single server Erlang cases is compared to the two approximation formulae. Then a family of H₂/M/1 cases is similarly considered. Maximum errors are seen to be about three percent. The Kramer formula seems to be better when the interarrival coefficient of variation is less than 0.66 and the Marchal formula is better for larger interarrival coefficients of variation. Finally, a multiserver refinement function (the ratio of G/G/1 results to M/M/1 results) is proposed to scale M/M/s as an approximation for G/G/s. In most of these multiple channel cases, the maximum error is less than six percent. The last section of this paper presents a simple, representative FMS. It is modelled as an open queuing network. Then the approximation procedure is applied node by node to illustrate the estimation of system performance measures such as machine utilizations and throughput.     

Cooperative dispatching – exploiting the flexibility of an FMS by means of incremental optimization

We present a new control scheme for releasing parts into a flexible manufacturing system (FMS) that is based on incremental optimization. Our objective is to exploit the available routing flexibility of parts in an enhanced manner by viewing part release as an assignment problem using system status information. In particular, we propose an “intelligent” part release mechanism with some look-ahead and optimization features in order to allow for optimization-based “cooperation” of workcenters. The cooperative dispatching concept is implemented in an object-oriented computer simulation model, and experiments with a varying degree of average routing flexibility are performed. The experimental results are used for a statistical analysis of the benefits of cooperative dispatching versus the common approach of standard dispatching. Finally, we investigate the robustness of the presented FMS control scheme in the case of random machine breakdowns.     

A supervisory control paradigm for real-time control of flexible manufacturing systems

Most of the current academic flexible manufacturing system (FMS) scheduling research has focused on the derivation of algorithms or knowledge-based techniques for efficient FMS real-time control. Here, the limitations of this view are outlined with respect to effective control of actual real-time FMS operation. A more realistic paradigm for real-time FMS control is presented, based on explicit engineering of human and automated control functions and system interfaces. To illustrate design principles within the conceptual model, an example of algorithmic and operator function models for a specific real-time FMS control problem are developed.Portions of this paper have appeared in: Proc. 2nd ORSA/TIMS Conf. on Flexible Manufacturing Systems: Operations Research Models and Applications, Ann Arbor, Michigan, August 12–15, 1986, and Proc. 1986 Int. Conf. on Systems, Man, and Cybernetics, Atlanta, Georgia, October 14–17, 1986.This research was supported in part by the New Faculty Research Program of the Georgia Institute of Technology.     

Cyclic scheduling for F.M.S.: Modelling and evolutionary solving approach

This paper concerns the domain of flexible manufacturing systems (FMS) and focuses on the scheduling problems encountered in these systems. We have chosen the cyclic behaviour to study this problem, to reduce its complexity. This cyclic scheduling problem, whose complexity is NP-hard in the general case, aims to minimise the work in process (WIP) to satisfy economic constraints. We first recall and discuss the best known cyclic scheduling heuristics. Then, we present a two-step resolution approach. In the first step, a performance analysis is carried out; it is based on the Petri net modelling of the production process. This analysis resolves some indeterminism due to the system’s flexibility and allows a lower bound of the WIP to be obtained. In the second step, after a formal model of the scheduling problem has been given, we describe a genetic algorithm approach to find a schedule which can reach the optimal production speed while minimizing the WIP. Finally, our genetic approach is validated and compared with known heuristics on a set of test problems.     

A dispatching algorithm for parallel machines with rework processes

This paper presents a parallel machine scheduling problem with rework probabilities, due-dates and sequence-dependent setup times. It is assumed that rework probability for each job on a machine can be given through historical data acquisition. Since the problem is NP-hard in the strong sense, a heuristic algorithm is presented, which finds good solutions. The dispatching algorithm named MRPD (minimum rework probability with due-dates) is proposed in this paper focusing on the rework processes. The performance of MRPD is measured by the six diagnostic indicators: total tardiness, maximum lateness, mean flow-time, mean lateness, the number of reworks and the number of tardy jobs. A large number of test problems are randomly generated to evaluate the performance of the proposed algorithm. Computational results show that the proposed algorithm is significantly superior to existing dispatching algorithms for the test problems.