Performance-based dynamic scheduling model for flexible manufacturing systems

A performance-based dynamic scheduling model for random flexible manufacturing systems (FMSs) is presented. The model is built on the mathematical background of supervisory control theory of discrete event systems. The dynamic FMS scheduling is based on the optimization of desired performance measures. A control theory-based system representation is coupled with a goal programming-based multi-criteria dynamic scheduling algorithm. An effectiveness function, representing a performance index, is formulated to enumerate the possible outputs of future schedules. Short-term job scheduling and dispatching decisions are made based on the values obtained by optimizing the effectiveness function. Preventive actions are taken to reduce the difference between actual and desired target values. To analyse the real-time performance of the proposed model, a software environment that included various Visual Basic Application® modules, simulation package Arena®, and Microsoft Access® database was developed. The experimentation was conducted (a) to determine the optimum look-ahead horizons for the proposed model and (b) to compare the model with conventional scheduling decision rules. The results showed that the proposed model outperformed well-known priority rules for most of the common performance measures.     

Loading and scheduling for flexible manufacturing systems with controllable processing times

This study addresses the problem of determining the allocation of operations and their tools to machines, the operation processing times and the allocation/sequence of the parts to be processed on each machine for flexible manufacturing systems with controllable processing times. Tool lives, tool copies and tool sharing are also considered. An integer programming model is developed for the objective of minimizing the sum of operation processing and tardiness costs. Then, iterative algorithms are proposed that solve the two subproblems iteratively, where the loading subproblem is solved by a modified bin packing algorithm under initial processing times and the resulting scheduling subproblem is solved by a priority scheduling method while modifying the loading plans and operation processing times iteratively. Computational experiments were carried out, and the results are reported.     

Design and scheduling of hybridmulti-cell flexible manufacturing systems

The objective of this paper is to minimize machine duplication by increasing its utilization, minimize intercell moves, simplify the scheduling problem and increase the flexibility of the manufacturing system. An integrated approach of design and scheduling alternative hybrid multi-cell flexible manufacturing systems (MCFMSs) in four steps will be presented in this paper. The first step is the implementation of branch and bound techniques which provide tools to design group technology (GT) cells. The second step is balancing the inter-cell workload of GT cells which leads to a hybrid MCFMS with better utilization of the machines. The problem of the exception machines and their utilization and workload balance will be solved within the MCFMScentre. Thus the performance of GT cells can be improved by transferring workloads from a congested (bottleneck) machine in one cell to an alternative one, a less congested (exception) machine in another cell within a group of GT cells forming a MCFMS centre. The third step is the group scheduling; a proposed heuristic method will be used for the scheduling of a family of parts with the objective of minimizing the maximum completion time of each part. The problem of scheduling under MCFMS can be reduced by considering the scheduling of each family of parts. Finally, the flexibility of the system will be enhanced by selecting appropriate machine tools and flexible material handling equipments. This approach is both effective and efficient-it has generated a hybrid MCFMS centre which includes several alternatives, for some benchmark problems in much shorter time than algorithms previously reported in the literature. In addition, the method is conceptually simple and easy to implement.     

Deadlock-free scheduling in flexible manufacturing systems using Petri nets

This paper addresses the deadlock-free scheduling problem in Flexible Manufacturing Systems. An efficient deadlock-free scheduling algorithm was developed, using timed Petri nets, for a class of FMSs called Systems of Sequential Systems with Shared Resources (S 4 R). The algorithm generates a partial reachability graph to find the optimal or near-optimal deadlock-free schedule in terms of the firing sequence of the transitions of the Petri net model. The objective is to minimize the mean flow time (MFT). An efficient truncation technique, based on the siphon concept, has been developed and used to generate the minimum necessary portion of the reachability graph to be searched. It has been shown experimentally that the developed siphon truncation technique enhances the ability to develop deadlock-free schedules of systems with a high number of deadlocks, which cannot be achieved using standard Petri net scheduling approaches. It may be necessary, in some cases, to relax the optimality condition for large FMSs in order to make the search effort reasonable. Hence, a User Control Factor (UCF) was defined and used in the scheduling algorithm. The objective of using the UCF is to achieve an acceptable trade-off between the solution quality and the search effort. Its effect on the MFT and the CPU time has been investigated. Randomly generated examples are used for illustration and comparison. Although the effect of UCF did not affect the mean flow time, it was shown that increasing it reduces the search effort (CPU time) significantly.     

