Heuristics and sequence-dependent set-up jobs in flow line cells

A key operational issue in cellular manufacturing systems is the scheduling of jobs within a family at each cell. Sequence-dependent set-up times during changeovers from one job to another afford scope for the exploitation of similarities at this stage to minimize the time spent on set-ups. This paper proposes heuristics for scheduling jobs within a part family by identifying subfamilies and sequencing them to improve the use of machines within a cell and to reduce the tardiness as well as the number of tardy jobs. The proposed heuristic, when evaluated by comparison with existing benchmark heuristics, yielded encouraging results.     

A Multifactor Priority Rule for Jobshop Scheduling Using Computer Search

Priority rules are widely used in jobshop scheduling to determine the sequence in which jobs are to be processed. The research in this area has been directed at developing generally applicable priority rules. This paper presents a method for determining an effective priority rule specific to the jobshop scheduling problem to be solved. First, a generalized objective function is formulated which is the sum of costs of tardiness, carrying in-process inventory and machine idleness. Second, a multifactor priority rule is developed which is a weighted average of four factors used in simple priority rules. Third, a method is presented for using a computer search technique to determine the best weights to use in the priority rule. Finally, a computer simulation for testing this approach versus using other priority rules is described and the experimental results are reported.     

Simulation modelling and analysis of scheduling in robotic flexible assembly cells using Taguchi method

Due to increasing competition in the developing global economy, today’s companies are facing greater challenges than ever to employ flexible manufacturing systems (FMS) capable of dealing with unexpected events and meeting customers’ requirements. One such system is robotic flexible assembly cells (RFACs). There has been relatively little work on the scheduling of RFACs, even though overall scheduling problems of FMS have attracted significant attention. This paper presents Taguchi optimisation method in conjunction with simulation modelling in a new application for dynamic scheduling problems in RFACs, in order to minimise total tardiness and number of tardy jobs (N_T). This is the first study to address these particular problems. In this study, Taguchi method has been used to reduce the minimum number of experiments required for scheduling RFACs. These experiments are based on an L9 orthogonal array with each trial implemented under different levels of scheduling factors. Four factors are considered simultaneously: sequencing rule, dispatching rule, cell utilisation and due date tightness. The experimental results are analysed using an analysis of mean to find the best combination of scheduling factors and an analysis of variance to determine the most significant factors that influence the system’s performance. The resulting analysis shows that this proposed methodology enhances the system’s scheduling policy.     

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.     

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

Experimental investigation of FMS machine and AGV scheduling rules against the mean flow-time criterion

Although a significant amount of research has been carried out in the scheduling of flexible manufacturing systems (FMSs), it has generally been focused on developing intelligent scheduling systems. Most of these systems use simple scheduling rules as a part of their decision process. While these scheduling rules have been investigated extensively for a job shop environment, there is little guidance in the literature as to their performance in an FMS environment. This paper attempts to investigate the performances of machine and AGV scheduling rules against the mean flow-time criterion. The scheduling rules are tested under a variety of experimental conditions by using an FMS simulation model.     

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.     

An application of discrete-event simulation to on-line control and scheduling in flexible manufacturing

The on-line control and scheduling of flexible manufacturing systems has been a major interest in the production research area since these systems first appeared. In this paper, a scheduling algorithm is described which employs discrete simulation in combination with straightforward part dispatching rules in a dynamic fashion. The result is that, instead of scheduling being planned ahead of time and then being applied to a rapidly changing system, a dispatching rule is determined for each short period just before the implementation time occurs. In the long run, the algorithm combines various dispatching rules in response to the dynamic status of the system. The algorithm is described in detail. The efficacy of the algorithm is discussed and demonstrated on a prototype system.     

Priority scheduling with cost considerations

