Optimum loading of machines in a flexible manufacturing system using a mixed-integer linear mathematical programming model and genetic algorithm

Machine loading problem in a flexible manufacturing system (FMS) encompasses various types of flexibility aspects pertaining to part selection and operation assignments. The evolution of flexible manufacturing systems offers great potential for increasing flexibility by ensuring both cost-effectiveness and customized manufacturing at the same time. This paper proposes a linear mathematical programming model with both continuous and zero-one variables for job selection and operation allocation problems in an FMS to maximize profitability and utilization of system. The proposed model assigns operations to different machines considering capacity of machines, batch-sizes, processing time of operations, machine costs, tool requirements, and capacity of tool magazine. A genetic algorithm (GA) is then proposed to solve the formulated problem. Performance of the proposed GA is evaluated based on some benchmark problems adopted from the literature. A statistical test is conducted which implies that the proposed algorithm is robust in finding near-optimal solutions. Comparison of the results with those published in the literature indicates supremacy of the solutions obtained by the proposed algorithm for attempted model.     

Integrated scheduling of resource-constrained flexible manufacturing systems using constraint programming

This contribution presents a novel approach to address the scheduling of resource-constrained flexible manufacturing systems (FMSs). It deals with several critical features that are present in many FMS environments in an integrated way. The proposal consists in a constraint programming (CP) formulation that simultaneously takes into account the following sub-problems: (i) machine loading, (ii) manufacturing activities scheduling, (iii) part routing, (iv) machine buffer scheduling, (v) tool planning and allocation, and (vi) AGV scheduling, considering both the loaded and the empty movements of the device. Before introducing the model, this work points out the problems that might appear when all these issues are not concurrently taken into account. Then, the FMS scheduling model is presented and later assessed through several case-studies. The proposed CP approach has been tested by resorting to problems that consider dissimilar number of parts, operations per part, and tool copies, as well as different AGV speeds. The various examples demonstrate the importance of having an integrated formulation and show the important errors that can occur when critical issues such as AGV empty movements are neglected.     

A computer simulation model for studying the performance of coordinate measuring machines

The increasing trend toward computer-integrated manufacturing (CIM) in today's industry created a need for an effective process control. The objective of the inspection process is not only preventing shipment of defective parts but also providing a feedback to keep the manufacturing process in control. Through data processing capability, speed, and flexibility of operation, coordinate measuring machines (CMMs) play an important role for computer-integrated manufacturing (CIM). This paper introduces coordinate measuring machines and studies their performance. A computer simulation method for studying the performance of such machines working in a production line is developed. In this paper, CMM performance is measured by its speed and flexibility in performing measurements. In flexible manufacturing systems (FMS), CMMs serve as the inspection work station where arrival time of parts to be measured vary according to the flow of operations. The developed simulation model provides information about the machine, scheduled time for parts to be measured, and delay time for the measuring process.     

Multi-period part selection and loading problems in flexible manufacturing systems

We consider multi-period part selection and loading problems in flexible manufacturing systems with the objective of minimizing subcontracting costs. The part selection problem is to select sets of part types and to determine their quantities to be produced during the upcoming planning horizon while satisfying due dates of all orders for the parts, and the loading problem involves allocation of operations and required tools to machines. Production demands should be satisfied for periods through subcontracting if production demands cannot be satisfied by the system due to machine capacity or tool magazine capacity constraints. For the part selection and loading problems, we develop three iterative algorithms, called the forward algorithm, the backward algorithm and the capacity approximation algorithm, that solve the part selection and loading problems iteratively for each period. To compare the three algorithms, a series of computational experiments is done on randomly generated test problems.     

Integrating manufacturing resources planning (MRP II) with flexible manufacturing systems (FMS)

