An efficient heuristic for scheduling batches of parts in a flexible flow system

Flexible manufacturing systems (FMSs) are a class of automated systems that can be used to improve productivity in batch manufacturing. Four stages of decision making have been defined for an FMS—the design, planning, scheduling, and control stages. This research focuses on the planning stage, and specifically in the area of scheduling batches of parts through the system. The literature to date on the FMS planning stage has mostly focused on the machine grouping, tool loading, and parttype selection problems. Our research carries the literature a step further by addressing the problem of scheduling batches of parts. Due to the use of serial-access material-handling systems in many FMSs, the batch-scheduling problem is modeled for a flexible flow system (FFS). This model explicitly accounts for setup times between batches that are dependent on their processing sequence. A heuristic procedure is developed for this batch-scheduling problem—the Maximum Savings (MS) heuristic. The MS heuristic is based upon the savings in time associated with a particular sequence and selecting the one with the maximum savings. It uses a two-phase method, with the savings being calculated in phase I, while a branch-and-bound procedure is employed to seek the best heuristic solution in phase II. Extensive computational results are provided for a wide variety of problems. The results show that the MS heuristic provides good-quality solutions.     

An Evaluative Study of Operation Grouping Policies in an FMS

The increased use of flexible manufacturing systems to provide customers with diversified products efficiently has created a significant set of operational challenges for managers. This technology poses a number of decision problems that need to be solved by researchers and practitioners. In the literature, there have been a number of attempts to solve design and operational problems. Special attention has been given to machine loading problems, which involve the assignment of job operations and allocation of tools and resources to optimize specific measures of productivity. Most existing studies focus on modeling the problem and developing heuristics in order to optimize certain performance metrics rather than on understanding the problem and the interaction between the different factors in the system. The objective of this paper is to study the machine loading problem. More specifically, we compare operation aggregation and disaggregation policies in a random flexible manufacturing system (FMS) and analyze its interaction with other factors such as routing flexibility, sequencing flexibility, machine load, buffer capacity, and alternative processing-time ratio. For this purpose, a simulation study is conducted and the results are analyzed by statistical methods. The analysis of results highlights the important factors and their levels that could yield near-optimal system performance.     

Developing a Hybrid Programmable Logic Controller Platform for a Flexible Manufacturing System

In this article, we present the design and implementation of a flexible manufacturing system (FMS) control platform based on a programmable logic controller (PLC) and a personal computer (PC)-based visual man-machine interface (MMI) and data acquisition (DAS) unit. The key aspect of an FMS is its flexibility to adapt to changes in a demanding process operation. The PLC provides feasible solutions to FMS applications, using PC-based MMI/DAS, whereby PLCs are optimized for executing rapid sequential control strategies. PCs running MMI/DAS front-ends make intuitive operation interfaces, full of powerful graphics and reporting tools. Information from the PC can be distributed through a company's local area network or web using client-server technologies. Currently, with the convergence of underlying microprocessor technology and software programming techniques, many users find that PLCs provide a cost-effective solution to real-time control in small- to medium-sized process plants, especially when combined with supervisory PCs using hybrid systems. The major work of this article demonstrates that PLCs are responsive to rapid and repetitious control tasks, using PCs that present the flow of information automation and accept operator instructions, thereby providing the user a tool to modify and monitor the process as the requirements change.     

Production planning of a flexible manufacturing system in a material requirements planning environment

