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.     

Methods for activating the decision-making process that is used for controlling flexible manufacturing systems

This paper deals with controlling flexible manufacturing systems (FMS) operating in volatile production environments. Shnits et al. (Shnits, B., Rubinovitz, J., and Sinreich, D., 2004. Multicriteria dynamic scheduling methodology for controlling a flexible manufacturing system. International Journal of Production Research, 42 (17), 3457–3472.) and Shnits and Sinreich (Shnits, B. and Sinreich, D., 2006. Controlling flexible manufacturing systems based on a dynamic selection of an appropriate operational criteria and scheduling policy. International Journal of Flexible Manufacturing Systems, 18 (1), 1–27.) developed a multi-criteria dynamic scheduling mechanism for controlling an FMS that can cope with such environments. An important part of this mechanism functioning, which impinges directly on its performance, is the activation of its decision-making process. This study continues the research presented in the above-mentioned papers and proposes different triggering methods for activating the control system decision-making process. The operational conditions for each suggested triggering method were analysed and a comparative analysis between these methods was performed. It was revealed that the highly dynamic triggering method, which activates the decision-making process right before a resource becomes available, outperformed the triggering methods that use a predefined scheduling period.     

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.     

Flexibility trade-offs in a random flexible manufacturing system: A simulation study

Flexible manufacturing systems (FMSs) are allowing firms to take advantage of diversified, low volume production of products with short life-cycles. The flexibility provided by an FMS improves the ability of a system to respond to change. Several types of manufacturing flexibility (M F) have been identified in the literature. Ideally, it is desirable to provide an FMS with all types of flexibility. However, there is a general consensus on the discordant nature of some of the flexibilities. This makes it imperative for management to recognize which flexibilities it deems critical to the manufacturing strategy of the firm. This allows the management to trade-off some of the less important flexibilities for the more important ones, as the need arises.

This study is an attempt toward an empirical examination of the flexibility trade-offs in an FMS. By using computer simulation, we study the flexibility tradeoffs in the stochastic environment of a random FMS. Various configurations of the FMS are simulated under the influence of a variety of loading and dispatching strategies. The results show that there is a trade-off among the various flexibility types under most circumstances. However, some scenarios illustrate that an appropriate combination of the variables like scheduling environment, product variety, and system configuration, can be effective in containing these trade-offs. In other cases, it is seen that the FMS can accommodate more than one flexibility type simultaneously.     

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.     

A constructive heuristic algorithm for concurrently selecting and sequencing jobs in an FMS environment

This paper deals with the concurrent solution of the loading and scheduling problems in a flexible manufacturing system ( FMS) environment. It is assumed that the FMS environment has production planned periodically and each job in the system has a number of operations to be processed on flexible machines. A heuristic approach using a constructive scheduling method is developed to solve the FMS loading and scheduling problems concurrently. The computational results are compared to an existing procedure that considers a hierarchical approach with a similar problem environment. The comparison study shows a significant improvement over the existing hierarchical procedure. This experiment indicates that a concurrent solution approach can solve the FMS loading and scheduling problems very effectively.     

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.     

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 comparison of tool management strategies and part selection rules for a flexible manufacturing system

An important element in the successful operation of flexible manufacturing systems (FMS) is the management of the tooling component. This paper reports on one aspect of tool management for FMS operations. Four tool allocation and scheduling strategies are compared in the presence of three part selection rules through a simulation study of a five-machine FMS with an automated tool handling system. The tool allocation strategies are similar to those used in industry while the part selection rules are synthesized from the literature on FMS scheduling under tooling constraints. The use of different tooling strategies produces significantly different outcomes in FMS performance.     

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.     

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.     

Part ordering through simulation-optimization in an FMS

One of the most important scheduling and control problems that must be solved concerning the efficient operation of FMS is the part ordering problem, i.e. finding the optimal sequence of parts to be released into the manufacturing system. Methods currently available for handling this problem are based on heuristic dispatching rules. In this paper an approach for solving the problem using the simulation-optimization technique is proposed. Currently available heuristic approaches can only try to get the optimum at a local level because of the complexities of the system and the dependencies of its components, whereas the proposed approach tries to get the global optimum.     

Fuzzy inference-based multiple criteria FMS scheduling

This paper proposes a fuzzy inference-based scheduling decision for flexible manufacturing systems (FMS) with multiple objectives. The objectives have different and dynamic preference levels. It is inferred that the changes in the production environment may be sensed by environmental variables. The detected changes are input in a fuzzy inference mechanism, which outputs the current preference levels of all objectives. A multiple criteria scheduling decision is then made, using the partitioned combination of the preference levels. An example of application is presented. Simulation results show very good performance for the proposed system.     

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.     

