Short-Term Capacity Adjustment with Offline Production for a Flexible Manufacturing System under Abnormal Disturbances

Large production variations caused by abnormal disturbances can significantly reduce the production capacity of a flexible manufacturing system (FMS). To prevent production delays, short-term capacity adjustment strategies can be used to augment the capacity of the FMS, such as working overtime, using alternative tools that are suited for faster processing, and producing parts outside of the FMS. We propose a mixed integer programming (MIP) model to obtain an optimal production plan for a multi-machine FMS. Our model evaluates both the FMS loading decision and the effective use of short-term capacity adjustment strategies to minimize the total part production cost. We develop an iterative procedure to solve the model that uses the Lagrangian relaxation method for finding lower bounds and a Lagrangian heuristic for obtaining feasible solutions. The procedure exploits certain special structures found in the Lagrangian multipliers which enable us to obtain good solutions to reasonably large test problems quickly.     

Cyclic scheduling of a 2-machine robotic cell with tooling constraints

In this study, we deal with the robotic cell scheduling problem with two machines and identical parts. In an ideal FMS, CNC machines are capable of performing all the required operations as long as the required tools are stored in their tool magazines. However, this assumption may be unrealistic at times since the tool magazines have limited capacity and in many practical instances the required number of tools exceeds this capacity. In this respect, our study assumes that some operations can only be processed on the first machine while some others can only be processed on the second machine due to tooling constraints. Remaining operations can be processed on either machine. The problem is to find the allocation of the remaining operations to the machines and the optimal robot move cycle that jointly minimize the cycle time. We prove that the optimal solution is either a 1-unit or a 2-unit robot move cycle and we present the regions of optimality. Finally, a sensitivity analysis on the results is conducted.     

Capital budgeting and optimal timing of investments in flexible manufacturing systems

This paper investigates the financial-economic decision process for investments in flexible manufacturing systems (FMS). Contrary to popular belief, we show that conventional capital budgeting techniques can be used to make such investment decisions. First, we identify theoverall impact of installing an FMS and present guidelines for a cash flow forecasting model. We then present ways in which to incorporate uncertainty in these cash flows within a risk-adjusted discount rate. These expected cash flows and the discount rate are used in calculating the net present value (NPV). Once the capital budgeting analysis is completed, a critical issue facing the firm is the optimal timing of the installation. We reinterpret the general results on optimal timing of investments within the special context of an FMS project. Finally, we illustrate the above technique via a stylized example.     

Steady state scheduling of a flexible manufacturing system with periodic releasing and flow time constraints

This paper deals with the dynamic behaviour of an FMS when parts are released periodically. The minimal release period is induced by the most critical machine or fixture pallet type. Moreover, with a fixed period, the limited number of available pallets induces a maximal flow time for every part type. Thus, the objective of this paper is to determine a part release strategy and an activity schedule on every machine which allows to control every part flow time for steady state. An analysis method for this objective is presented in this paper. Its purpose is to obtain releasing and scheduling conditions ensuring a workshop steady state compatible with the considered constraints, especially part flow times. This method is based on the resolution of conflicts between activities processed on a common machine. This resolution uses limit times associated with each activity and it can modify these limit times. These modifications in turn can induce modifications for other activity limit times due to part routing, steady-state periodicity, and part flow time constraints. Thus, an iterative procedure has been defined. It refines steady-state feasibility conditions through limit times and sequencing conditions of activities processed on a common machine. The method is illustrated with two examples.     

Tool planning models for flexible manufacturing systems

Although the tool loading problem for Flexible Manufacturing Systems (FMSs) has been analyzed in the past, the tool planning problem, the basis of tool management, has largely been ignored. In this paper, the interface between tool planning and the FMS loading and routing decisions is analyzed. It is shown that tool policy has a pronounced effect on the flexibility and the planned makespan of an FMS. A tool planning model is developed and integrated into an overall FMS detailed tool loading and part routing procedure. This model while considerably reducing the number of tools required (by 55%) matches the performance of a policy that equips each machine with all tools in terms makespan, routing flexibility, and tool productivity.     