Early flexible manufacturing system (FMS) production planning models exhibited a variety of planning objectives; typically, these objectives were independent of the overall production environment. More recently, some researchers have proposed hierarchical production planning and scheduling models for FMS. In this article, we examine production planning of FMS in a material requirements planning (MRP) environment. We propose a hierarchical structure that integrates FMS production planning into a closed-loop MRP system. This structure gives rise to the FMS/MRP rough-cut capacity planning (FMRCP) problem, the FMS/MRP grouping and loading (FMGL) problem, and the FMS/MRP detailed scheduling problem. We examine the FMRCP and FMGL problems in detail and present mathematical programming models for each of these problems. In particular, the FMRCP problem is modeled as a generalized assignment problem (GAP), and a GAP-based heuristic procedure is defined for the problem. We define a two-phase heuristic for the FMGL problem and present computational experience with both heuristics. The FMRCP heuristic is shown to solve problems that exhibit a dependent-demand relation within the FMS and with FMS capacity utilization as high as 99 percent. The FMGL heuristic requires very little CPU time and obtains solutions to the test problems that are on average within 1.5 percent of a theoretical lower bound. This FMS/MRP production planning framework, together with the resulting models, constitutes an important step in the integration of FMS technology with MRP production planning. The hierarchical planning mechanism directly provides for system-level MRP planning priorities to induce appropriate production planning and control objectives on the FMS while simultaneously allowing for necessary feedback from the FMS. Moreover, by demonstrating the tractability of the FMRCP and FMGL problems, this research establishes the necessary groundwork upon which to explore systemwide issues pertaining to the coordination of the hierarchical structure.     

A comparative study of FMS tool allocation and part type selection approaches for a varying part type mix

Hankins and Rovito (1984) examined the impact of different tool policies on cutting tool inventory levels and spindle utilization for a flexible manufacturing system (FMS). This study provides a broader perspective of the impact of tool allocation approaches on flow times, tardiness, percent of orders tardy, machine utilization, and robot utilization. Part type selection procedures have been suggested for the FMS prerelease planning problem. However, very little research has specifically evaluated the part type selection procedures across different tool allocation approaches. Also, with the exception of Stecke and Kim (1988, 1991) no other known study has provided any insights on what tool allocation approaches are appropriate when processing different mixes of part types. This research is devoted to addressing those issues. Three tool allocation approaches, three production scheduling rules, and three levels of part mix are evaluated in this study through a similation model of a flexible manufacturing system. The specific impacts of the tool approaches, their interaction effects with the part type selection rules, and their effectiveness at different part type mix levels are provided through the use of a regression metamodel.     

Loading problems with tool management in flexible manufacturing systems: A few integer programming models

In automated production systems like flexible manufacturing systems (FMSs), an important issue is to find an adequate workload for each machine for each time period. Many integer linear programming (ILP) models have been proposed to solve the FMS loading problems, but not all of them take tools into account. Those that do not consider tooling are quite unrealistic, especially when setup times are important with respect to processing times. When tool loading has to be handled by the model, the load assignment may have to be changed completely. In this article we consider FMSs with a tool management of the following type: the system works in time periods whose durations are fixed or not; and tools are loaded on the machines at the beginning of each time period and stay there for the whole time period. Tool changes may occur only at the end of each time period when the system is stopped. We present some integer programming models for handling these situations with several types of objectives. Emphasis is laid on the ILP formulations. Computational complexities are discussed.     

A Dynamic Tool Requirement Planning Model for Flexible Manufacturing Systems

Despite their strategic potential, tool management issues in flexible manufacturing systems (FMSs) have received little attention in the literature. Nonavailability of tools in FMSs cuts at the very root of the strategic goals for which such systems are designed. Specifically, the capability of FMSs to economically produce customized products (flexibility of scope) in varying batch sizes (flexibility of volume) and delivering them on an accelerated schedule (market response time) is seriously hampered when required tools are not available at the time needed. On the other hand, excess inventory of tools in such systems represents a significant cost due to the expensive nature of FMS tool inventory. This article constructs a dynamic tool requirement planning (DTRP) model for an FMS tool planning operation that allows dynamic determination of the optimal tool replenishments at the beginning of each arbitrary, managerially convenient, discrete time period. The analysis presented in the article consists of two distinct phases: In the first phase, tool demand distributions are obtained using information from manufacturing production plans (such as master production schedule (MPS) and material requirement plans (MRP)) and general tool life distributions fitted on actual time-to-failure data. Significant computational reductions are obtained if the tool failure data follow a Weibull or Gamma distribution. In the second phase, results from classical dynamic inventory models are modified to obtain optimal tool replenishment policies that permit compliance with such FMS-specific constraints as limited tool storage capacity and part/tool service levels. An implementation plan is included.     