This paper will describe the gap that exists between the Manufacturing Resources Planning (MRP II) system and the Flexible Manufacturing System (FMS) and discuss several approaches for closing the gap. Considerable effort has gone into developing and integrating the various modules in the MRP II system. The modules for business planning, production planning, master production scheduling, material requirement planning, capacity requirements planning, and shop floor control have been integrated into a comprehensive computer package for planning and controlling manufacturing. At the same time, a similar effort has been underway to develop and integrate the several subsystems of a FMS. In particular, a number of computer control systems have been developed to automatically plan and control the operations of NC machines with automated tool changers, automated material handling, and automated test and inspection equipment. Unfortunately these two efforts have proceeded relatively independently with little interaction between the two groups. If computer integrated manufacturing (CIM) is to become a reality, the resulting gap must be closed, and closed rapidly.     

Beam search algorithm for capacity allocation problem in flexible manufacturing systems

This study considers the operation assignment and tool allocation problem in flexible manufacturing systems. A set of operations together with their required tools are selected so as to maximize the total weight. The machines have limited time and tool magazine capacities and the tools are available in limited quantities. We develop a beam search algorithm and obtain near optimal solutions for large size problems very quickly.     

An integrated manufacturing planning assistant — IMPA

In this paper, we describe our development of a fully integrated manufacturing planning assistant (IMPA) system, which is able to: (1) interpret the finished part requirements directly from the designer's CAD systems or solid modelers without user intervention or special feature coding; (2) check the machinability of a designed part; (3) automatically generate a process plan, a tool path and an NC (numerically controlled) code, and (4) support interactive user modification of the resulting plans, tool paths and NC code. A demonstration version of the system was designed to provide automated assistance for the planning of machining processes on three-axes NC machine tools. The underlying architectural concepts and reasoning algorithms can be extended to more complex machines such as four-or-more-axes NC machines. CAD, CAE, and CAM including robotic, FMS (flexible manufacturing system) and NC machines are widely used in industry today. There is increasing interest in automation of factory control software Merchant, (1988); this includes automating the generation of the control programs — that is, in developing systems which will automatically produce the NC code for machining the part, given a model of the part, the shape of the raw material, and the machine specifications. With such systems, there are several difficulties in the manual preparation of an NC program code such as, long and tedious calculations, high risk of error in data preparation, etc., which need to be eliminated. This is a critical step toward the integration of CAD and CAM into a truly concurrent engineering and manufacturing environment.     

Loading of pallets on identical CNC machines with cyclic schedules

Flexible manufacturing systems (FMS) are generally set up to process a wide variety of parts with low to medium volume demand. The loading problem in FMS is a short-term decision issue, which addresses the simultaneous processing of a set of different parts in an efficient manner on capital-intensive resources. This study focuses on cyclic schedules in loading pallets carrying groups of identical parts to CNC machining centers. A predefined stream of pallets fixtured for different part types is repeatedly supplied to every CNC machine in cycles. Moreover, a limited number of pallets have to be shared among the cycles of machines to keep utilization and the overall throughput rate at acceptably high levels. The solution approach is an integrated mix of optimization and simulation methodologies. The validation of the model is based on data from past 6 months of operation. Comparisons are made retrospectively.     

A heuristic based on multi-stage programming approach for machine-loading problem in a flexible manufacturing system

Manufacturing industries are rapidly changing from economies of scale to economies of scope, characterized by short product life cycles and increased product varieties. This implies a need to improve the efficiency of job shops while still maintaining their flexibility. These objectives are achieved by Flexible manufacturing systems (FMS). The basic aim of FMS is to bring together the productivity of flow lines and the flexibility of job shops. This duality of objectives makes the management of an FMS complex. In this article, the loading problem in random type FMS, which is viewed as selecting a subset of jobs from the job pool and allocating them among available machines, is considered. A heuristic based on multi-stage programming approach is proposed to solve this problem. The objective considered is to minimize the system unbalance while satisfying the technological constraints such as availability of machining time and tool slots. The performance of the proposed heuristic is tested on 10 sample problems available in FMS literature and compared with existing solution methods. It has been found that the proposed heuristic gives good results.     

Analysis of dynamic due-date assignment models in a flexible manufacturing system

