Work flow control in the flexible flow line

This research involves the development and evaluation of a part flow control model for a type of flexible manufacturing system (FMS) called a dedicated flexible flow line (FFL). In the FFL, all part types flow along the same path between successive machine groups. The specific objective of the part flow control model for the FFL is to minimize makespan for a given set of parts produced in a FFL near-term schedule, given fixed available buffer constraints. The control model developed in this research involved the repeated, real-time execution of a mathematical programming algorithm. The algorithm attempts to release the right mix of parts at the tight time to keep the FFL operating smoothly. The focus of the approach is directed toward managing WIP buffers for each machine group queue. The algorithm specifically incorporates stochastic disturbance factors such as machine failures. Through a limited number of simulation experiments, performance of the control model is shown to be superior to other parts releasing and control methods reported in the literature.     

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.     

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.     

Scheduling parallel machines with major and minor setup times

This article discusses the problem of scheduling a large set of parts on an FMS so as to minimize the total completion time. Here, the FMS consists of a set of parallel identical machines. Setup time is incurred whenever a machine switches from one type of part to another. The setup time may be large or small depending on whether or not the two part types belong to the same family. This article describes a fast heuristic for this scheduling problem and derives a lower bound on the optimal solution. In computational tests using random data and data from an IBM card test line, the heuristic archieves nearly optimal schedules.     

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.     

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.     

Multiple-Objective Scheduling for the Hierarchical Control of Flexible Manufacturing Systems

This paper presents a hierarchical approach to scheduling flexible manufacturing systems (FMSs) that pursues multiple performance objectives and considers the process flexibility of incorporating alternative process plans and resources for the required operations. The scheduling problem is solved at two levels: the shop level and the manufacturing system level. The shop level controller employs a combined priority index developed in this research to rank shop production orders in meeting multiple scheduling objectives. To overcome dimensional complexity and keep a low level of work-in-process inventory, the shop controller first selects up to three production orders with the highest ranking as candidates and generates all possible release sequences for them, with or without multitasking. These sequences are conveyed to the manufacturing system controller, who then performs detailed scheduling of the machines in the FMS using a fixed priority heuristic for routing parts of multiple types while considering alternative process plans and resources for the operations. The FMS controller provides feedback to the shop controller with a set of suggested detailed schedules and projected order completion times. On receiving these results, the shop controller further evaluates each candidate schedule using a multiple-objective function and selects the best schedule for execution. This allows multiple performance objectives of an FMS to be achieved by the integrated hierarchical scheduling approach.     

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.     

Sequencing of Parts in Robotic Cells

This paper considers scheduling problems in robotic cells that produce a set of part types on several machines served by one robot. We study the problem of sequencing parts of different types in a cell to minimize the production cycle time when the sequence of the robot moves is given. This problem is NP-hard for most of the one-unit robot move cycles in a robotic cell with more than two machines and producing more than two part types. We first give a mathematical formulation to the problem, and then propose a branch-and-bound algorithm to solve it. The bounding scheme of this algorithm is based on relaxing, for all of the machines except two, the constraints that a machine should be occupied by a part for a period at least as long as the processing time of the part. The lower bound obtained in this way is tight. This relaxation allows us to overcome the complexity of the problem. The lower bound can be computed using the algorithm of Gilmore and Gomory. Computational experiments on part sequencing problems in three-machine robotic cells are given.     

Dispatching and Conflict-Free Routing of Automated Guided Vehicles: An Exact Approach

This article presents an exact solution approach for the problem of the simultaneous dispatching and conflict-free routing of automated guided vehicles. The vehicles carry out material handling tasks in a flexible manufacturing system (FMS). The objective is to minimize the costs related to the production delays. The approach is based on a set partitioning formulation. The proposed model is solved to optimality by a column generation method, which is embedded in a branch-and-cut exploration tree. The proposed model and solution methodology are tested on several scenarios with up to four vehicles in the manufacturing system. The results show that most of these scenarios can be solved to optimality in less than three minutes of computational time.     

Capacity optimization of flexible manufacturing systems under budget constraints