Experimental design and regression analysis in simulation: An FMS case study

The machine mix for a particular FMS, the number of machines performing each of three operations and the number of machines performing any of the three operations (flexible machines), is input to an FMS simulation. An intuitively selected combination of these four inputs are compared to a 2⁴⁻¹ fractional factorial design. The throughput predicted by the simulation is analyzed through two different regression models. These models are validated. A regression model in two inputs including their interaction, gives valid predictions and stable explanations.     

Heuristics for determining economic processing rates in a flexible manufacturing system

In this paper, models are presented for determining economic processing speeds and tool loading to minimize the makespan required to produce a given set of parts in a flexible manufacturing system. Using Taylor's tool life equation, models for determining the optimal processing speeds and the tools to be loaded into finite capacity machine magazines are formulated to minimize the maximum processing time in the system. These problems are evaluated for computational complexity, and several heuristics for obtaining good feasible solutions to the problem are discussed. The quality of the solutions obtained using these heuristics is evaluated by computational experiments against lower bounds established by either relaxations or optimal solutions when possible.     

Auxiliary tool allocation in flexible manufacturing systems

This paper analyses a new approach to the machine loading problem arising in flexible manufacturing systems (FMSs). This approach allows the operations to be assigned to machines assuming that machines have access to all the tools required for their operations. This exploits the flexibility of the FMS completely. Next an allocation of tools to machines is determined which satisfies the tool requirements for each machine and minimizes the total number of tools. Thus this approach minimizes the unnecessary tool duplications in the system and maximizes the tool utilization. The problem is modeled as an integer linear program (ILP). We notice that the main problem has a block diagonal structure which is decomposable by relaxing a set of linking constraints. Each separated sub-problem represents a problem of allocation of a single type of tools. We develop a branch-and-bound based exact solution procedure and three heuristic procedures to solve the sub-problems. Our lower bounding approach uses Lanrangean relaxation. The solutions to the Lagrangean relaxation are further used to determine the branching sequences and to develop heuristic approaches. Since finding even a feasible solution to the main problem is NP-hard, we develop only enumerative procedures to solve the main problem. Finally, these solution procedures are tested on randomly generated test problems.     

Batching and routing: Two functions in the operational planning of flexible manufacturing systems

The success of a Flexible Manufacturing System (FMS) is based on many factors such as the appropriate selection of parts, machine tools and material handling systems, effective planning and a full specification of the control software. In particular, planning must be carried out effectively at many different levels. The production operations of FMS's are planned at one of these levels, and this paper presents a new functional structure for this planning task, called operational planning. Four operational planning functions are identified: batching, routing, dispatching and sequencing. The models that are used to represent the batching and routing problems are presented in detail. The models are formulated as mixed integer programming models, which broadly specify the capacity constraints of the FMS, enabling the decision-maker to look for planning alternatives in a variable time horizon. Results are derived using data from an existing FMS.     

New steps in the amazing world of sequences and schedules

In this paper we consider classical shop problems:n jobs have to be processed onm machines. The processing timep _i,j of jobi on machinej is given for all operations (i, j). Each machine can process at most one job at a time and each job can be processed at most on one machine at a given time. The machine orders are fixed (job-shop) or arbitrary (open-shop). We have to determine a feasible combination of machine and job orders, a so-called sequence, which minimizes the makespan. We introduce a partial order on the set of sequences with the property that there exists at least one optimal sequence in the set of minimal elements of this partial order independent of the given processing times. The set of minimal elements (set of irreducible sequences) can be in detail described in the case of the two machine open-shop problem. The cardinality is calculated. We will show which sequences are generated by the well-known polynomial algorithms for the construction of optimal schedules. Furthermore, we investigate the problemO∥C _max on an operation set with spanning tree structure. Supported by Deutsche Forschungsgemeinschaft, Project ScheMA     

