A mixed dispatching rule approach in FMS scheduling

Short-term scheduling in flexible manufacturing systems (FMSs) is a difficult problem because of the complexities and dynamic behavior of FMSs. To solve this problem, a dispatching rule approach is widely used. In this approach, however, a single dispatching rule is usually assigned for all machines in a system during a given scheduling interval. In this paper, a mixed dispatching rule which can assign a different dispatching rule for each machine is proposed. A search algorithm which selects an appropriate mixed dispatching rule using predictions based on discrete event simulation is developed for this approach. The search algorithm for the mixed dispatching rule is described in detail. The effectiveness (in meeting performance criteria) of the mixed dispatching rule and the efficiency of the search algorithm relative to exhaustive search (complete enumeration) is demonstrated on an FMS model. The mixed dispatching rule approach performs up to 15.9% better than the conventional approach, and is 4% better on average. The statistical significance of the results is dicussed.     

Production activity control: A practical approach to scheduling

There is a widely perceived gap within the domain of scheduling for manufacturing systems, namely, many of the methods employed by production supervisors are quite different from those developed by researchers. In a sense, this inconsistency highlights the important fact that much scheduling research has failed to win approval where it matters most, namely, within the manufacturing system. In this article, we argue for a practical approach to scheduling for manufacturing systems, one that we believe can narrow, and possibly bridge, the gap between theory and practice. This approach is based upon a well-defined and modular architecture for scheduling, termedproduction activity control. This architecture is the foundation of our proposed solution to scheduling, since it provides a coherent blueprint for the synthesis of information technology and scheduling strategies. The result of this synthesis is a design tool for production activity control, which allows for detailed and disciplined experimentation with a range of scheduling strategies in a controlled and simulated environment. Due to the unique modular property of the design tool, these strategies may then be implemented live in a flexible manufacturing facility, hence narrowing the gap between scheduling theory and manufacturing practice. Our overall approach is tested through an appropriate implementation in a modern electronics assembly plant.     

Dispatching,routing, and scheduling of two automated guided vehicles in a flexible manufacturing system

This article presents a new approach for planning the dispatching, conflict-free routing, and scheduling of automated guided vehicles in a flexible manufacturing system. The problem is solved optimally in an integrated manner, contrary to the traditional approach in which the problem is decomposed in three steps that are solved sequentially. The algorithm is based on dynamic programming and is solved on a rolling time horizon. Three dominance criteria are used to limit the size of the state space. The method finds the transportation plan minimizing the makespan (the completion time for all the tasks). Various results are discussed. A heuristic version of the algorithm is also proposed for an extension of the method to many vehicles.     

Effectiveness of flexible routing control

Flexibility in part process representation and in highly adaptive routing algorithms are two major sources for improvement in the control of flexible manufacturing systems (FMSs). This article reports the investigation of the impact of these two kinds of flexibilities on the performance of the system. We argue that, when feasible, the choices of operations and sequencing of the part process plans should be deferred until detailed knowledge about the real-time factory state is available. To test our ideas, a flexible routing control simulation system (FRCS) was constructed and a programming language for modeling FMS part process plans, control strategies, and environments of the FMS was designed and implemented. In addition, a scheme for implementing flexible process routing called data flow dispatching rule (DFDR) was derived. The simulation results indicate that flexible processing can reduce mean flow time while increasing system throughput and machine utilization. We observed that this form of flexibility makes automatic load balancing of the machines possible. On the other hand, it also makes the control and scheduling process more complicated and calls for new control algorithms.     

Scheduling tasks and vehicles in a flexible manufacturing system

Due to their increasing applicability in modern industry, flexible manufacturing systems (FMSs), their design, and their control have been studied extensively in the recent literature. One of the most important issues that has arisen in this context is the FMS scheduling problem. This article is concerned with a new model of an FMS system, motivated by the practical application that takes into account both machine and vehicle scheduling. For the case of a given machine schedule, a simple polynomial-time algorithm is presented that checks the feasibility of a vehicle schedule and constructs it whenever one exists. Then a dynamic programming approach to construct optimal machine and vehicle schedules is proposed. This technique results in a pseudopolynomialtime algorithm for a fixed number of machines.     

A Heuristic Search Approach Using Approximate Solutions to Petri Net State Equations for Scheduling Flexible Manufacturing Systems