Scheduling algorithms for a two-machine flexible manufacturing system

The flexible manufacturing system (FMS) considered in this paper is composed of two CNC machines working in series—a punching machine and a bending machine connected through rollers acting as a buffer system of finite capacity. The main difference between the present problem and the standard two-machine flow shop problem with finite intermediate capacity is precisely the buffer system, which in our problem consists of two stacks of parts supported by rollers: the first stack contains the output of the punching machine, while the second stack contains the input for the bending machine. When the second stack is empty, the first stack may be moved over. Furthermore, the capacity of each stack depends on the particular part type being processed. The FMS can manufacture a wide range of parts of different types. Processing times on the two machines are usually different so that an unbalance results in their total workload. Furthermore, whenever there is a change of the part type in production, the machines must be properly reset—that is, some tools need to be changed or repositioned. A second important difference between the present problem and the usual two-machine flow shop problem is the objective. Given a list ofp part types to be produced in known quantities, the problem considered here is how to sequence or alternate the production of the required part types so as to achieve various hierarchical targets: minimize the makespan (the total time needed to complete production) and, for instance, compress the idle periods of the machine with less workload into a few long enough intervals that could be utilized for maintenance or other reasons. Although Johnson's rule is optimal in some particular cases, the problem addressed in the paper isNP-hard in general: heuristic procedures are therefore provided.     

An Object-Oriented Approach for Flexible Manufacturing Control Systems Analysis and Design Using the Unified Modeling Language

In reacting to global competition and rapidly changing customer demands, industrial business organizations have developed a strong interest in flexible automation. The aim of flexible automation focuses on achieving agility in handling uncertainties from internal or external environments. Modeling complex structures, promoting reuse, and shortening the development time cycle are particularly significant aspects in the analysis and design of CIM systems, where heterogeneous elements have to be integrated in a complex control architecture. The design methodology for FMS control software involves the abstraction of an FMS and the estimation of the system performances. The aim of this activity is to suggest the optimal configuration of an FMS for given specifications, through simulation tools. In the software engineering field, object-oriented (OO) approaches have proven to be a powerful technique with respect to such aspects. The unified modeling language (UML), by using OO design methodologies, can offer reusability, extendibility, and modifiability in software design. Also, it bridges the gap that exists between the OO analysis and design area and the area of OO programming by creating an integrative metamodel of OO concepts. The specific goal of this paper is to formulate a new methodology for developing reusable, extendible, and modifiable control software for an FMS in an object-oriented environment. It is demonstrated that, with few diagrams, UML can be used to model such systems without being associated with other modeling tools.     

Classification in LCA: Building of a coherent family of criteria

There is a very close analogy between Life Cycle Assessment (LCA) and decision making tools such as the multicritcria approach. LCA is a particular model of a multicriteria decision making tool which is applied to environmental data. The similarities between LCA and multicriteria decision making tools are highlighted. The strict precision of multicriteria decision making tools is used to improve classification. For this, six dimensions (or axes of significance) of environmental impacts can be distinguished. The aim is to build a coherent family of environmental data from these considerations. Rules for the building of this family are proposed.     

A decision-making approach to the operation of flexible manufacturing systems

This paper introduces a generic decision-making framework for assigning resources of a manufacturing system to production tasks. Resources are broadly defined production units, such as machines, human operators, or material handling vehicles; and tasks are activities performed by resources. In the specific context of FMS, resources correspond to individual machines; tasks correspond to operations to be performed on parts. The framework assumes a hierarchical structure of the system and calls for the execution of four consecutive steps to make a decision for the assignment of a resource to a task. These steps are 1) establishment of decision-making criteria, 2) formation of alternative assignments, 3) estimation of the consequences of the assignments, and 4) selection of the best alternative assignment. This framework has been applied to an existing FMS as an operational policy that decides what task will be executed on which resource of this FMS. Simulation runs provide some initial results of the application of this policy. It is shown that the policy provides flexibility in terms of system performance and computational effort.     

