State space representation of routing flexibility

This paper describes a state space representation for sequencing and routing flexibility in manufacturing systems. Routing flexibility is represented using five different stages as follows: (i) Precedence Graph of Operations; (ii) State Transition Graph of Manufacturing Operation Sequences; (iii) State Transition Graph of Manufacturing Operation Routes; (iv) Disjunctive Normal Form (DNF) Representation of Manufacturing Sequences; and (v) DNF Representation of Manufacturing Routes. Each representation is able to represent sequencing and routing flexibility at different levels of detail. The third representation is capable of enumerating all possible manufacturing operation routes that can be applied to a certain part, being the most complete representation. Bounds for computation of some of the representations are presented to help users select the most suitable for a specific problem context. The efficacy of the representation is demonstrated through its application to problems such as job route selection and routing flexibility measure.     

Analysis of dynamic due-date assignment models in a flexible manufacturing system

This paper investigates the effects of dynamic due-date assignment models (DDDAMs), routing flexibility levels (RFLs), sequencing flexibility levels (SFLs) and part sequencing rules (PSRs) on the performance of a flexible manufacturing system (FMS) for the situation wherein part types to be produced in the system arrive continuously in a random manner. The existing DDDAMs considered are dynamic processing plus waiting time and dynamic total work content. A new model known as dynamically estimated flow allowance (DEFA) has also been developed and investigated. The routing flexibility of the system and the sequencing flexibility of parts are both set at three levels. A discrete-event simulation model of the FMS is used as a test-bed for experimentation. The performance measures evaluated are mean flow time, mean tardiness, percentage of tardy parts and mean flow allowance. The statistical analysis of the simulation results reveals that there are significant interactions among DDDAMs, RFLs, SFLs and PSRs for all the performance measures. The proposed DEFA model provides the minimum percentage of tardy parts in all the experiments. Regression-based metamodels have been developed using the simulation results. The metamodels are found to provide a good prediction of the performance of the FMS within the domain of their definition.     

Flexible job-shop scheduling with routing flexibility and separable setup times using ant colony optimisation method

This paper proposes an ant colony optimisation-based software system for solving FMS scheduling in a job-shop environment with routing flexibility, sequence-dependent setup and transportation time. In particular, the optimisation problem for a real environment, including parallel machines and operation lag times, has been approached by means of an effective pheromone trail coding and tailored ant colony operators for improving solution quality. The method used to tune the system parameters is also described. The algorithm has been tested by using standard benchmarks and problems, properly designed for a typical FMS layout. The effectiveness of the proposed system has been verified in comparison with alternative approaches.     

Analysis of dynamic control strategies of an FMS under different scenarios

This paper presents a simulation study aimed at evaluating the performances of a flexible manufacturing system (FMS) in terms of makespan, average flow time, average delay time at local buffers and average machine utilization, subject to different control strategies which include routing flexibilities and dispatching rules. The routing strategies under evaluation are ‘no alternative routings’; ‘alternative routings dynamic’; and ‘alternative routings planned’. Above routing strategies are combined with seven dispatching rules, and studied in different production volume which varies from 50 to 500 parts. In addition, impacts of both infinite and finite local buffer capacities are analyzed. Since an FMS usually deals with a variety of products, effects of changing the part mix ratio are also discussed. Finally, machine failure is also introduced in this research to study the effects of machine reliability on the system. Simulation results indicate that the ‘alternative routings planned’ strategy outperforms other routing strategies if the local buffer size is infinity. However, there is no particular dispatching rule that performs well in all buffer size settings but infinity buffer size is not the best choice with respect to the four performance measures. In addition, the four performance measures, except machine utilization, under different control strategies seem quite insensitive to the variation in part mix ratios.     

Some effects of flexibility and dependability on cellular manufacturing system performance