Integrated scheduling and tool management in flexible manufacturing systems

A multistage algorithm is proposed that will solve the scheduling problem in a flexible manufacturing system by considering the interrelated subproblems of processing time control, tool allocation and machining conditions optimization. The main objective of the proposed algorithm is to minimize total production cost consisting of tooling, operational and tardiness costs. The proposed integrated approach recognizes an important trade-off in automated manufacturing systems that has been largely unrecognized, and which is believed can be effectively exploited to improve production efficiency and lead to substantial cost reductions.     

A scheduling approach for a flexible manufacturing system

This paper discusses the scheduling problem of a particular flexible manufacturing system (FMS). The two main components of the FMS are a CNC turret lathe and a CNC machining centre. In the system a wide range of different jobs has to be processed. Each job consists of one or more processing operations on one or both machines. Important characteristics of the scheduling problem are sequence-dependent change-over times (on the turret lathe) and transfer times (on both machines and between the machines). The change-over times are caused by the need to exchange tools in the turret when a new part is going to be processed. The transfer times reflect the time needed to perform manual transportation and clamping activities between two subsequent processing (machining) operations of a part. In this paper a branch and bound algorithm is described based on an active schedule strategy. Solutions are compared to results obtained by a simple dispatching rule     

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.     

A study of scheduling rules of flexible manufacturing systems: A simulation approach

This study examines the effects of scheduling rules on the performance of flexible manufacturing systems (FMSs). Several machine and AGV scheduling rules are tested against the mean flowtime criterion. In general, scheduling rules are widely used in practice ranging from direct applications as a stand-alone scheduling scheme to indirect application as a part of complicated scheduling systems. In this paper, we compare the rules under various experimental conditions by using an FMS simulation model. Our objective is to measure sensitivity of the rules to changes in processing time distributions, various levels of breakdown rates, and types of AGV priority schemes. A comprehensive bibliography is also presented in the paper.     

Robot and machine scheduling with state-dependent part input sequencing in flexible manufacturing systems

In competitive global markets, it is important to meet customer demands on multiple priorities such as price, quality, customisation and quick delivery. This paper investigates the problems of part input sequencing and scheduling in flexible manufacturing systems in a mass customisation/mass personalisation (MC/MP) environment. Both robot and machine scheduling rules using a state-dependent part input sequencing algorithm are investigated. Simulation experiments and statistical analyses are carried out. Effective rules are identified. The results show interactions between robot scheduling and machine scheduling in the MC/MP environment. Further research suggestions are provided.     

Adaptive scheduling in random flexible manufacturing systems subject to machine breakdowns

In a FMS dynamic scheduling environment, frequent rescheduling to react to disruptions such as machine breakdowns can make the behaviour of the system hard to predict, and hence reduce the effectiveness of dynamic scheduling. Another approach to handle the disruptions is to update the job ready time and completion time, and machine status on a rolling horizon basis, and consider the machine availability explicitly in generating schedules. When machine downtime has a small variation, the operation completion time is estimated by using limiting (steady-state) machine availability. However, steady-state analysis is sometimes unlikely to provide a complete picture of the system when there is a large variation in machine downtime and repair time, and frequent disruptions (e.g. tool failures) exist. Transient analysis of machine availability will be more meaningful in such a situation during a finite observation period. In this paper, an adaptive scheduling approach is proposed to make coupled decisions about part/machine scheduling and operation/tool assignments on a rolling horizon basis, while the operation completion time is estimated by a transient machine availability analysis based on a two-state continuous time Markov process. The expected tool waiting time is explicitly considered in the job machine scheduling decision. The effectiveness of the proposed method is compared with other approaches based on various dispatching heuristics such as Apparent Tardiness Cost, Cost OVER Time, and Bottleneck Dynamics, etc under different shop load and machine downtime levels.     

Production planning for flexible manufacturing systems with multiple machine types: A practical method