Workload balance and part-transfer minimization in flexible manufacturing systems

Problems related to the flow management of a flexible manufacturing system (FMS) are here formulated in terms of combinatorial optimization. We consider a system consisting of several multitool automated machines, each one equipped with a possibly different tool set and linked to each other by a transportation system for part moving. The system operates with a given production mix. The focused flow-management problem is that of finding the part routings allowing for an optimal machine workload balancing. The problem is formulated in terms of a particular capacity assignment problem. With the proposed approach, a balanced solution can be achieved by routing parts on a limited number of different paths. Such a balancing routing can be found in polynomial time. We also give polynomial-time and-space algorithms for choosing, among all workload-balancing routings, the ones that minimize the global amount of part transfer among all machines.     

Tool addition strategies for flexible manufacturing systems

The allocation of tools to machines determines potential part routes in flexible manufacturing systems. Given production requirements and a minimum feasible set of tools, the decision of how to fill vacant slots in tool magazines to maximize routing flexibility is shown to be a minimum cost network flow problem for the cases when routing flexibility is a function of the average workload per tool aggregated over tool types, or of the number of possible routes through the system. A linear programming model is then used to plan a set of routes for each part type so as to minimize either the material handling requirement or the maximum workload on any machine. The impact of these tool addition strategies on the material handling and workload equalization is investigated and computational results presented. The advantage of the overall approach is computational simplicity at each step and the ability to react to dynamic changes.     

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.     

Risk-aware limited lookahead control for dynamic resource provisioning in enterprise computing systems

Utility or on-demand computing, a provisioning model where a service provider makes computing infrastructure available to customers as needed, is becoming increasingly common in enterprise computing systems. Realizing this model requires making dynamic, and sometimes risky, resource provisioning and allocation decisions in an uncertain operating environment to maximize revenue while reducing operating cost. This paper develops an optimization framework wherein the resource provisioning problem is posed as one of sequential decision making under uncertainty and solved using a limited lookahead control scheme. The proposed approach accounts for the switching costs incurred during resource provisioning and explicitly encodes risk in the optimization problem. Simulations using workload traces from the Soccer World Cup 1998 web site show that a computing system managed by our controller generates up to 20% more profit than a system without dynamic control while incurring low control overhead.

An Index of Regional Sustainability: A GIS-based multiple criteria analysis decision support system for progressing sustainability

GIS (Geographical Information Systems) based decision support tools will be useful in helping guide regions to sustainability. These tools need to be simple but effective at identifying, for regional managers, areas most in need of initiatives to progress sustainability. Multiple criteria analysis (MCA) has been used as a decision support tool for a wide number of applications, as it provides a systematic framework for evaluating various options. It has the potential to be used as a tool for sustainability assessment, because it can bring together the sustainability criteria from all pillars, social, economic and environmental, to give an integrated assessment of sustainability. Furthermore, the use of GIS and MCA together is an emerging addition to conducting sustainability assessments.This paper further develops a sustainability assessment framework developed for the Glenelg Hopkins Catchment Management Authority region of Victoria, Australia by providing a GIS-based decision support system for regional agencies. This tool uses multiple criteria analysis in a GIS framework to assess the sustainability of sub-catchments in the Glenelg Hopkins Catchment. The multiple criteria analysis based on economic, social and environmental indicators developed in previous stages of this project was used as the basis to build a model in ArcGIS^®. The GIS-based multiple criteria analysis, called An Index of Regional Sustainability Spatial Decision Support System (AIRS SDSS), produced maps showing sub-catchment sustainability, and environmental, social and economic condition. As a result, this tool is able to highlight those sub-catchments most in need of assistance with achieving sustainability. It will also be a valuable tool for evaluation and monitoring of strategies for sustainability. This paper shows the usefulness of GIS-based multiple criteria analysis to enhance the monitoring and evaluation of sustainability at the regional to sub-catchment scale.     