The advantages of cellular manufacturing organization can be strongly affected by uncertainty. In particular, the effects of resource dependability on system performance are investigated. The use of routing flexibility in cellular manufacturing systems (CMS) is analyzed to search system configurations that optimize system performance. Adopting the concept of “limited flexibility” proposed in the literature, a simulation model is proposed to point out some trade-off between routing flexibility costs and benefits in a CMS with both constant and variable part family demand. Three specific problems are addressed and quantitative results, in terms of costs and lost sale performance, are provided by case examples.     

Flexibility performance: Taguchi's method study of physical system and operating control parameters of FMS

In present manufacturing environment, the manufacturing flexibility has become one of the strategic competitive tools. Flexibility refers to the availability of alternative resources. These resources may have varied parameters, particularly related to physical and operating system. These physical and operating parameters of alternative resources may influence the system's performance with the changing levels of flexibility and operational control parameters such as scheduling rules. Is increase in a flexibility level provides desired improved performance output? If yes, than under what conditions of physical and operating parameters and under which control strategy (CS)? Is improved performance is present at all increasing levels of flexibility? Flexible manufacturing system (FMS) being consist of numerous physical and operating parameters and complex in nature, the solution to these questions can provide an understanding of the productive levels of flexibility for a given physical and operating parameters of an FMS. This paper establishes the need of modelling of the physical and operating parameters of flexible manufacturing system along with flexibility and presents a simulation study under Taguchi's method analysis of these parameters. The paper contributes an approach to study the impact of variations in physical and operating parameters of an FMS and to identify the level of these variations that do not restrict the advantages of flexibility. The results show that the expected benefits from increasing the levels of flexibility and a superior CS may not be achieved if the physical and operating parameters of alternative machines have variations. Taguchi's method analysis indicates that relative percentage contribution of variations in physical and operating parameters of alternative resources should be negligible or minimum in the performance of FMS. Their increasing relative contribution may restrict the advantages of flexibility. If these variations are higher than increase in flexibility level may be counter productive.     

A hybrid heuristic to solve the parallel machines job-shop scheduling problem

This paper presents an advanced software system for solving the flexible manufacturing systems (FMS) scheduling in a job-shop environment with routing flexibility, where the assignment of operations to identical parallel machines has to be managed, in addition to the traditional sequencing problem. Two of the most promising heuristics from nature for a wide class of combinatorial optimization problems, genetic algorithms (GA) and ant colony optimization (ACO), share data structures and co-evolve in parallel in order to improve the performance of the constituent algorithms. A modular approach is also adopted in order to obtain an easy scalable parallel evolutionary-ant colony framework. The performance of the proposed framework on properly designed benchmark problems is compared with effective GA and ACO approaches taken as algorithm components.     

Design and planning problems in flexible manufacturing systems: a critical review

This review paper describes the state-of-the-art research on flexible manufacturing systems (FMS) design and planning issues. The emphasis is on presenting research results coming out of the current FMS literature that help the FMS manager in setting up a highly efficient manufacturing system. In addition to that, it discusses relevant research contributions after 1986, that were not part of any of the previous survey papers on operations research models for FMSs. Also, applications of combinatorial optimization approaches to FMS planning problems are adequately exposed in the paper.     

Genetic algorithms for match-up rescheduling of the flexible manufacturing systems

Scheduling plays a vital role in ensuring the effectiveness of the production control of a flexible manufacturing system (FMS). The scheduling problem in FMS is considered to be dynamic in its nature as new orders may arrive every day. The new orders need to be integrated with the existing production schedule immediately without disturbing the performance and the stability of existing schedule. Most FMS scheduling methods reported in the literature address the static FMS scheduling problems. In this paper, rescheduling methods based on genetic algorithms are described to address arrivals of new orders. This study proposes genetic algorithms for match-up rescheduling with non-reshuffle and reshuffle strategies which accommodate new orders by manipulating the available idle times on machines and by resequencing operations, respectively. The basic idea of the match-up approach is to modify only a part of the initial schedule and to develop genetic algorithms (GAs) to generate a solution within the rescheduling horizon in such a way that both the stability and performance of the shop floor are kept. The proposed non-reshuffle and reshuffle strategies have been evaluated and the results have been compared with the total-rescheduling method.     