This paper proposes a new heuristic search approach based on an analytic theory of the Petri net state equations for scheduling flexible manufacturing systems (FMSs) with the goal of minimizing makespan. The proposed method models an FMS using a timed Petri net and exploits approximate solutions of the net's state equation to predict the total cost (makespan) from the initial state through the current state to the goal. That is, the heuristic function considers global information provided by the state equation. This makes the method possible to obtain solutions better than those obtained using prior works (Lee and DiCesare, 1994a, 1994b) that consider only the current status or limited global information. In addition, to reduce memory requirement and thus to increase the efficiency of handling larger systems, the proposed scheduling algorithm contains a procedure to reduce the searched state space.     

On the Consequences of Information Delays in the Scheduling of Semi-Automated Flexible Machines

Manufacturing systems with varying levels and types of flexibility employ alternative scheduling strategies to exploit flexibility for performance enhancement. Scheduling decisions in manufacturing systems are influenced by time delays due to information handling activities such as information collection, transfer, and processing. More specifically, scheduling strategies implicitly involve information intensive activities that may entail significant time delays for implementation, depending on the extant shop floor automation and integration within a flexible system. These are information delays and we believe that most contemporary flexible systems must inherently cope with some level of information delay when implementing on-line scheduling strategies. This paper conceptualizes the manifestation of information delays in the context of scheduling decisions within flexible systems through the definition of three key delay modes: (i) Mode 1 information-transfer delay; (ii) Mode 2 decision-implementation delay; and (iii) Mode 3 status-review delay. We then stress the need and importance of devising suitable on-line scheduling strategies for countering the effect of information delays by demonstrating the efficacy of a novel scheduling strategy on a single machine. While opening a new scheduling dimension with potential research ramifications, this paper highlights the fact that the concept of information delay can effectively capture the synergism issues related with flexibility, integration, and automation in the context of scheduling decisions within semi-automated flexible systems.     

Intelligent scheduling of FMSs with inductive learning capability using neural networks

With the growing uncertainty and complexity in the manufacturing environment, most scheduling problems have been proven to be NP-complete and this can degrade the performance of conventional operations research (OR) techniques. This article presents a system-attribute-oriented knowledge-based scheduling system (SAOSS) with inductive learning capability. With the rich heritage from artificial intelligence (AI), SAOSS takes a multialgorithm paradigm which makes it more intelligent, flexible, and suitable than others for tackling complicated, dynamic scheduling problems. SAOSS employs an efficient and effective inductive learning method, a continuous iterative dichotomister 3 (CID3) algorithm, to induce decision rules for scheduling by converting corresponding decision trees into hidden layers of a self-generated neural network. Connection weights between hidden units imply the scheduling heuristics, which are then formulated into scheduling rules. An FMS scheduling problem is also given for illustration. The scheduling results show that the system-attribute-oriented knowledge-based approach is capable of addressing dynamic scheduling problems.     

Vehicle Travel Time Models for AGV Systems under Various Dispatching Rules

The design and evaluation of AGV-based material handling systems are highly complex because of the randomness and the large number of variables involved. Vehicle travel time is a fundamental parameter for solving various flexible manufacturing system (FMS) design problems. This article presents stochastic vehicle travel time models for AGV-based material handling systems with emphasis on the empty travel times of vehicles. Various vehicle dispatching rules examined here include the nearest vehicle selection rule and the longest idle vehicle selection rule. A simulation experiment is used to evaluate and demonstrate the presented models.     

Developing manufacturing control software: A survey and critique

The complexity and diversity of manufacturing software and the need to adapt this software to the frequent changes in the production requirements necessitate the use of a systematic approach to developing this software. The software life-cycle model (Royce, 1970) that consists of specifying the requirements of a software system, designing, implementing, testing, and evolving this software can be followed when developing large portions of manufacturing software. However, the presence of hardware devices in these systems and the high costs of acquiring and operating hardware devices further complicate the manufacturing software development process and require that the functionality of this software be extended to incorporate simulation and prototyping. This paper reviews recent methods for planning, scheduling, simulating, and monitoring the operation of manufacturing systems. A synopsis of the approaches to designing and implementing the real-time control software of these systems is presented. It is concluded that current methodologies support, in a very restricted sense, these planning, scheduling, and monitoring activities, and that enhanced performance can be achieved via an integrated approach.     