The capacity of a flexible manufacturing system (FMS) is optimized with the objective to maximize the system's throughput, while a budget constraint is considered. Decisions are performed on the capacity of machine groups (sets of identical machines), the transportation system and, in case of a significant cost impact, the number of pallets in the system. Throughput evaluation is achieved either by an open finite queueing network or by a closed queueing network if the number of pallets is included in the decision process. For both cases the solution procedure is based on the marginal allocation scheme.     

Inventory issues in incremental FMS implementation

In recent years, numerous studies have demonstrated convincingly that impressive benefits can be obtained by the adoption of flexible manufacturing systems (FMSs). To obtain the benefits of an FMS requires the development of a completely integrated system. However, FMS implementations are frequently done incrementally through the introduction of subsystems such as flexible machining centers into an existing conventional system. The purpose of this research is to investigate some of the operational issues associated with the introduction of a CNC (computer numerically controlled) machine tool into a conventional system. The primary objective of the present study is to explore the relative effects on inventory holding cost of installing a single CNC at different locations within three different system configurations. Additionally, the study examines the sensitivity of these impacts to changes in (1) System utilization; (2) the ratios of setup times to run times in the conventional work centers; and (3) the rates of increase in holding costs for parts as they move through the system. Results indicated that, in general, introduction of a CNC into an otherwise conventional system reduces inventory holding cost for the system as a whole. However, the degree of this reduction varies depending on the position of the CNC in the system. In some cases the reduction in inventory holding cost is substantial, while in other cases it is relatively small.     

PCB assembly scheduling with alternative nozzle types for one component type

The placement machine is the bottleneck of a printed circuit board (PCB) assembly line. The type of machine considered in this paper is the beam-type placement machine that can simultaneously pick up several components from feeders. It is assumed that the number of nozzle types (NTs) is less than the number of heads on the beam. The objective of the PCB assembly scheduling for a single placement machine is to minimize the cycle time based on the average machine operation time instead of the travelling distance. To minimize the cycle time, the number of turns and the number of pickups should be minimized. The PCB assembly scheduling is hierarchically decomposed into four problems: the nozzle assignment problem, the head allocation problem, the component type (CT) grouping problem and the pickup clustering problem, which are optimized successively and iteratively. First, the nozzle assignment problem considering alternative NTs for one CT is dealt with by the proposed genetic algorithm. For a given nozzle assignment solution, the head allocation problem is solved by a previously greedy heuristic to minimize the number of turns.Then, the CT grouping problem and the pickup clustering problem are solved by a proposed greedy heuristic and a modified agglomerative hierarchical clustering approach, respectively, to minimize the number of pickups. Numerical experiments are carried out to examine the performances of these proposed heuristic approaches. The importance of considering alternative NTs for one CT for the cycle time is also confirmed.     

A Genetic-Based Vision System for Cross-Functional Integration in Flexible Manufacturing: A Tutorial and Application

Machine vision has the potential to significantly impact both quality and productivity in automated manufacturing, due to its versatility, flexibility, and relative speed. Unfortunately, algorithmic development has not kept pace with advances in vision hardware technology, particularly in the areas of analysis and decision making. In this article, a tutorial is presented that explains how a genetic algorithm can be applied to vision systems for shape analysis and quality assessment. The control parameters for the algorithm are optimized by conducting experiments of Taguchi's approach to parameter design. The main objective behind this algorithm is to explain an application of the vision system that uses upstream design data of machined parts of different types for downstream metrology and quality decision making in the environment of flexible manufacturing. The part types used for demonstration are restricted to planar polygonal profiles generated by projecting 3D objects onto a 2D inspection plane. The input to the system is a set of boundary features of the part being analyzed, and the outputs from the system include the estimators of size, orientation, position, and out-of-profile error of the part. The system can analyze machined parts of different types without modifying software programs and parameter settings, which makes it generic and flexible, and is inherently suitable for on-line implementation in FMS environments.     

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.     

A Genetic Algorithm Approach to the Scheduling of FMSs with Multiple Routes

Usually, most of the typical job shop scheduling approaches deal with the processing sequence of parts in a fixed routing condition. In this paper, we suggest a genetic algorithm (GA) to solve the job-sequencing problem for a production shop that is characterized by flexible routing and flexible machines. This means that all parts, of all part types, can be processed through alternative routings. Also, there can be several machines for each machine type. To solve these general scheduling problems, a genetic algorithm approach is proposed and the concepts of virtual and real operations are introduced. Chromosome coding and genetic operators of GAs are defined during the problem solving. A minimum weighted tardiness objective function is used to define code fitness, which is used for selecting species and producing a new generation of codes. Finally, several experimental results are given.     