This paper investigates the effects of dynamic due-date assignment models (DDDAMs), routing flexibility levels (RFLs), sequencing flexibility levels (SFLs) and part sequencing rules (PSRs) on the performance of a flexible manufacturing system (FMS) for the situation wherein part types to be produced in the system arrive continuously in a random manner. The existing DDDAMs considered are dynamic processing plus waiting time and dynamic total work content. A new model known as dynamically estimated flow allowance (DEFA) has also been developed and investigated. The routing flexibility of the system and the sequencing flexibility of parts are both set at three levels. A discrete-event simulation model of the FMS is used as a test-bed for experimentation. The performance measures evaluated are mean flow time, mean tardiness, percentage of tardy parts and mean flow allowance. The statistical analysis of the simulation results reveals that there are significant interactions among DDDAMs, RFLs, SFLs and PSRs for all the performance measures. The proposed DEFA model provides the minimum percentage of tardy parts in all the experiments. Regression-based metamodels have been developed using the simulation results. The metamodels are found to provide a good prediction of the performance of the FMS within the domain of their definition.     

Tool requirements in manufacturing systems under dynamic tool sharing

This paper addresses a tooling problem in automated manufacturing systems under dynamic tool assignment policy. In this type of systems, while parts stay on a machine all through its operations, the tools required (but not available on the machine) are delivered in time for requirements. The system performance is restricted to a great extent by tooling constraints. This paper presents an analytical method to determine tool requirement levels under dynamic production environment. The appropriate tool duplication levels are determined by trading off tool duplication levels and tool waiting time. Simulation studies are used to verify the performance of the proposed analytical model.     

Expert systems: An application in flexible manufacturing

Flexible manufacturing systems (FMS) are needed to provide manufacturing operations with the capability to adjust, in real time, to changes in the manufacturing environment. Realization of the goals of flexible manufacturing is governed by the ability of the FMS to maintain adequate information on the factory to assist in generating scenarios from product planning to operations and performance. This leads to a view where the factory is represented as an integrated information system. To facilitate the analysis of information requirements and the design of information systems for flexible manufacturing, an expert support system (ESS) which can be used to model and study the various structures is described. This ESS uses the information cell model to build these information structures. Petri net representations of these structures and their interactions are then constructed. The ESS may now be used to exercise these models and study their performance using time and cost measures.     

A constraint programming approach to tool allocation and production scheduling in flexible manufacturing systems

This paper presents a constraint programming (CP) methodology to deal with the scheduling of flexible manufacturing systems (FMSs). The proposed approach, which consists of both a model and a search strategy, handles several features found in industrial environments, such as limitations on number of tools in the system, lifetime of tools, as well as tool magazine capacity of machines. In addition, it tackles the problem in a integrated way by considering tool planning and allocation, machine assignment, part routing, and task timing decisions altogether in the approach. The formulation, which is able to take into account a variety of objective functions, has been successfully applied to the solution of test problems of various sizes and degrees of difficulty.     

Solving Part-Type Selection and Operation Allocation Problems in an FMS: An Approach Using Constraints-Based Fast Simulated Annealing Algorithm

Production planning of a flexible manufacturing system (FMS) is plagued by two interrelated problems, namely 1) part-type selection and 2) operation allocation on machines. The combination of these problems is termed a machine loading problem, which is treated as a strongly NP-hard problem. In this paper, the machine loading problem has been modeled by taking into account objective functions and several constraints related to the flexibility of machines, availability of machining time, tool slots, etc. Minimization of system unbalance (SU), maximization of system throughput (TH), and the combination of SU and TH are the three objectives of this paper, whereas two main constraints to be satisfied are related to time and tool slots available on machines. Solutions for such problems even for a moderate number of part types and machines are marked by excessive computational complexities and thus entail the application of some random search optimization techniques to resolve the same. In this paper, a new algorithm termed as constraints-based fast simulated annealing (SA) is proposed to address a well-known machine loading problem available in the literature. The proposed algorithm enjoys the merits of simple SA and simple genetic algorithm and is designed to be free from some of their drawbacks. The enticing feature of the algorithm is that it provides more opportunity to escape from the local minimum. The application of the algorithm is tested on standard data sets, and superiority of the same is witnessed. Intensive experimentations were carried out to evaluate the effectiveness of the proposed algorithm, and the efficacy of the same is authenticated by efficiently testing the performance of algorithm over well-known functions     