Integrated scheduling of resource-constrained flexible manufacturing systems using constraint programming

This contribution presents a novel approach to address the scheduling of resource-constrained flexible manufacturing systems (FMSs). It deals with several critical features that are present in many FMS environments in an integrated way. The proposal consists in a constraint programming (CP) formulation that simultaneously takes into account the following sub-problems: (i) machine loading, (ii) manufacturing activities scheduling, (iii) part routing, (iv) machine buffer scheduling, (v) tool planning and allocation, and (vi) AGV scheduling, considering both the loaded and the empty movements of the device. Before introducing the model, this work points out the problems that might appear when all these issues are not concurrently taken into account. Then, the FMS scheduling model is presented and later assessed through several case-studies. The proposed CP approach has been tested by resorting to problems that consider dissimilar number of parts, operations per part, and tool copies, as well as different AGV speeds. The various examples demonstrate the importance of having an integrated formulation and show the important errors that can occur when critical issues such as AGV empty movements are neglected.     

Identifying FMS repetitive patterns for efficient search-based scheduling algorithm: A colored Petri net approach

The multiple lot size scheduling problem plays a crucial role in minimizing production and setup costs in order to respond to constant fluctuations in customer demands. However, the computational cost to optimize a scheduling problem increases as the lot size of jobs increases, leading to a scalability problem for most scheduling algorithms. This paper presents an efficient search approach based on colored Petri net (CPN) formalism that addresses the state explosion problem of reachability graphs used for finding the optimal solutions to scheduling problems. To reduce the memory requirements, the proposed approach exploits the structural equivalence found in the reachability graphs of flexible manufacturing systems’ (FMS) CPNs to discard states once they are no longer needed to explore the state space. The hypothetical structural equivalence is attributed to the repetitive patterns identified in the execution of manufacturing processes when the lot sizes of jobs are scaled for FMS whose underlying layout configuration is fixed. We present the concept of structural equivalence based on duplicate state detection for FMS of different lot sizes and give sufficient conditions under which the structural equivalence obtained from a few lot size (smaller) instances holds for the same FMS of a larger size. The approach is validated experimentally on different FMS examples which confirm that the behavior of an FMS of any large lot size can be inferred from the FMS of a smaller size. Experimental results indicate that this work performs better than prior search methods and obtains optimal schedules of FMS with large lot sizes. Also, we show that the approach is applicable to FMS problems of similar configurations where the problem size differ by the number of jobs, resources and operations.     

Optimum loading of machines in a flexible manufacturing system using a mixed-integer linear mathematical programming model and genetic algorithm

Machine loading problem in a flexible manufacturing system (FMS) encompasses various types of flexibility aspects pertaining to part selection and operation assignments. The evolution of flexible manufacturing systems offers great potential for increasing flexibility by ensuring both cost-effectiveness and customized manufacturing at the same time. This paper proposes a linear mathematical programming model with both continuous and zero-one variables for job selection and operation allocation problems in an FMS to maximize profitability and utilization of system. The proposed model assigns operations to different machines considering capacity of machines, batch-sizes, processing time of operations, machine costs, tool requirements, and capacity of tool magazine. A genetic algorithm (GA) is then proposed to solve the formulated problem. Performance of the proposed GA is evaluated based on some benchmark problems adopted from the literature. A statistical test is conducted which implies that the proposed algorithm is robust in finding near-optimal solutions. Comparison of the results with those published in the literature indicates supremacy of the solutions obtained by the proposed algorithm for attempted model.     

Network-based hybrid genetic algorithm for scheduling in FMS environments