An integrated FMS design procedure

This paper considers the problem of the design of an FMS system. An integrated design procedure is outlined, which involves three stages — planning, design and implementation. Within each stage the design decisions to be made are discussed, together with the techniques and skills required to complete each design stage. At each stage, reference is made to the views of other designers and researchers. Finally, the procedure is illustrated through a case study of a miniature FMS designed and installed at the Cranfield Institute of Technology.     

Scheduling in robotic cells: Complexity and steady state analysis

This paper considers the scheduling of operations in a manufacturing cell that repetitively produces a family of similar parts on several machines served by a robot. The decisions to be made include finding the robot move cycle and the part sequence that jointly minimize the production cycle time, or equivalently maximize the throughput rate. We focus on complexity issues and steady state performance. In a three machine cell producing multiple part-types, we prove that in two out of the six potentially optimal robot move cycles for producing one unit, the recognition version of the part sequencing problem is unary NP-complete. The other four cycles have earlier been shown to define efficiently solvable part 'sequencing problems. The general part sequencing problem not restricted to any robot move cycle in a three machine cell is shown to be unary NP-complete. Finally, we discuss the ways in which a robotic cell converges to a steady state.     

A Hierarchical Model for Control of Flexible Manufacturing Systems

Flexible Manufacturing Systems (FMSs) are usually composed of general purpose machines with automatic tool changing capability and integrated material handling. The complexity of FMSs requires sophisticated control. In this paper we present a four-level control hierarchy and outline computationally feasible control algorithms for each level. The top level is concerned with the choice of part types and volumes to be assigned to the FMS over the next several months. The second level plans daily or shift production. Production levels are set and tools are allocated to machines so as to minimize holding and shortage costs. Various FMS environments are presented. The third level determines process routes for each part type in order to minimize material handling. Additional tools are loaded on machines when possible to maximize alternate routeing. Routes are then assigned to parts to minimize workload assignment, and these are used by level four for actual routeing, sequencing and material handling path control. The level three model is formulated as a linear program, and heuristics are used for level four. An example is provided to illustrate the completeness of the decision hierarchy and the relationships between levels.     

Application of operational research models and techniques in flexible manufacturing systems

In this paper, classification of Flexible Manufacturing Systems (FMSs) and flexibilities is presented. It would be difficult to efficiently implement an FMS without solving its design problems. These problems, as well as a number of operations problems, are discussed. A planning and scheduling framework is developed. Based on this framework, the relevant FMS literature is discussed. Most of the tools and techniques applicable for solving FMS problems are listed. Recommendations for future researh are also presented.     

Sequential Modelling of the Planning and Scheduling Problems of Flexible Manufacturing Systems

Research on the planning and scheduling issues of flexible manufacturing systems (FMS) has not been sparse. Most, if not all, studies, however, have focused on either developing the planning model or examining the performance of different scheduling rules. To date, the FMS planning and scheduling problems have not been studied together, though they are highly interrelated.This paper takes a first step to simultaneously address the planning and scheduling problems of flexible manufacturing systems. The problems are solved as a hierarchical process. We first integrate and formulate batching, loading, and routeing, three of the most important FMS planning problems, as a 0–1 mixed integer program. According to the optimal decisions provided by the integrated planning model, we then develop an off-line scheduling scheme that is capable of generating detail parts sequencing in the sequence independent environment (i.e. the operations are not constrained by a process sequence). Finally, we suggest several extensions and future research directions.     

Quasi-linear production systems: Optimisation of the transportation system

This paper is devoted to the quasi-linear production systems under the following additional hypothesis:

• 1.1. There exists a loading sequence which gives the input order of the parts of the system.
• 2.2. There exists, for each machine, a processing sequence which gives the order for manufacturing the parts.
• 3.3. The transportation system uses carts. A cart is a transportation unit able to carry one part for a machine to another. The parts are loaded on the carts before entering the system and unloaded when the manufacture of the part is finished.