Although many articles have been published on the general priority scheduling problem, very few have been concerned with directly minimizing costs. The few studies which do consider overall costs do not use these costs in establishing a job's priority in the queue. This paper investigates how the time and cost performance of jobs are affected by the use of a rule which directly considers costs. A simulation model of a hypothetical job shop is used to examine several of these cost rules, as well as some common rules concerned with the timeliness of jobs. Performance measures include both time-oriented and cost-oriented measures. The results indicate that rules which directly consider costs (or profit) may prove practical for a manager where minimization of WTP and maximization of ROT are the primary and secondary objectives of the company     

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.     

A two-layer dynamic scheduling method for minimising the earliness and tardiness of a re-entrant production line

This study focuses on the dynamic scheduling problem of a re-entrant production line, in which all of the parts are assumed to have the same processing routes and be processed on every machine. A two-layer dynamic scheduling method is proposed for the dynamic scheduling of the re-entrant line with the objective of minimising total earliness and tardiness. This method consists of two layers. The top layer is to select the appropriate scheduling policy, and the bottom layer is to generate the scheduling by using the policy selected in the top layer. In the top layer, three different rules are constructed for selecting scheduling policies, namely the lateness comparison rule, the lateness variation comparison rule, and the equal interval switching rule. In the bottom layer, three different scheduling policies are proposed to generate the real-time scheduling for manufacturing, namely the FCFS (first come first service) scheduling policy, the PI (proportional-integral) scheduling policy, and the fuzzy PI scheduling policy. Considering that the real-time status of manufacturing changes constantly, it is necessary to switch among different scheduling policies to adapt to this change. Numerical experiments are performed in the situations with and without urgent jobs. The results show that the proposed two-layer dynamic scheduling method outperforms any single scheduling policy (e.g., the FCFS policy, the PI policy and the fuzzy PI policy) for the dynamic scheduling of a re-entrant production line.     

Real-world extensions to scheduling algorithms based on lagrangian relaxation

Recently, efficient scheduling algorithms based on Lagrangian relaxation have been proposed for scheduling parallel machine systems and job shops. In this article, we develop real-world extensions to these scheduling methods. In the first part of the paper, we consider the problem of scheduling single operation jobs on parallel identical machines and extend the methodology to handle multiple classes of jobs, taking into account setup times and setup costs. The proposed methodology uses Lagrangian relaxation and simulated annealing in a hybrid framework. In the second part of the paper, we consider a Lagrangian relaxation based method for scheduling job shops and extend it to obtain a scheduling methodology for a real-world flexible manufacturing system with centralized material handling. This research was supported in part by the Office of Naval Research and the Department of Science and Technology grant N00014-93-1017.     

An efficient priority rule for scheduling job shops to minimize mean tardiness

The ability to respond quickly to customer demands is a key factor in successfully competing in today's globally competitive markets. Thus, meeting due dates could be the most important goal of scheduling in many manufacturing and service industries. Meeting due dates can naturally be translated into minimizing job tardiness. In this paper we present a priority rule for dynamic job shop scheduling that minimizes mean job tardiness. The rule is developed based on the characteristics of existing dispatching rules. With job due dates set by the generalized total work content rule, the computational results of simulation experiments show that the proposed dispatching rule consistently, and often, significantly outperforms a number of well-known priority rules in the literature. The proposed rule is also robust being the best or near-best rule for reducing the mean flowtime, for all the shop load levels and due date tightness factors tested.     

A priority scheduling approach for flexible job shops with multiple process plans

This paper considers the job shop scheduling problem with alternative operations and machines, called the flexible job shop scheduling problem. As an extension of previous studies, operation and routing flexibilities are considered at the same time in the form of multiple process plans, i.e. each job can be processed through alternative operations, each of which can be processed on alternative machines. The main decisions are: (a) selecting operation/machine pair; and (b) sequencing the jobs assigned to each machine. Since the problem is highly complicated, we suggest a practical priority scheduling approach in which the two decisions are done at the same time using a combination of operation/machine selection and job sequencing rules. The performance measures used are minimising makespan, total flow time, mean tardiness, the number of tardy jobs, and the maximum tardiness. To compare the performances of various rule combinations, simulation experiments were done on the data for hybrid systems with an advanced reconfigurable manufacturing system and a conventional legacy system, and the results are reported.     