Soluble factors released by ATDC5 cells affect the formation of calcium phosphate crystals

During biomineralization the organism controls the nature, orientation, size and shape of the mineral phase. The aim of this study was to investigate whether proteins or vesicles that are constitutively released by growing ATDC5 cells have the ability to affect the formation of the calcium phosphate crystal. Therefore, subconfluent cultured ATDC5 cells were incubated for 1 h in medium without serum. Subsequently, medium was harvested and incubated for 24 h in the presence of additional Pi. This resulted in the formation of flat mineralizing structures (FMS), consisting of complex irregularly shaped flat crystals, which occasionally contained fiber-like structures ( approximately 40 microm in size). Without pre-incubation of medium with cells, only small punctate (dot like) calcium phosphate precipitates were observed. The formation of FMS was shown to be caused by soluble factors released by subconfluent ATDC5 cells. Proteomic analysis by mass spectrometry showed that FMS contained a specific set intracellular proteins, serum proteins, and extracellular matrix proteins. Bulk cytosolic proteins derived from homogenized cells or serum proteins did, however, not induce the formation of FMS. Conditioned medium from HeLa, CHO K1, RAW 264.7 and MDCK cells was also capable to form FMS under our experimental conditions. Therefore the formation of FMS seems to be caused by specific soluble factors constitutively released by ADTC5 and other cells. This in vitro model system can be used as a tool to identify factors that affect the shape of the biomineral phase.     

Modeling FMS with decision Petri nets

Decision point extended timed Petri nets or decision Petri nets (DPN) are introduced as an extended modeling framework for FMS performance evaluation. The decision point extension allows the explicit modeling of the control of the flow of tokens in timed Petri nets and hence represents the control of the flow of material, resources, and information in FMS. Further, the concept of a bounded transition is proposed to conveniently model the blocking logic in an FMS with limited buffer capacities. The motivation to present these conventions is to develop a user-friendly graphic model to represent FMS designs for analysis by discrete event simulation. DPN affords concise models that can be conveniently developed and easily transformed into discrete event simulation models. With the help of a simple FMS example, which includes a number of part types, loading rules, dispatching rules, and probabilistic branching (at an inspection station), we illustrate the DPN model development. As an illustration of the ease with which it can be tranformed into a simulation model, we have developed a generalized simulator called ROBSIM and outline here its methodological basis. The proposed concepts should be of interest to users of discrete event simulation in FMS design or elsewhere to tap the potential of basic Petri net concepts for graphic representation and specification purposes. In particular, our work should encourage other researchers to develop extensions relevant to their own areas of interest.     

Dynamic flexibility metrics for capability and capacity

In production environments, such as Flexible Manufacturing Systems (FMSs), the schedule can be disturbed by the occurrence of unplanned events. Machines stop for major failures, maintenance, tool changes due to wear, or tool reassignments. The rescheduling process, however, can be costly. In this study, a dynamic measure of flexibility which helps to determine an appropriate time for rescheduling an FMS has been defined and investigated. Flexibility is defined as a function of Capability and Capacity. Accordingly, two metrics have been developed to monitor the capability and capacity efficiency of each machine in the system for responding to the dynamic system status. The value of each metric falls between 0 and 1 at all times. Higher values in the capability metric mean better machine selection and part distribution strategies among the machines. Higher values for the capacity metric mean higher machine utilization in the production plan. Based on the interaction between the metrics and their respective behavior in the system, four states have been identified and characterized. Simulations of various scenarios can be used to demonstrate the use of these metrics for monitoring FMS operations and determining appropriate times for rescheduling and tool reassignment.