We study three important production planning problems for flexible manufacturing systems (FMSs) that consist of multiple types of machines. Namely we address machine grouping, workload allocation among machine groups, and batch sizing that maximize system throughput, when part types are selected for the upcoming production period. This differs from earlier related works in that earlier works give either only qualitative characteristics of the optimum solution or provide a solution method for FMSs consisting of only one type of flexible machine. In this paper, we provide both the optimum and heuristic methods to simultaneously solve the three problems for realistic FMSs. Computational results show that the heuristic method always finds the optimum solution at a fraction of computation time and that batch sizing can significantly affect throughput. Development of the heuristic method is necessary since the optimum method can be time-consuming for a moderate size of problems.     

Deadlock-free genetic scheduling for flexible manufacturing systems using Petri nets and deadlock controllers

In this paper, a new deadlock-free scheduling method based on genetic algorithm and Petri net models of flexible manufacturing systems is proposed. The optimisation criterion is to minimise the makespan. In the proposed genetic scheduling algorithm, a candidate schedule is represented by a chromosome that consists of two sections: route selection and operation sequence. With the support of a deadlock controller, a repairing algorithm is proposed to check the feasibility of each chromosome and fix infeasible chromosomes to feasible ones. A feasible chromosome can be easily decoded to a deadlock-free schedule, which is a sequence of transitions without deadlocks. Different kinds of crossover and mutation operations are performed on two sections of the chromosome, respectively, to improve the performance of the presented algorithm. Computational results show that the proposed algorithm can get better schedules. Furthermore, the proposed scheduling method provides a new approach to evaluate the performance of different deadlock controllers.     

A methodology for designing flexible cellular manufacturing systems

Cell formation in cellular manufacturing deals with the identification of machines that can be grouped to create manufacturing cells and the identification of part families to be processed within each cell. Dynamic and random variations in part demands can negatively impact cell performance by creating unstable machine utilizations. The purpose of this paper is to introduce and illustrate an interactive cell formation method that can be used to design 'flexible' cells. Flexibility in this context refers to routing flexibility (i.e., the ability for the cellular system to process parts within multiple cells) and demand flexibility (i.e., the ability of the cell system to respond quickly to changes in part demand and part mix). Through an experimental analysis using multiple data sets, we also validate the procedure and provide guidelines for parameter settings depending upon the type of flexibility of interest to the user. Finally, trade-offs and interdependences between alternative types of flexibility in the context of cellular systems are illustrated.     

Biogeography-based optimisation for flexible manufacturing system scheduling problem

Biogeography-based optimisation (BBO) algorithm is a new evolutionary optimisation algorithm based on geographic distribution of biological organisms. With probabilistic operators, this algorithm is able to share more information from good solutions to poor ones. BBO prevents the good solutions to be demolished during the evolution. This feature leads to find the better solutions in a short time rather than other metaheuristics. This paper provides a mathematical model which integrates machine loading, part routing, sequencing and scheduling decision in flexible manufacturing systems (FMS). Moreover, it tackles the scheduling problem when various constraints are imposed on the system. Since this problem is considered to be NP-hard, BBO algorithm is developed to find the optimum /near optimum solution based on various constraints. In the proposed algorithm, different types of mutation operators are employed to enhance the diversity among the population. The proposed BBO has been applied to the instances with different size and degrees of complexity of problem adopted from the FMS literature. The experimental results demonstrate the effectiveness of the proposed algorithm to find optimum /near optimum solutions within reasonable time. Therefore, BBO algorithm can be used as a useful solution for optimisation in various industrial applications within a reasonable computation time.     

A bottleneck-based beam search for job scheduling in a flexible manufacturing system

In this paper, we study job-scheduling methods for flexible manufacturing systems (FMSs). Routeing flexibility is a feature that distinguishes FMS scheduling from a classic general jobshop problem. We formalize the problem as a flexible jobshop problem and introduce a flexibility index to measure the extent of routeing flexibility. Based on a procedure to identify a potential bottleneck machine, we develop a beam search method for approximately solving the problem. The proposed method yields a significantly shorter makespan than that of the commonly used shortest processing-time dispatching rule, and it properly exploits the added flexibility in routeing. The computational effort required also is small enough to enable practical implementation.     