Scheduling in flexible manufacturing systems (FMS) must take account of the shorter lead-time, the multiprocessing environment, the flexibility of alternative workstations with different processing times, and the dynamically changing states. The best scheduling approach, as described here, is to minimize makespan t _M, total flow time t _F, and total tardiness penalty p _T. However, in the case of manufacturing system problems, it is difficult for those with traditional optimization techniques to cope with this. This article presents a new flow network-based hybrid genetic algorithm (hGA) approach for generating static schedules in a FMS environment. The proposed method is combined with the neighborhood search technique in a mutation operation to improve the solution of the FMS problem, and to enhance the performance of the genetic search process. We update the change in swap mutation and the local search-based mutation ration. Numerical experiments show that the proposed flow network-based hGA is both effective and efficient for FMS problems.This work was presented in part at the 8th International Symposium on Artificial Life and Robotics, Oita, Japan, January 24–26, 2003     

Solving distributed FMS scheduling problems subject to maintenance: Genetic algorithms approach

In general, distributed scheduling problem focuses on simultaneously solving two issues: (i) allocation of jobs to suitable factories and (ii) determination of the corresponding production scheduling in each factory. The objective of this approach is to maximize the system efficiency by finding an optimal planning for a better collaboration among various processes. This makes distributed scheduling problems more complicated than classical production scheduling ones. With the addition of alternative production routing, the problems are even more complicated. Conventionally, machines are usually assumed to be available without interruption during the production scheduling. Maintenance is not considered. However, every machine requires maintenance, and the maintenance policy directly affects the machine's availability. Consequently, it influences the production scheduling. In this connection, maintenance should be considered in distributed scheduling. The objective of this paper is to propose a genetic algorithm with dominant genes (GADG) approach to deal with distributed flexible manufacturing system (FMS) scheduling problems subject to machine maintenance constraint. The optimization performance of the proposed GADG will be compared with other existing approaches, such as simple genetic algorithms to demonstrate its reliability. The significance and benefits of considering maintenance in distributed scheduling will also be demonstrated by simulation runs on a sample problem.     

The effect of responsiveness of the control-decision system to the performance of FMS

In Flexible Manufacturing System (FMS), decision-making process is one of the key aspects for its performance enhancement, particularly for shop-floor control, where operation managers need to make a large number of control decisions. A term called ‘response-time’ in decision-making process has been defined in this study, which refers to a lead time in decision-making and its implementation. This paper contributes a methodology for decision-maker to study the decision-making process and identify a suitable decision-making approach, while considering critical factors such as decision automation levels, routing flexibility levels, and control strategies. Considering the complexity in modelling an FMS with routing flexibility levels, control strategies (sequencing and dispatching rules), and decision-making process with information system, computer simulation modelling has been employed to study the makespan performance. The results show that decision-making process with response-time for FMS control performs as good as with the real-time control when routing flexibility level is low. Furthermore, under some specific situations, it even outperforms the real-time control. This research gives insight to decision-maker to identify whether a decision system with response-time will be more suitable and economically justified, or real-time decision-making system is more appropriate.     

Real time fuzzy scheduling rules in FMS

This paper presents a real-time fuzzy expert system to scheduling parts for a flexible manufacturing system (FMS). First, some vagueness and uncertainties in scheduling rules are indicated and then a fuzzy-logic approach is proposed to improve the system performance by considering multiple performance measures. This approach focuses on characteristics of the system's status, instead of parts, to assign priorities to the parts waiting to be processed. Secondly, a simulation model is developed and it has shown that the proposed fuzzy logic-based decision making process keeps all performance measures at a good level. The proposed approach provides a promising alternative framework in solving scheduling problems in FMSs, in contrast to traditional rules, by making use of intelligent tools.     

An asymmetric multileveled symbiotic evolutionary algorithm for integrated FMS scheduling