We give an algorithm which leads to the minimal number of carts needed in order to reach the maximal production rate, the loading and processing sequences being known. We also characterize the optimal solution in the case of equal processing times.     

On the solution of concave knapsack problems

We consider a version of the knapsack problem which gives rise to a separable concave minimization problem subject to bounds on the variables and one equality constraint. We characterize strict local miniimizers of concave minimization problems subject to linear constraints, and use this characterization to show that although the problem of determining a global minimizer of the concave knapsack problem is NP-hard, it is possible to determine a local minimizer of this problem with at most O(n logn) operations and 1+[logn] evaluations of the function. If the function is quadratic this algorithm requires at most O(n logn) operations.Work supported in part by the Applied Mathematical Sciences subprogram of the Office of Energy Research of the U.S. Department of Energy under Contract W-31-109-Eng-38.Work supported in part by a Fannie and John Hertz Foundation graduate fellowship.     

Three-stage flow-shop scheduling with assembly operations to minimize the weighted sum of product completion times

A modified flow-shop scheduling problem for a production system, characterized by parts machining followed by their subsequent assembly (joining) operation, is studied. Several products of different kinds are ordered. Each part for the products is processed on machine M₁ (the first stage) and then processed on machine M₂ (the second stage). Each product is processed (e.g., joined) with the parts by one assembly operation on assembly stage M_A (the third stage). The objective function to be minimized is the weighted sum of product completion times. The decision variables are the sequence of products to be assembled and the sequence of parts to be processed. In this paper, we assume that if product h is assembled before product h^′, then, on each machine, processing of any part for product h^′ is done after processing of all parts for product h is completed. We call this assumption “Assumption B(2)” and call this problem “SP_constrained”. An efficient solution procedure using a branch and bound method is developed based on this assumption, where Johnson's algorithm is used as a part of the solution procedure. Computational experiments are provided to evaluate the performance of the solution procedure. It has been found that the proposed solution procedure is effective to obtain an optimal or ε-optimal solution for larger-scaled problems. We further compare the optimal value for SP_constrained with the optimal value for another problem SP_{unconstrained} defined without Assumption B(2); the optimal solution for SP_{unconstrained} being significantly more difficult to obtain. We offer three propositions to analyze some special cases in which the difference between the optimal value of SP_constrained and the optimal value of SP_{unconstrained} is zero. For general cases, we make some computational experiments to evaluate the difference between the optimal value of SP_constrained and the optimal value of SP_{unconstrained}. It has been found that the difference is very small.     

Turnpike properties for a class of piecewise deterministic systems arising in manufacturing flow control

This paper deals with a general class of piecewise deterministic control systems that encompasses FMS flow control models. One uses the Markov renewal decision process formalism to characterize optimal policies via a discrete event dynamic programming approach. A family of control problems with a random stopping time is associated with these optimality conditions. These problems can be reformulated as infinite horizon deterministic control problems. It is then shown how the so-calledturnpike property should hold for these deterministic control problems under classical convexity assumptions. These turnpikes have the same generic properties as the attractors obtained via a problem specific approach in FMS flow control models and production planning and are calledhedging points in this literature.This research has been supported by NSERC-Canada, Grants No. A4952 by FCAR-Québec, Grant No. 88EQ3528, Actions Structurantes, MESS-Québec, Grant No. 6.1/7.4(28), and FNRS-Switzerland.     

A graph theory approach to subcontracting, machine duplication and intercell moves in cellular manufacturing

We address in this paper the problem of finding an optimal strategy for dealing with bottleneck machines and bottleneck parts in the cell formation process in group technology. Three types of economic decisions are considered: subcontracting, machine duplication and intercell moves. The problem is formulated as a minimum weighted node covering problem in a hypergraph, and we show that it can be solved in polynomial time by finding a maximum weighted stable set in a bipartite graph. We extend this result to cellular manufacturing systems in which the sequence of operations of each part is known in advance.