A queueing network model for flexible manufacturing systems with tool management

The analytical model in this paper allows the evaluation of the performance of a flexible manufacturing system (FMS) with a tool management system. Design parameters such as the transportation time for tools to machines, as well as the number of transportation vehicles for tools, are explicitly considered. The part and the tool transportation system are modeled as two interacting closed queueing networks. The classical convolution algorithm is used to evaluate the part transportation system and mean value analysis approximation is applied to evaluate the tool transportation system. The resulting set of nonlinear equations allows then to estimate important system parameters such as the throughput of parts, the utilization of the tool transportation vehicles and the service interruptions caused by a tool supply order.     

Design and scheduling for flexible manufacturing cells with automatic set-up equipment

A flexible manufacturing cell (FMC) has become of major interest recently as a new machining unit for low-volume, variety production. However, set-up operations for workpieces have not yet been automated in the usual FMC. In this paper, the design and scheduling problems for FMC with automatic set-up equipment are discussed. The FMC consists of a machining centre, an industrial robot, a loading-unloading station and an index-pallet changer. First, the design and control system of the FMC is explained. Then a scheduling algorithm is developed to achieve the minimum total production time in order to operate the FMC effectively. As this FMC has finite buffer spaces on the index-pallet changer, this model can be regarded as a two-machine flow-shop problem with finite buffer spaces. Next, an algorithm for determining the optimum number of buffer spaces is constructed to design the FMC using the results of scheduling. Finally, a numerical example is given for demonstrating the effectiveness of the proposed algorithms.     

A learning-based methodology for dynamic scheduling in distributed manufacturing systems

To enhance productivity in a distributed manufacturing system under hierarchical control, we develop a framework of dynamic scheduling scheme that explores routeing flexibility and handles uncertainties. We propose a learning-based methodology to extract scheduling knowledge for dispatching parts to machines. The proposed methodology includes three modules: discrete-event simulation, instance generation, and incremental induction. First, a sophisticated simulation module is developed to implement a dynamic scheduling scheme, to generate training examples, and to evaluate the methodology. Second, the search for training examples (good schedules) is successfully fulfilled by the genetic algorithm. Finally, we propose a tolerance-based learning algorithm that does not only acquire general scheduling rules from the training examples, but also adapts to any newly observed examples and thus facilitates knowledge modification. The experimental results show that the dynamic scheduling scheme significantly outperforms the static scheduling scheme with a single dispatching rule in a distributed manufacturing system.     

Application of genetic algorithms with dominant genes in a distributed scheduling problem in flexible manufacturing systems

Multi-factory production networks have increased in recent years. With the factories located in different geographic areas, companies can benefit from various advantages, such as closeness to their customers, and can respond faster to market changes. Products (jobs) in the network can usually be produced in more than one factory. However, each factory has its operations efficiency, capacity, and utilization level. Allocation of jobs inappropriately in a factory will produce high cost, long lead time, overloading or idling resources, etc. This makes distributed scheduling more complicated than classical production scheduling problems because it has to determine how to allocate the jobs into suitable factories, and simultaneously determine the production scheduling in each factory as well. The problem is even more complicated when alternative production routing is allowed in the factories. This paper proposed a genetic algorithm with dominant genes to deal with distributed scheduling problems, especially in a flexible manufacturing system (FMS) environment. The idea of dominant genes is to identify and record the critical genes in the chromosome and to enhance the performance of genetic search. To testify and benchmark the optimization reliability, the proposed algorithm has been compared with other approaches on several distributed scheduling problems. These comparisons demonstrate the importance of distributed scheduling and indicate the optimization reliability of the proposed algorithm.     

A heuristic procedure for loading problems in flexible manufacturing systems

The loading problem in a flexible manufacturing system (FMS) is viewed as selecting a subset of jobs from a job pool and allocating the jobs among machines. In this paper a heuristic solution to the loading problem has been suggested by developing the concept of essentiality ratio for the objective of minimizing the system unbalance and thereby maximizing the throughput. The proposed heuristic is tested on ten problems and the results show that the algorithm developed is very reliable and efficient.