Operation assignment and capacity allocation problem in automated manufacturing systems

We address an operation assignment and capacity allocation problem that arises in semiconductor industries and flexible manufacturing systems. We assume the automated machines have scarce time and tool magazine capacities and the tools are available in limited quantities. The aim is to select a subset of operations with maximum total weight. We show that the problem is NP-hard in the strong sense, develop two heuristics and a Tabu Search procedure. The results of our computational tests have revealed that our Tabu Search procedure produces near optimal solutions very quickly.     

Performability of systems based on renewal process models

A system of N statistically identical machines is modeled using renewal theory through a unique architecture and state space. The model is very useful in evaluating flexible manufacturing systems (FMS) in particular. Each machine consists of multiple part types that are subject to individual failure. A multiple stage repair process composed of integrable sojourn time distributions requires access to spare parts to repair down machines. A performability measure is used to gauge system effectiveness for this partially degradable system, and an example is given     

Throughput optimization in two-machine flowshops with flexible operations

In this study, a two-machine flowshop producing identical parts is considered. Each of the identical parts is assumed to require a number of manufacturing operations, and the machines are assumed to be flexible enough to perform different operations. Due to economical or technological constraints, some specific operations are preassigned to one of the machines. The remaining operations, called flexible operations, can be performed on either one of the machines, so that the same flexible operation can be performed on different machines for different parts. The problem is to determine the assignment of the flexible operations to the machines for each part, with the objective of maximizing the throughput rate. We consider various cases regarding the number of parts to be produced and the capacity of the buffer between the machines. We present solution methods for each variant of the problem.     

Simulation modelling and analysis of part and tool flow control decisions in a flexible manufacturing system

This paper presents the details of a simulation study carried out for analyzing the impact of scheduling rules that control part launching and tool request selection decisions of a flexible manufacturing system (FMS) operating under tool movement along with part movement policy. Two different scenarios have been investigated with respect to the operation of FMS. In scenario 1, the facilities such as machines, tool transporter and part transporter are assumed to be continuously available without breakdowns, whereas in scenario 2, these facilities are prone to failures. For each of these scenarios, a discrete-event simulation model is developed for the purpose of experimentation. A number of scheduling rules are incorporated in the simulation models for the part launching and tool request selection decisions. The performance measures evaluated are mean flow time, mean tardiness, mean waiting time for tool and percentage of tardy parts. The results obtained through the simulation have been statistically analyzed. The best possible scheduling rule combinations for part launching and tool request selection have been identified for the chosen FMS.     

Algorithms for selecting cutters in multi-part milling problems

This paper describes geometric algorithms for automatically selecting an optimal sequence of cutters for machining a set of 2.5-D parts. In milling operations, cutter size affects the machining time significantly. Meanwhile, if the batch size is small, it is also important to shorten the time spent on loading tools into the tool magazine and establishing z-length compensation values. Therefore, in small-batch manufacturing, if we can select a set of milling tools that will produce good machining time on more than one type of parts, then several unnecessary machine-tool reconfiguration operations can be eliminated. In selecting milling cutters we consider both the tool loading time and the machining time and generate solutions that allow us to minimize the total machining time. In this paper we first present algorithms for finding the area that can be cut by a given cutter. Then we describe a graph search formulation for the tool selection problem. Finally, the optimal sequence of cutters is selected by using Dijkstra's shortest path planning algorithm.     

Simultaneous machine-part grouping approach in manufacturing cells

We present a comprehensive model including all of the operational constraints for solving a cell formation problem in cellular manufacturing systems. It is formulated as a generalized quadratic binary programming model with the objective of minimizing total moves evaluated as a weighted sum of inter- and intracell moves. Two most significant operational constraints included in the model are the sequence of operations associated with each part and the capability of assigning machines of the same type to different cells if two or more machines are considered due to workload requirements. The original model is Transformed into a linear binary programming model, and an example problem is solved using a commercial programming package. The final assignment of parts and machines to cells result in a lower total move than that evaluated from a previous study for the same problem.