An Artificial Intelligence Approach to the Scheduling of Flexible Manufacturing Systems

Scheduling in a flexible manufacturing system (FMS)must take into account the shorter lead-time, the multiprocessing environment, the flexibility of machine tools, and the dynamically changing states. The scheduling approach described in this paper employs a knowledge-based system to carry out the nonlinear planning method developed in artificial intelligence. The state-space process for plan-generation, by either forward- or backward-chaining, can handle scheduling requirements unique to the FMS environment. A prototype of this scheduling system has been implemented on a LISP machine and is applied to solve the scheduling problem in flexible manufacturing cells. This scheduling method is characterized by its knowledge-based organization, symbolic representation, state-space inferencing, and its ability for dynamic scheduling and plan revision. It provides a foundation for integrating intelligent planning, scheduling, and machine learning in FMSs.     

Solving machine loading problems in a flexible manufacturing system using a genetic algorithm based heuristic approach

The machine-loading problem of a flexible manufacturing system (FMS) has been recognized as one of the most important planning problems. In this research, a Genetic Algorithm (GA) based heuristic is proposed to solve the machine loading problem of a random type FMS. The objective of the loading problems is to minimize the system unbalance and maximize the throughput, satisfying the technological constraints such as availability of machining time, and tool slots. The proposed GA-based heuristic determines the part type sequence and the operation-machine allocation that guarantee the optimal solution to the problem, rather than using fixed predetermined part sequencing rules. The efficiency of the proposed heuristic has been tested on ten sample problems and the results obtained have been compared with those of existing methods.     

Experimental investigation of flexible manufacturing system scheduling decision rules

This paper reports the results of an experimental investigation of scheduling decision rules for a dedicated flexible manufacturing system. A simulation model of an existing flexible manufacturing system (FMS) comprised of 16 computer numerical controlled machines (CNC) was constructed using actual operation routings and machining times to evaluate the performance of various part loading and routing procedures. The results indicate that FMS performance is significantly affected by the choice of heuristic parts scheduling rules.     

Toward Knowledge-Based Control Of Flexible Manufacturing Systems

This paper examines the use of artificial intelligence (AI) concepts to augment/enhance flexible manufacturing system (FMS) control systems by providing flexibility in decision-making to manage and control the system. Such a system would use a “knowledge-based” approach to system control. The paper first defines the problems and issues in FMS planning and control and then examines the AI technology that can be used to solve them. The paper shows that the FMS control structure is conceptually similar to an Al-based opportunistic hierarchical planning architecture. The paper concludes by discussing the prospects for knowledge-based control of FMSs in view of current technology.     

Production planning for flexible flow systems with limited machine flexibility

A flexible manufacturing system (FMS) is highly capital-intensive and FMS users are concerned with achieving high system utilization. The production planning function for setting up an FMS prior to production should be developed in order to make the most of the potential benefits of FMSs. We consider two production planning problems of grouping and loading a flexible flow system, which is an important subset of FMSs where the routing of parts is unidirectional. We show that considering this routing restriction as well as limited machine flexibility strongly affects both the solution techniques and the quality of the solutions. Because of the complexity of the problem, we present a heuristic approach that decomposes the original problem into three interrelated subproblems. We show that the proposed approach usually finds a near-optimum solution and is superior to an approach that exists in the literature of FMS production planning. We also introduce effective heuristic methods for two new subproblems that arise because of the unidirectional flow precedence and flexibility constraints. Computational results are reported and future research issues are discussed.     

A methodical approach to the flexible-manufacturing-system batching,loading and tool configuration problems

A mixed-integer programming (MIP) problem is formulated to address the flexible manufacturing system (FMS) batching, loading, and tool configuration problems concurrently. This model results in a great many variables, making its mathematical solution impractical. We introduce a four-pass approach using submodels of the original MIP problem. The approach assumes that the need for batching is primarily that of tool magazine capacity constraints, with balancing and maximizing flexibility as secondary objectives.     

Simultaneous versus sequential loading and scheduling of flexible assembly systems