Performance evaluation of cellular layouts: Extension to DRC system contexts

This study involves a comparison of the performance of functional layouts (FL) and cellular manufacturing (CM) systems in a dual-resource-constrained (DRC) system context. Past studies of FL and CM have been based mostly on single-resource-constrained (SRC) systems. Recent studies have included labour-related factors, but have assumed high labour flexibility levels, and shown the superiority of CM. In this study we assume more realistic levels of labour flexibility, and factors such as lot size, set-up reduction, labour assignment and transfer rule, and scheduling rules. The parameter range in which CM can outperform efficiently operated FL, in a DRC context, are indicated.     

Workshop scheduling using practical (inaccurate) data Part 1: The performance of heuristic scheduling rules in a dynamic job shop environment using a rolling time horizon approach

This paper is a report on a simulation study to investigate the performance of a number of scheduling rules on the basis of a rolling time horizon approach for a dynamic job shop environment. The performance measure considered is an economic objective which includes the main costs involved in a scheduling decision. The first purpose of the study was to find the best scheduling rule and the second to investigate the effects of the rescheduling interval on performance and examine whether there is a policy that can always improve performance. The simulation study, which is part of a larger project on practical workshop scheduling, has been carried out under widely varying conditions in terms of due date tightness, shop load level, and shop load balance level. The results show that a recently developed scheduling rule, SPT-C/R, is the most appropriate scheduling rule in minimizing overall cost and that the relationship between performance and rescheduling interval can be shown.     

Cellular manufacturing: its impact on the total factory

This paper compares a factory structured as a traditional job shop with the same factory structured as a hybrid factory containing a cellular manufacturing unit. The comparison is based on job shop simulation using differing combinations of capacities, allocations of jobs between the cell and the rest of the factory and levels of productivity improvements achieved in the cell. Performance is evaluated in terms of flow times and delays for the cell, the non-cell remainder of the factory and for the normal functional factory. The simulation model was designed to eliminate possible confounding issues of machine reliability, operator skill, unique manufacturer specific part characteristics, factory layout and different scheduling techniques. The result is a systematic evaluation of cellular manufacturing, some general conclusions as to the particular circumstances that favour the use of cells and a set of implications for management practice.     

An Evaluation of Scheduling Policies in a Dual Resource Constrained Assembly Shop

The purpose of this paper is to evaluate scheduling policies for the production of assembled products in an assembly shop. The scheduling policies examined include duedate assignment, labor assignment and item sequencing rules. The sensitivity of these rules to product structure is also considered. The data for analysis is generated by a SLAM II simulation model of a hypothetical dual constrained assembly shop operation. The 2·3·3·3 complete factorial experiment is analyzed by an ANOVA procedure to statistically determine whether job structure, duedate assignment rule, labor assignment rule and item sequencing rule or their interaction significantly affect the root mean square of tardiness of jobs completed by the assembly shop. Further analysis to identify where significant differences in performance occurs is conducted via Tukey multiple comparison tests and general linear contrasts.     

An effective heuristic for adaptive control of job sequences subject to variation in processing times

Variation in sequential task processing times is common in manufacturing systems. This type of disturbance challenges most scheduling methods since they cannot fundamentally change job sequences to adaptively control production performance as jobs enter the system because actual processing times, are not known in advance. Some research literature indicates that simple rules are more suitable than algorithmic scheduling methods for adaptive control. In this work, a ‘state space – average processing time’ (SS-APT) heuristic is proposed and compared to four most commonly used scheduling rules and two well-established heuristics based on Taillard’s benchmarks. It is shown that the adaptive control is made possible under variation in processing times given the flexibility and strong performance of the SS-APT heuristic, especially for work-in-process inventory control.