Auction-based distributed scheduling in a dynamic job shop environment

Developments in computing and communication technology coupled with the inability to address real-time issues in scheduling algorithms based on central control, has led to an interest in solving the problem of a distributed decision-making environment. This paper presents a new job shop formulation that schedules jobs using auctions for distributing control. A theoretical basis is presented for problem decomposition, bid construction, and bid evaluation for the auction using standard mathematical programming tools. Numerical results show that the auction-based approach outperforms the distributed dispatching approaches and can be used to create schedules for a wide range of scheduling objectives.     

The study of real time scheduling by an intelligent multi-controller approach

Earlier studies indicated that using multiple dispatching rules (MDRs) for the various zones in the system can enhance the production performance to a greater extent than using a single dispatching rule (SDR) over a given scheduling interval for all the machines in the system, since MDRs employ the multi-pass simulation approach for real-time scheduling (RTS). However, if a classical machine learning approach is used, an RTS knowledge base (KB) can be developed by using the appropriate MDRs strategy (this method is called an intelligent multi-controller in this paper) as obtained from training examples. The main disadvantage of using MDRs is that the classes (scheduling decision variables) to which training examples are assigned must be provided. Hence, developing an RTS KB using the intelligent multi-controller approach becomes an intolerably time-consuming task because MDRs for the next scheduling period must be determined. To address this issue, we proposed an intelligent multi-controller incorporating three main mechanisms: (1) simulation-based training example generation mechanism, (2) data pre-processing mechanism and (3) SOM-based real time MDRs selection mechanism. Under various performance criteria over a long period, the proposed approach yields better system performance than the machine learning-based RTS using the SDR approach and heuristic individual dispatching rules.     

分布式FMS智能调度和控制系统的研究与开发

介绍了分布式ＦＭＳ智能调度和控制系统的研究与开发情况：提出了一种新的适合于分布式系统建模的网络计时Ｐｅｔｒｉ网ＮＴＰＮ；将ＮＴＰＮ模型与专家系统技术相结合，为系统控制器开发了基于工程的专家系统ＥＢＥＳ；利用面向对象的技术开发了仿真的对象类库，并实现了从仿真到控制的软件重用。     

A loading and dispatching problem in a random flexible manufacturing system

A scheduling problem in a flexible manufacturing system (FMS) is considered to be a composite of two interdependent tasks: loading and sequencing. Formulations are presented for the loading problem with two objectives:

(i) minimization of the system workload unbalance, and

(ii) minimization of system unbalance and the number of late jobs;

including constraints such as the number of tools slots with duplications, unique job routing, nonsplitting of jobs and machine capacity. For both the objectives, heuristic methods are developed and performance is compared with the exact mixed integer programming solutions. A simulation model is developed for investigating the system performance for the problem of minimizing the system unbalance using heuristic and sequential loading methods in conjunction with four—FIFO, SPT, LPT and MOPR—dispatching rules.     

Modelling of flexible manufacturing system: a review

A flexible manufacturing system (FMS) due to its ability of being flexible in nature is concerned with automatic production of different parts in medium range. In short, it can be regarded as an automated manufacturing system. In this paper, an insight on previous work in the area of FMS modelling has been provided with an overview of research and development for better understanding of FMS. It serves as a medium for investigation of work that are accomplished by using different modelling techniques in FMS like mathematical, artificial intelligence, hierarchical, multi criteria decision-making method, Petri Nets and simulation. This paper will help researchers who are keen to do research in the area of FMS modelling, by highlighting contribution of available techniques in the field of FMS. It will also help them in deciding which modelling techniques can be used for a given problem. At last, comparison of different parameters considered in the recent papers of modelling FMS has been provided in the form of Table, along with a clear vision related to those works that still need to be investigated.     

Learning effective dispatching rules for batch processor scheduling

Batch processor scheduling, where machines can process multiple jobs simultaneously, is frequently harder than its unit-capacity counterpart because an effective scheduling procedure must not only decide how to group the individual jobs into batches, but also determine the sequence in which the batches are to be processed. We extend a previously developed genetic learning approach to automatically discover effective dispatching policies for several batch scheduling environments, and show that these rules yield good system performance. Computational results show the competitiveness of the learned rules with existing rules for different performance measures. The autonomous learning approach addresses a growing practical need for rapidly developing effective dispatching rules for these environments by automating the discovery of effective job dispatching procedures.