A monolithic and a hierarchical approach is presented for loading and scheduling in a general flexible assembly system and a flexible assembly line. The system is made up of a set of assembly stations of various types each with limited working space and is capable of simultaneously producing a mix of product types. The objective is to determine an assignment of assembly tasks to stations and an assembly schedule for all products so as to complete the products in a minimum time. In the monolithic approach loading and scheduling decisions are made simultaneously. In the hierarchical approach, however, first the station workloads are balanced by solving the loading problem, and then detailed assembly schedule is determined for prefixed task assignments and assembly routes by solving a standard job-shop problem. Mixed integer programming formulations are presented for simultaneous and for sequential loading and scheduling. Loading and scheduling with alternative or with single task assignments are considered. Numerical examples are included to illustrate and compare the two approaches proposed.     

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 of machines and automated guided vehicles in FMS using differential evolution

This paper addresses the problem of simultaneous scheduling of machines and two identical automated guided vehicles (AGVs) in a flexible manufacturing system (FMS). For solving this problem, a new meta-heuristic differential evolution (DE) algorithm is proposed. The problem consists of two interrelated problems, scheduling of machines and scheduling of AGVs. A simultaneous scheduling of these, in order to minimise the makespan will result in a FMS being able to complete all the jobs assigned to it at the earliest time possible, thus saving resources. An increase in the performance of the FMS under consideration would be expected as a result of making the scheduling of AGVs as an integral part of the overall scheduling activity. The algorithm is tested by using problems generated by various researchers and the makespan obtained by the algorithm is compared with that obtained by other researchers and analysed.     

Scheduling of flexible manufacturing systems based on Petri nets and hybrid heuristic search

This paper proposes and evaluates a hybrid search strategy and its application to flexible manufacturing system (FMS) scheduling in a Petri net framework. Petri nets can concisely model multiple lot sizes for each job, the strict precedence constraint, multiple kinds of resources, and concurrent activities. To cope with the complexities for FMS scheduling, this paper presents a hybrid heuristic search strategy, which combines the heuristic A* strategy with the DF strategy based on the execution of the Petri nets. The search scheme can invoke quicker termination conditions, and the quality of the search result is controllable. To demonstrate this, the scheduling results are derived and evaluated through a simple FMS with multiple lot sizes for each job. The algorithm is also applied to a set of randomly generated more complex FMSs with such characteristics as limited buffer sizes, multiple resources, and alternative routings.     

Incorporating dynamism in traditional machine loading problem: an AI-based optimisation approach

Machine breakdowns have been recognised in flexible manufacturing systems (FMS) as the most undesirable characteristic adversely affecting the overall efficiency. In order to ameliorate product quality and productivity of FMS, it is necessary to analyse, as well as to minimise the effect of breakdowns on the objective measures of various decision problems. This paper addresses the machine loading problem of FMS with a view to maximise the throughput and minimise the system unbalance and makespan. Moreover, insufficient work has been done in the domain of machine loading problem that considers effect of breakdowns. This motivation resulted in a potential model in this paper that minimises the effect of breakdowns so that profitability can be augmented. The present work employs an on-line machine monitoring scheme and an off-line machine monitoring scheme in conjunction with reloading of part types to cope with the breakdowns. The proposed model bears similarity with the dynamic environment of FMS, hence, termed as the dynamic machine loading problem. Furthermore, to examine the effectiveness of the proposed model, results for throughput, system unbalance and makespan on different dataset from previous literature has been investigated with application of intelligence techniques such as genetic algorithms (GA), simulated annealing (SA) and artificial immune systems (AIS). The results incurred under breakdowns validate the robustness of the developed model for dynamic ambient of FMS.     

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.     

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.     

Scheduling manufacturing systems with blocking: a Petri net approach

This paper introduces a Petri net-based approach for scheduling manufacturing systems with blocking. The modelling of the job routings and the resource and blocking constraints is carried out with the Petri net formalism due to their capability of representing dynamic, concurrent discrete-event dynamic systems. In addition Petri nets can detect deadlocks typically found in systems with blocking constraints. The scheduling task is performed with an algorithm that combines the classical A* search with an aggressive node-pruning strategy. Tests were conducted on a variety of manufacturing systems that included classical job shop, flexible job shop and flexible manufacturing scheduling problems. The optimisation criterion was makespan. The experiments show that the algorithm performed well in all types of problems both in terms of solution quality and computing times.     

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.     