This paper considers the integrated FMS (flexible manufacturing system) scheduling problem (IFSP) consisting of loading, routing, and sequencing subproblems that are interrelated to each other. In scheduling FMS, the decisions for the subproblems should be appropriately made to improve resource utilization. It is also important to fully exploit the potential of the inherent flexibility of FMS. In this paper, a symbiotic evolutionary algorithm, named asymmetric multileveled symbiotic evolutionary algorithm (AMSEA), is proposed to solve the IFSP. AMSEA imitates the natural process of symbiotic evolution and endosymbiotic evolution. Genetic representations and operators suitable for the subproblems are proposed. A neighborhood-based coevolutionary strategy is employed to maintain the population diversity. AMSEA has the strength to simultaneously solve subproblems for loading, routing, and sequencing and to easily handle a variety of FMS flexibilities. The extensive experiments are carried out to verify the performance of AMSEA, and the results are reported.     

A modeling technique for loading and scheduling problems in FMS

In recent years, due to highly competitive market conditions, it has become necessary for manufacturing systems to have quick response times and high flexibility. Flexible manufacturing systems (FMS's) have gained attention in response to this challenge. FMS has the ability to produce a variety of parts using the same system. However this flexibility comes at the price, which is the development of efficient and effective methods for integrated production planning, and control.In this paper, we analyze the production planning problem in flexible manufacturing systems. We address the problems of part loading, tool loading, and part scheduling. We assume that there is a set of tools with known life and a set of machines that can produce a variety of parts. A batch of various part types is routed through this system with the assumption that the processing time and cost vary with the assignment of parts to different machines and assignment of various tool sets to machines. We developed a mathematical model to select machines and assign operations and the required tools to machines in order to minimize the summation of maximum completion time, material handling time, and total processing time.We first integrate and formulate loading, and routing, two of the most important FMS planning problems, as a 0–1 mixed integer programming problem. We then take the output from the integrated planning model and generate a detailed operations schedule. The results reported in this paper demonstrate the model efficiency and examine the performance of the system with respect to measures such as production rate and utilization.     

Evaluations of operational control rules in scheduling a flexible manufacturing system

In this paper, computer simulation is used to evaluate the effects of various control rules on the performance of a flexible manufacturing system (FMS) operating under different manufacturing environment. Alternative routings are available, if the operation of a part can be performed by more than one machine. Three control rules, namely, dynamic alternative routings, planned alternative routings, and no alternative routings, are proposed to control the selection of alternative routings for each part. The effects of the universal loading station and also those of the dedicated loading station are investigated. In addition, the impact of buffer existence on the system’s performance is also examined by considering machines with and without local buffers. The effects of changing production ratios of different part types on the performance of various operational control rules are also investigated. Moreover, the effects of system having machine breakdown are also discussed. The simulation results indicate that the FMS with dedicated loading stations outperforms the FMS with universal loading stations in all aspects. The dynamic alternative routings generally produces the best results in system performance if the universal loading station is provided. The planned alternative routings generally gives the best system performance when both the dedicated loading stations and local buffers are available. The no alternative routings usually remains at the bottom of the rank, occasionally with some exceptions. Problems in actual implementation are also highlighted.     

Using multiple objective tabu search and grammars to model and solve multi-objective flexible job shop scheduling problems

A linguistic-based meta-heuristic modeling and solution approach for solving the flexible job shop scheduling problem (FJSSP) is presented in this study. FJSSP is an extension of the classical job-shop scheduling problem. The problem definition is to assign each operation to a machine out of a set of capable machines (the routing problem) and to order the operations on the machines (the sequencing problem), such that predefined performance measures are optimized. In this research, the scope of the problem is widened by taking into account the alternative process plans for each part (process plan selection problem). Probabilistic selection of alternative process plans and machines are also considered. The FJSSP is presented as a grammar and the productions in the grammar are defined as controls (Baykasolu, 2002). Using these controls and Giffler and Thompson's (1960) priority rule-based heuristic along with the multiple objective tabu search algorithm of Baykasolu et al. (1999) FJSSP is solved. This novel approach simplifies the modeling process of the FJSSP and enables usage of existing job shop scheduling algorithms for its fast solution. Instead of scheduling job shops with inflexible algorithms that cannot take into account the flexibility which is available in the job shop, the present algorithm is developed which can take into account the flexibility during scheduling. Such an approach will considerably increase the responsiveness of the job shops.