Dynamic load control policies for a flexible manufacturing system with stochastic processing rates

Real-time scheduling and load controls of FMSs are complex processes in which the control logic must consider a broad spectrum of instantaneous state variables while taking into account the probabilistic future impact of each decision at each time epoch. These processes are particularly important in the management of modern FMS environment, since they are known to have a significant impact on the FMS productive capacity and economic viability. In this article we outline the approach developed for dynamic load controls within an FMS producing a variety of glass lenses. Two revenue-influencing objective functions are evaluated for this capital-intensive facility. It is shown that by using Semi-Markovian modeling concepts, the FMS states need to be observed only at certain decision epochs. The mean holding time in each state is then obtained using the probability distribution function of the conditional state occupancy times. Several key performance measures are then derived by means of the value equations. In addition, the structure of the optimal policies are exemplified for a variety of operational parameters. It is shown that the optimal policies tend to generate higher buffer stocks of parts in those work centers having the highest revenue-generation rates. These buffer stocks get smaller and smaller as the relative processing capacity of the centers increases. Similar observations lead us to the introduction of several promising heuristics that capture the structural properties of the optimal policies with a significantly smaller computational effort. Results of the empirical evaluation of these heuristics are also analyzed here.     

Dissimilarity Maximization Method for Real-time Routing of Parts in Random Flexible Manufacturing Systems

This paper presents a dissimilarity maximization method (DMM) for real-time routing selection and compares it via simulation with typical priority rules commonly used in scheduling and control of flexible manufacturing systems (FMSs). DMM aims to reduce the congestion in the system by selecting a routing for each part among its alternative routings such that the overall dissimilarity among the selected routings is maximized. In order to evaluate the performance of DMM, a random FMS, where the product mix is not known prior to production and off-line scheduling is not possible, is selected for the simulation study. A software environment that consists of a computer simulation model, which mimics a physical system, a C++ module, and a linear program solver is used to implement the DMM concept. In addition to DMM, the simulation study uses two priority rules for routing (i.e., machine) selection and seven priority rules for selecting parts awaiting service at machine buffers. The results show (1) DMM outperforms the other two routing selection rules on production rate regardless of the part selection rule used, and (2) its performance is highly dependent on the part selection rules it is combined with.     

An Analytical Queueing Network Model for Flexible Manufacturing Systems with a Discrete Handling Device and Transfer Blockings

In this paper, we study job shop-like flexible manufacturing systems (FMSs) with a discrete material handling system (MHS). In such FMSs, the MHS is a critical device, the unavailability of which may induce transfer blockings of the machines. The FMS devices therefore are hierarchically structured into primary and secondary devices to manage such blocking and avoid deadlocks in these FMSs. For evaluating the quantitative steady-state performance of such FMSs, we propose an analytical queueing network model that relies on an approximate method proposed for analyzing computer systems with simultaneous possessions of resources. Such a model is obtained using the concept of passive resources and by aggregating the FMS workload data so that models are much more tractable. The analytical results are validated against discrete event simulation and shown to be very encouraging. We also show how to increase their robustness, especially under light workload conditions, by modifying an assumption of the method concerning service time distributions.     

Hybrid FMS control architectures based on holonic principles

The escalation in processor technologies and the corresponding reduction in costs have enabled alternative FMS control architectures to be developed without the restrictions of “fixed machine controller boundaries”. These new architectures can be based upon the use of intelligent servo axes, which are desccribed in this article, as flexible numerical control (FNC). In current parlance, the FNC is a “part movement holon” within a manufacturing cell. The control architectures that can be derived from the FNC concept are referred to as hybrid architectures and share the emerging attributes of holonics. This article details the problems that arise in the scheduling and control of FMSs in the light of hybrid control architectures. A number of traditional scheduling approaches have been devised to cope with the scheduling of parts to discrete machines, but the problem here is to ascribe the processing (machining) of part features to axis groups. This article documents how two research programs, undertaken at the CIM Centre at Swinburne University of Technology in Hawthorn, Victoria, Australia, have endeavored to address the problem of hybrid architectures and their associated scheduling.