Near optimal manufacturing flow controller design

Flow control of flexible manufacturing systems (FMSs) addresses an important real-time scheduling requirement of modern manufacturing facilities, which are prone to failures and other controllable or stochastic discrete events affecting production capacity, such as change of setup and maintenance scheduling. Flow controllers are useful both in the coordination of interconnected flexible manufacturing cells through distributed scheduling policies and in the hierarchical decomposition of the planning and scheduling problem of complex manufacturing systems. Optimal flow-control policies are hedging-point policies characterized by a generally intractable system of stochastic partial differential equations. This article proposes a near optimal controller whose design is computationally feasible for realistic-size systems. The design exploits a decomposition of the multiple-part-type problem to many analytically tractable one-part-type problems. The decomposition is achieved by replacing the polyhedra production capacity sets with inscribed hypercubes. Stationary marginal densities of state variables are computed iteratively for successive trial controller designs until the best inscribed hypercubes and the associated optimal hedging points are determined. Computational results are presented for an illustrative example of a failureprone FMS.     

Improved responsiveness of reconfigurable manufacturing systems using a standards-based approach to assess manufacturing capacity

Market acceptance of the S95 enterprise-control system integration standard and its adoption in IEC 62264, combined with the use of the ISO 15745 application integration scheme, offers a common framework for integrating diagnostic and control activities with asset maintenance and management activities. This paper describes a standard-based approach to improve the responsiveness of reconfigurable systems by using condition-based maintenance and diagnostics information to assess manufacturing capacity. Use of integration models and interoperability schemas enable manufacturing management to have greater visibility into the current state and the capabilities of manufacturing assets to meet scheduled manufacturing requirements.     

On the Dependability Design of Manufacturing Information Systems

In computer integrated manufacturing environments, dependability is a crucial attribute for the production management and control information system, which should be carefully assessed during system design. This paper discusses a global approach for assessment of the dependability of industrial information systems, covering all the phases of a study, from initial system modeling to dependability analysis and evaluation. After the presentation of the modeling concepts and tools, the paper focuses on the dependability evaluation. Two complementary algorithms are discussed, one based on the device stage method and the other on the automatic derivation of analytical expressions for the state probabilities and their symbolic evaluation. The central feature of these algorithms is their ability to deal with nonexponential stochastic processes, a fundamental requirement for this class of systems.     

A pattern-directed approach to flexible manufacturing: A framework for intelligent scheduling,learning, and control

The planning, scheduling, and control of manufacturing systems can all be viewed as problem-solving activities. In flexible manufacturing systems (FMSs), the computer program carrying out these problem-solving activities must additionally be able to handle the shorter lead time, the flexibility of job routing, the multiprocessing environment, the dynamic changing states, and the versatility of machines. This article presents an artificial intelligence (AI) method to perform manufacturing problem solving. Since the method is driven by manufacturing scenarios represented by symbolic patterns, it is referred to as pattern-directed. The method is based on three AI techniques. The first is the pattern-directed inference technique to capture the dynamic nature of FMSs. The second is the nonlinear planning technique to construct schedules and assign resources. The third is the inductive learning method to generate the pattern-directed heuristics. This article focuses on solving the FMS scheduling problem. In addition, this article reports the computation results to evaluate the utility of various heuristic functions, to identify important design parameters, and to analyze the resulting computational performance in using the pattern-directed approach for manufacturing problem-solving tasks such as scheduling.     

A distributed knowledge-based approach to flexible automation: The contract net framework

This article applied distributed artificial intelligence to the real-time planning and control of flexible manufacturing systems (FMS) consisting of asynchronous manufacturing cells. A knowledge-based approach is used to determine the course of action, resource sharing, and processor assignments. Within each cell there is an embedded automatic planning system that executes dynamic scheduling and supervises manufacturing operations. Because of the decentralized control, real-time task assignments are carried out by a negotiation process among cell hosts. The negotiation process is modeled by augmented Petri nets —the combination of production rules and Petri nets—and is excuted by a distributed, rule-based algorithm.     

Integrated Modeling Framework for Manufacturing Systems: A Unified Representation of the Physical Process and Information System