Jointly solving the group scheduling and machining speed selection problems: A hybrid tabu search and simulated annealing approach

In a cellular manufacturing environment, once the machines and parts have been grouped the remaining tasks are sequencing part families and scheduling operations for the parts within each part family so that some planning goals such as minimization of tardiness can be achieved. This type of problem is called group scheduling and will be analysed in this paper. The solution of the group scheduling is affected by the machining speed specified for each operation since the completion time of each operation is a function of machining speed. As such, the group scheduling and machining speed selection problems should be simultaneously solved to provide meaningful solutions. This, however, further complicates the solution procedure. In view of this, a hybrid tabu-simulated annealing approach is proposed to solve the group scheduling problem. The main advantage of this approach is that a short term memory provided by the tabu list can be used to avoid solution re-visits while preserving the stochastic nature of the simulated annealing method. The performance of this new method has been tested and favourably compared with two other algorithms using tabu search and simulated annealing alone.     

FMS Scheduling Simulation Based on an Evolution Algorithm

A FMS（flexible manufacturing system) scheduling algorithm based on an evolution algorithm (EA) is developed by intensively analyzing and researching the scheduling method in this paper.Many factors related to FMS scheduling are considered sufficiently.New explanations for a common kind of the encoding model are given.The rationality of encoding model is ensured by designing a set of new encoding methods,while the simulation experiment is performed.The results show that a FMS scheduling optimum problem with multi-constraint conditions can be effectively solved by a FMS scheduling simulation model based on EA.Comparing this method with others,this algorithm has the advantage of good stability and quick convergence.     

Development of a simulation-based optimisation for controlling operation allocation and material handling equipment selection in FMS

Flexible manufacturing system (FMS) is described as a set of computerised numerical controlled machines, input–output buffers interconnected by automated material handling devices. This paper develops a bi-objective operation allocation and material handling equipment selection problem in FMS with the aim of minimising the machine operation, material handling and machine setup costs and maximising the machine utilisation. The proposed model is solved by a modified chaotic ant swarm simulation based optimisation (CAS²O) while applying pre-selection and discrete recombination operators is surveyed a capable method to simulate different experiments of FMS problems. A test problem is selected from the literature to evaluate the performance of the proposed approach. The results validate the effectiveness of the proposed method to solve the FMS scheduling problem.     

Multicriteria dynamic scheduling methodology for controlling a flexible manufacturing system

A methodology is presented for the dynamic scheduling of flexible manufacturing systems (FMSs). A two-level control hierarchy is suggested. The higher level is used for determining a dominant decision criterion and relevant scheduling rules, based on an analysis of the actual shop status. The lower level uses simulation for determining the best scheduling policy to be selected. Simulation is used to evaluate different control options, and once a control decision is made, it is operated in real time to serve as the FMS controller. The suggested scheduling and control scheme is being developed, implemented and tested in a physical computer integrated manufacturing (CIM)/FMS environment at the CIM and Robotics Lab of the Faculty of Industrial Engineering and Management, Technion. This will serve as a test-bed to study the performance of the FMS under different scheduling rules and control options, and to recommend the best combination of control policies and parameters for specific system conditions and global production objectives.     

Multi-criteria optimisation-based dynamic scheduling for controlling FMS

This study deals with controlling flexible manufacturing systems (FMS) operating in volatile production environments. Most studies that address this issue use some sort of adaptive scheduling that enables the FMS to cope with the randomness and variability efficiently. The methods presented in the literature are usually based on heuristics and use simple dispatching rules. They do not consider changing the decision criteria dynamically as the system conditions change. In contrast to previous studies, the present study focuses on developing a control mechanism for dynamic scheduling that is based on incremental optimisation. This means that each time a scheduling decision is made, the local optimisation problem is solved such that the next jobs to be processed on machines are selected. The objective function (dominant decision criterion) for this optimisation problem is selected dynamically based on production order requirements, actual shop-floor status and system priorities. The proposed multi-criteria optimisation-based dynamic scheduling methodology was evaluated and compared with some known scheduling rules/policies. The results obtained demonstrate the superiority of the suggested methodology as well as its capability to cope with a multi-criteria environment.