The task of process modeling in a manufacturing environment centers around controlling and improving the flow of materials. This flow comprises a complicated web of control and physical systems. Despite a variety of manufacturing system modeling approaches, more rigorous process modeling is required. This paper presents an integrated modeling framework for manufacturing systems (IMF-M). Conceptual modeling of physical materials flow supported by a graphical representation facilitates improvement of operations in manufacturing environments. A declarative and executable representation of control information systems helps to improve information management by managing a variety of information models with improved readability and reusability. A unified representation of the physical process and information system provides a common modeling milieu in which efforts can be coordinated among several groups working in the different domains of scheduling, shop floor and logistics control, and information system. Since the framework helps adapt to the changes of the physical process and information system affecting each other in a consistent manner, the modeling output enhances integration of the manufacturing system.     

A fuzzy dispatching strategy for due-date scheduling of FMSs with information delays

Conventional dispatching strategies for FMSs with routing flexibility have typically employed simple heuristics such as work-in-next-queue (WINQ) and number-in-next-queue (NINQ). The effectiveness of these heuristics, however, deteriorates in FMSs whose operational environment must cope with information delays that are non-negligible in comparison to part processing times. Such delays could arise from planned activities, e.g., acquisition, selection, processing, and transfer of plant-wide system status information as well as from unplanned events such as ERP/IT system malfunctions, mismatch of software interfaces, and erroneous inventory master files, for example. Uncertainties from information delays make a strong case for the introduction of fuzzy controllers for making scheduling decisions. This paper introduces a novel fuzzy logic-based dispatching strategy to cope with a specific manifestation of information delays, called status review delay within FMSs. Status review information delays impact system performance adversely because of the obsolescent nature of the information used in the determination of dispatch decisions. A fuzzy dispatching strategy (FDS), designed specifically for deployment within FMSs where information delays are manifest, provides an appropriate alternative to conventional dispatching strategies such as WINQ and NINQ. In the design of an FDS, relevant system-based parameters are fuzzified and an appropriate rule base is designed. Simulation experiments demonstrate the superiority of an FDS over the conventional WINQ dispatching strategy using the mean tardiness, percent tardy, and mean flowtime performance measures.     

Controlling flexible manufacturing systems based on a dynamic selection of the appropriate operational criteria and scheduling policy

This study presents the development of a multi-criteria control methodology for flexible manufacturing systems (FMSs). The control methodology is based on a two-tier decision making mechanism. The first tier is designed to select a dominant decision criterion and a relevant scheduling rule set using a rule-based algorithm. In the second tier, using a look-ahead multi-pass simulation, a scheduling rule that best advances the selected criterion is determined. The decision making mechanism was integrated with the shop floor control module that comprises a real-time simulation model at the top control level and RapidCIM methodology at the low equipment control level. A factorial experiment was designed to analyze and evaluate the two-tier decision making mechanism and the effects that the main design parameters have on the system’s performance. Next, the proposed control methodology was compared to a selected group of scheduling rules/policies using DEA. The results demonstrated the superiority of the suggested control methodology as well as its capacity to cope with a fast changing environment.     

A dynamic heuristic-based algorithm to part input sequencing in flexible manufacturing systems for mass customization capability

In the increasingly competitive global markets, enterprises face challenges in responding to customer orders quickly, as well as producing customized products cost-effectively. This paper proposes a dynamic heuristic-based algorithm for the part input sequencing problem of flexible manufacturing systems (FMSs) in a mass customization (MC) environment. The FMS manufactures a variety of parts, and customer orders arrive dynamically with order size as small as one. Segmental set functions are established in the proposed algorithm to apply the strategy of dynamic workload balancing, and the shortest processing time (SPT) scheduling rule. Theoretical analysis is performed and the effectiveness of the algorithm in dynamic workload balancing under the complex and dynamic environment is proven. The application of the algorithm is illustrated by an example. The potential of its practical applications to the FMSs in make-to-order (MTO) supply chains is also discussed. Further research is provided.     

Object-Oriented Modeling for Flexible Manufacturing Systems

Object-oriented modeling provides a new way of thinking about flexible manufacturing systems, using models organized around real-world concepts. This paper describes how the object modeling technique can be used to develop integrated factory models that embrace factory process modeling as well as policy modeling. Such models can be used to assess how quickly a manufacturing organization can adjust its operations to meet changes in demands for products, consumer preferences, supplier quality, and lead times. These models also can be used as vehicles for studying the impact of introducing new product lines or new process technology without the disruption or expense of pilot projects or test setups.