Integration of mathematical and simulation models for operational planning of FMS.

Maheshwari, Sharad K.

INTRODUCTION

Flexible Manufacturing Systems (FMSs) are automated small-batch manufacturing systems consisting of a number of numerical and computerized numerical controlled metal cutting machinetools linked together via an automated material handling system (MHS), Real-time control of machines and MHS is accomplished by computers and data transmitting links. The main objective of these integrated systems is to achieve the efficiency of automated high-volume mass production while retaining the flexibility of low-volume job-shop production. The flexibility in FMS is introduced via several factors which may include versatile machine tools, small set-up and tool changing time, relatively large tool carrying capacity and the ability to automatically transfer tools between the machines. These factors allow a part to take alternate route while under process in the system. The possibility of the alternate routings adds an important element to the overall flexibility of these manufacturing systems.

An FMS possesses enormous potential for increasing overall productivity of manufacturing systems due to its flexibility. However, the task of operational level planning of FMS is more complex compared to traditional systems. During the operational planning of an FMS, small batches of parts are selected for simultaneous production in a manufacturing cycle. Several planning decisions such as, part production ratio, tool loading, machine grouping, and resource allocation (Stecke, 1983) are considered at the operational stage.

Numerous research studies are available in literature related to these operational planning problems (for review see: Buzacott & Yao, 1986; O'Grady & Menon, 1986). In general, the research studies in FMS production planning utilize the mathematical modeling approach to solve the problem. However, these mathematical models do not capture dynamic aspects (scheduling and other time-based factors) of the system. To address the dynamic aspects, discrete event simulation is widely employed (for review see: Gupta, Gupta & Bector, 1989). In typical FMS environment, the operational plamiing and scheduling problems are addressed at two different levels.

Since at the operational planning level, scheduling aspects are not considered, the results from the mathematical planning models are generally not realistic for FMS (Leung, Maheshwari & Miller, 1993). For example, the machine workload at the planning model results may be highly balanced, but due to scheduling constraints it may not be achievable during the actual operation of the FMS. This variance in the outcome of two models may result in the poor utilization of resources, longer makespan, etc.

In this paper, the part assignment and tool allocation problem in FMS is considered. The solution procedure utilized to solve the problems combines mathematical model with a discrete event si-tnulafion model. This procedure provides both optimal and realistic solution to mathematical model by integrating it with a simulation model. The remainder of the paper is organized as follows. The next section, briefly, reviews the literature on operational planning in FMS. Section 3 provides an overview of the problem and solution procedure. Section 4 provides proof of convergence of the procedure. This is followed by presentation of the example problems and the results obtained from these problems. Section 7 provides guidelines for parameter modificafion based on the example problems.

LITERATURE REVIEW

The operational planning problem in FMS has been extensively examined in the research literature. Mostly, operational planning problem is formulated as a mathematical model. The scheduling and control issues are not considered at this stage. Stecke (1983) formulated the machine loading problem as a non-linear programming model. Several different loading objectives were considered. These objectives included balancing the assigned machine processing times, maximizing the number of consecutive operations of a part on each machine, maximizing the sum of operation priorities, and maximizing the tool density of each magazine. Shanker and Tzen (1985) modified Stecke's (1983) model to include due dates. The modified objective function tries to balance the workload on each machine and to reduce the nwnber of late jobs simultaneously. Kusiak (1985) formulated FMS loading problem as a 0-1 linear integer model with the objective of minimizing total processing cost. However, he considered identical processing time for operations. Sarin and Chen (1987) formulated the machine loading and tool allocation as a 0-1 linear program. Part assignments and tool allocations were determined concurrently incorporating considerations such as tool life, tool slot capacity, and machine capacity. Leung, et al. (1993) formulated part assignment and tool allocation problem with material handling considerations.

Avonts and Van Wassenhove (1988) combined mathematical planning model with queuing network model to solve part mix and routing mix problems. They proposed a solution procedure where a linear programming model results were evaluated using CAN-Q. The results from the queuing model were fed into to the linear programming model. It was shown that combining a static linear programming model with a dynamic queuing model helped in achieving more realistic results for the part mix and routing mix problems.

The scheduling and control has been studied extensively in FMS. Gupta, et al. (1989) reviewed some aspects of FMS scheduling literature. Generally simulation is employed as the evaluation tool at this stage. A selective review of some of these studies is provided here.

Nof, Barash, and Solberg (1979) have studied the control problem in FMS. They have considered three rules for part releasing into the empty system and two rules for part releasing into the loaded system. The releasing sequence is either random or a function of the production requirement of part types. Their research shows that these rules have significant influence on system utilization and production rate. Stecke and Solberg (1981) carried out a simulation study of an FMS to show the impact of the several machine sequencing rules on the performance of the FMS under different loading objectives. They concluded that scheduling rules have significant influence on performance of the FMS. Similar conclusions have been made in a recent study by Montazeri and Van Wassenhove (1990). Carrie and Petsopoulos (1985) conducted simulation experiments to examine the part releasing rules, and part sequencing rules. However, their investigation of an existing FMS shows that neither the part releasing nor the part sequencing rules have significant impact on performance of that FMS.

Egbelu and Tanchoco (1984) explored the system from a different perspective. They tested the effect of vehicle dispatch and vehicle selection rules on the system performance. Their results show that vehicle dispatching rules have significant influence on the system performance. Due to high utilization of the material handling system, the vehicle selection rules did not show significant impact.

Most research studies at the operational level of FMS focus independently either on planning or scheduling problem. Some researchers (Stecke & Solberg, 1981; Shanker & Tzen, 1987; Maheshwari & Khator, 1993; etc.) have considered both problems simultaneously. These studies show that the performance of the system at the operational level is greatly influenced by dynamic factors such as part and vehicle scheduling rides. Avonts and Van Wassenhove (1988) have shown that the results from operational planning model for FMS can be more realistic if dynamic system factors are given some considerations. Hence at the operational stage, planning and scheduling model should be considered together, not separately.

PROBLEM STATEMENT AND SOLUTION STRATEGY

Two operational planning decisions, part assignment and tool allocation, are considered in this research. Part assignment is defined as the assignment of operations of part types to machines. Tool allocation refers to the loading of tools onto machine magazines. We utilized the mathematical model developed earlier by Leung et al. (1993).

The main objective of this research is to present an integrated solution procedure for part assignment and tool allocation problem in FMS. The integrated procedure combines the mathematical planning model with a simulation model in a hierarchical fashion.

The mathematical model determines part assignment and tool allocation based upon static system constraints such as resource capacity, tool life, operation times, etc. The consideration of detailed real-time factors (such as scheduling rules) makes mathematical model rather difficult to solve, if not impossible, However during actual operation of the system, there are several dynamic factors (part scheduling rules, vehicle scheduling rules, etc.) which influences the system performance. The overall system performance is a function of both mathematical planning model results as well as scheduling and control rules (Stecke & Solberg, 1979; Maheshwari & Khator, 1993). For example, a part may experience delays in actual operation of an FMS due to blocking of machines, blocking of the pathways of transporters, starving of machines, etc. However, these effects cannot be directly accounted at the mathematical model level. Consequently, the mathematical model results may become unattainable during actual operation, especially in terms of resources capacities, workload balancing, and makespan.

The procedure described here aims at achieving more realistic results from the mathematical model. The results from mathematical model are evaluated at simulation model. The necessary mathematical model parameters, such as machine utilization factors, vehicle utilization factor, length of the manufacturing cycle, are modified after the evaluation of mathematical model results. Another set of mathematical model results is obtained using these modified set of parameters. The procedure continues till a viable set of mathematical model results is obtained.

Part Assignment and Tool Allocation

The part assignment and tool allocation model is an integer linear programming model. The model is included in the Appendix. Readers are referred to Leung, et al.(1993) for the detailed mathematical formulation. For brevity, we describe the characteristics of the model in principle.

Decision Variables

There are two set of decision variables. The first set of decision variables represents the quantity of each part type whose specific operation is to be processed on a machine using a particular tool type after visiting a given machine for a preceding operation. Second set of decision variables depicts the number of tools of a given type allocated to a machine.

Constraints

The constraint sets include tool life constraint tool availability constraint, magazine size constraint, machine capacity constraint material handling capacity constraint, etc. These constraints are briefly addressed below.

* Machines Features. The operational characteristics of the machines such as operation capacity and tool compatibility are included in this constraint set (3). Tool magazine size is also considered (2).

* Operational Requirements. These constraints ensure, that all operations are processed and all output requirements are satisfied (5, 6). This constraint set also ensures that tool-life requirements are met at each machine (3).

* Resource Constraints. The assigned time for any resource is formulated to be less than the available time. The resources considered in this formulation are machines, and material handling system (7, 8). Cutting tools availability is also formulated as a constraint set (4).

Objective Function

The objective function incorporates the operation and travel times of parts (1). The travel times are a function of the distance between the machines and the velocity of material handling device. The travel times are multiplied by a factor to represent the empty travel time associated with the material handling device.

Scheduling Rules

A discrete event simulation model is used to incorporate the system details so that mathematical model results can be evaluated. Part releasing, part sequencing and vehicle dispatching rules are considered in this model. Two system parameters, number of buffer spaces and number of pallets, are also taken into consideration. Maheshwari and Khator (1993) have evaluated several different scheduling rules for a similar FMS. Only the rules which were found significant are used in this research.

Part Releasing Rule

This rule assigns priority to the parts awaiting release into the system. There is a finite number of parts circulating concurrently into the system. A part remains on a pallet while in the system. A pallet becomes available when a circulating part finishes all of its operations. A new part can be released into the system on an available pallet according to a priority rule. A releasing rule may depend upon the part characteristics such as processing time requirements, arrival time and number of operations, or upon the global system characteristics such as the up or down state of the machine a part needs to visit and instantaneous production ratio (Carrie & Petsopoulos, 1985). The following rule was utilized in this research.

Least Production Ratio (LPR). The production ratio is calculated as
the number of parts released into the system divided by the
production requirement for the given part type. This rule tries to
maintain the desired production ratio throughout the manufacturing
cycle.

Part Sequencing Rules

The part sequencing rules deal with sequencing of parts waiting at a machine for processing. An operation processing priority is assigned to a part waiting to be processed at a machine. These priority rules are applicable only if more than one part is waiting at that machine. Several part sequencing rules have been examined in an FMS environment by Stecke and Solberg (1982) and Montazeri and Van Wassenhove (1990). The rules used here are:

Shortest Processing Time (SPT). SPT selects the part for processing for which operation can be completed in the least time. SPT is found to be generally efficient in the FMS environment (Stecke & Solberg, 1981).

Smallest ratio of imminent Processing Time/Total Processing Time (SPT/TPT). This sequencing rule arranges the parts for processing with a ratio of the processing time for the current operation to the total processing time. SPT/TPT has been reported to be a very efficient rule in terms of throughput rate (Stecke & Solberg, 1982; Montazeri &Van Wassenbove, 1990).

Vehicle Dispatching Rules

The vehicle dispatching rules are required when a part is to be transported from one machine to another machine or to the load/unload station. Priority is assigned for selecting the part if more than one part is waiting to be transported when a vehicle becomes idle. These priority schemes are called vehicle initiated rules (Egbelu & Tanchoco, 1984). Two different vehicle initiated rules-minimum work in input queue and minimum remaining outgoing queue space--are considered here. In the situations when a part has to select a vehicle, work-center initiated rule, from several idle vehicles, the shortest distance rule is always utilized.

Minimum Work in Input Queue (MWIQ). MWIQ determines transportation priority according to the work content in the destination queue of the part. Work content of a queue is defined as the sum of processing times of all the parts in that queue.

Minimum Remaining outgoing Queue Space (MRQS). MRQS assigns transportation priority to the parts according to the state of the buffer in the outgoing queue. A common inputoutput buffer is considered in this research. This rule attempts to reduce the transportation delay for incoming parts which may occur due to the non-availability of the buffer space at the machine.

System Parameters

The size of buffers and the number of pallets have direct impact on performance of the system (Schriber & Stecke, 1988). It is assumed that the same buffer area is used for both input and output of the parts at a machine. Two different buffer capacities, 5 and 6, are considered in this research. It is assumed that each machine has equal number of buffer spaces. Two different capacities of pallets, 10 and 12, are considered. These are 2.5 and 3 times of the number of machines, respectively. Iterative Procedure: Integration of Mathematical and Simulation Models

The iterative procedure was first proposed by Leung, et al. (1993). This procedure links mathematical model to a simulation model to solve the part assignment and tool allocation problem in FMS. The steps of the procedure are as follow.

Step 1. Initialize parameters for mathematical model (machine utilization, vehicle utilization, number of vehicles, length of manufacturing cycle, etc.).

Step 2. Solve the mathematical model for part assignment and tool allocation. Obtain machine utilization and vehicle utilization.

Step 3. Input mathematical model results into the simulation model.

Step 4. Collect statistics on system utilization, makespan and vehicle utilization.

Step 5. Compare mathematical results with simulation results.

Step 6. Stop if, simulation outcomes comply with the results from the mathematical model; otherwise go to Step 7.

Step 7. Modify parameters of the mathematical model based on simulation results and go to Step 2.

CONVERGENCE OF THE ITERATIVE PROCEDURE

The utility of the above iterative procedure would be very limited in practice, if it fails to converge. A mathematical proof, that the procedure would converge to an overall optimum value, is rather difficult and will be function of a large number of operational level variables. However, it can be easily shown that if an optimal solutions exist, the iterative procedure will converge, provided some conditions are satisfied.

Lemma 1

There exists a lower bound and an upper bound to the solution of the iterative procedure, if some of the system parameters are predetermined, and if arbitrary slack time is not added to the length of manufacturing cycle.

Proof of Lemma 1

Let's assume that the part-mix ratio and production quantity to be produced are known, however, length of the planning cycle is variable. There are alternative machine and cutting-tools combinations for each operation of the given parts. Then, a lower bound on the makespan can be obtained by assigning parts using machine workload balancing objective.

An upper bound can be determined by simulating the mathematical model results obtained by maximizing the sum of processing and traveling time. The parts will be assigned to the least efficient machining center within the given constraints. All the dynamic delays (scheduling delays) can be accounted by the simulation model, The optimum solution to the procedure will lie between this lower and upper bound, if it exists. If arbitrary delays are introduced between the operations then there can be infmite solutions to the problem. The set of feasible schedules can be limited to a finite set only if no-delay schedules are considered.

Lemma 2

The iterative procedure will attain an optimum solution, if the optimum solution to the iterative procedure exists, and if some of the system parameters are predetermined.

Proof of Lemma 2

The procedure is non-monotonic in nature. However, according to lemma 1, if the production quantities are fixed, a lower ([L.sub.b]) and upper ([U.sub.b]) bound to the solution can be determined.

If an optimum solution exists, it will lie between [L.sub.b] and [U.sub.b]. Let's assume that value of the planning parameters (resource utilization factors and length of planning cycle) are modified randomly. Furthermore, the solution follows an arbitrary probability density function f(s). Mathematically, it can be defined as:

Probability Density = f(s),
 Function

where s = A solution to the mathematical model, and
 s [L.sub.b],
 s [U.sub.b],
 [L.sub.b] = Lower bound on s, and
 [L.sub.b] 0.
 [U.sub.b] = Upper bound on s, and
 [U.sub.b] [L.sub.b].

Let [I.sub.s], be a small interval between [L.sub.b] and [U.sub.b] such that it contains the optimum solution to the iterative procedure. In other words, probability that a solution lies somewhere on [I.sub.s], is greater than zero (P([I.sub.s]) > 0). If a large number of random samples are drawn (random modification of the parameters at the end of each iteration will provide a random sample on solution space) then there is a finite probability that the solution to one of the sample will lie on the interval [I.sub.s]. The length of the interval [I.sub.s] can be made small to reach closer to the solution. In fact length [I.sub.s] could be fixed on the basis of an acceptable variation between mathematical and simulation models results. Therefore, in general the process will converge to an optimum solution of the iterative procedure.

The above lemma, does not determine the speed convergence of the procedure. However, during the implementation process both upper and lower bounds can be updated at every iteration. Therefore, the spread of the solution range can be reduced at each step. The reduction of the solution space would assist in improving the rate. A mathematical bound on the rate of convergence cannot be obtained due to non-monotonicity of the procedure. Nevertheless, the practical utility of the procedure can be tested, especially if large number of problems are solved using this procedure. In this paper, two numerical problems were utilized to show the implementation of the procedure.

EXAMPLE PROBLEMS

A flexible manufacturing system may consists a large number of machining centers, however a typical number of machining centers in an FMS is usually between 3 and 6. An FMS with four machining centers is considered in this research. Each machining center has a fixed size tool (40 tools) magazine. It is assumed that tools are allocated at the beginning a manufacturing cycle only. No automated tool transfer is available during the manufacturing cycle.

Tables 1 and 2 show the range of parts to be manufactured in two independent test problems, henceforth referred as Problem I and Problem 2. In this research, only part assignment and tool allocation problem is considered. Therefore, it is assumed that part selection problem has been already been solved. Consequently, for each manufacturing cycle number and type of parts are known. But the part assignment and tool allocation are yet to be determined.

Tables 1 and 2 also indicate operation times, in minutes, to perform each operation of every part type. Operations can be performed at an alternate machining center as well. Table 3 shows the number of parts to be processed, demand of each part type, in the given manufacturing cycle. The length of manufacturing cycle is assumed to be 2400 minutes.

The procedure requires to solve two different models--mathematical and simulation--at each iteration of the procedure. ne mathematical model is linear-integer model. It was solved using MPSX/370 version 2.0. The second model, used in the procedure, is a discrete event simulation model. This model was built using SIMAN IV simulation language and Microsoft C.

RESULTS

Mathematical Model Results

The mathematical model was solved with the utilization factors (machines utilization and MHS utilizations as 100% in the first iteration of the procedure for both Problems I and 2. This was necessary due to the lack of historical data. A common utilization factor was employed for all four machines in the system. Part assignments and tool allocations were obtained. In subsequent iterations, these parameters were modified according to the simulation results. Each time a parameter was modified, new mathematical model results were obtained. Tables 4 and 5 show the parameters and aggregate results for all iterations for Problem 1 and Problem 2, respectively. The parameter modification was based on makespan, mean waiting times, and vehicle utilization.

Simulation Model Results

The mathematical model results were used as the input to simulation model. At this stage, five different operational factors were considered. Only one part releasing rule was used. Whereas, two part sequencing rules, two vehicle dispatching rules, and two levels of buffer size and pallets were utilized to test the results at the simulation model. In all for each run there were 16 combinations (2 x 2 x 2 x 2) for a full factorial experiment. A fractional factorial design (1/2 x 2 x 2 x 2 x 2) was used to reduce the number of simulation runs. The results from the simulation model are displayed in Tables 6 and 7 for Problems 1 and 2, respectively.

Results of Iterative Procedure

Problem 1 required three iterations to reach to a solution, whereas, Problem 2 required four iterations. Here, the results at the each iterations for both problems are discussed. A subsequent iteration became necessary for a problem because the results from the mathematical model were not feasible at the simulation level. Thus, some mathematical model parameters were modified at each iteration to get new results.

Iteration 1: Initial iteration started with 100% utilization factor in both the problems. Mathematical model makespan was 2400 and 2360 minutes respectively. However, when the results of the Problems 1 and 2 were simulated, minimum makespan was 2826 and 2869 minutes, respectively. This was about 17% longer than planned period of 2400 minutes. Vehicle utilization was 97% and 78%. Higher vehicle utilization indicates that there was higher empty travel time (e.g., vehicle utilization was 95% and makespan was 2826 minutes. Then, total time vehicles were used would be 0.95*2826 = 2685 minutes. Whereas, the planned loaded travel time was 1038 minutes only). The available loaded travel time on the vehicle should be reduced. On the basis of these results, two planning parameters--vehicle and machine utilization were updated for the next iteration for both the problems.

Iteration 2: New sets of mathematical model results were obtained using 90% machine capacity and 50% vehicle capacity. The mathematical model results were still infeasible at the simulation level. Vehicle utilization was 97% in the case of the Problem 1 and 78% in the case of the Problem 2. However, the results were closer to the mathematical model results compared to the results at iteration 1. This shows that solution is moving in the right direction.

The higher utilization of the vehicle resulted in relatively longer mean waiting time as well. In other words the reduction in the waiting time was very small from iteration 1 to iteration 2. Therefore for the next iteration, number of vehicles was increased to 2 and available vehicle time was further reduced to 35%.

Iteration 3: This iteration didn't require any solution of mathematical model. At that stage only material handling capacity was increased on the basis of simulation model results. However, the material handling capacity was not a binding constraint at the mathematical model stage at iteration 2. Therefore, increase in the MHS capacity would not change the mathematical model results from iteration 2 to iteration 3. A new set of simulation runs were made with increased capacity of MHS. The results show that the mathematical model results became feasible at simulation model for Problem 1. The makespan achieved at the simulation stage was 2395 as compared to 2400 at mathematical model. The iterative process terminates here for the Problem 1.

However, results were still not viable for the Problem 2. There was approximately 10% difference in the length of manufacturing cycle. But vehicle utilization was low--about 43%. Hence, any further increase in the vehicle capacity would not reduce the length of manufacturing cycle. Consequently, machine utilization was reduced to 80% for mathematical model for Problem 2.

Iteration 4: A new set of the mathematical model results was obtained for the Problem 2. The simulation and mathematical models results were within [+ or -]1.2% of the each other. The iterative process was terminated.

The results show that the solutions from the mathematical model without considerations to the utilization factors are not viable at the simulation level. Therefore, resource capacities at the mathematical model must be adjusted by utilization factors so that its results are feasible at both the levels.

Despite the lower material handling requirement in the example problems 1 and 2, the vehicle utilization was relatively very high. This was due to the fact that large amount of the empty travel is involved in the system layout under consideration. This layout allows only unidirectional travel of vehicles. Consequently, every loaded travel is accompanied by a significant amount of unloaded travel. This reduces the available time for loaded travel on a vehicle to less than 50% of the total time.

GUIDELINES FOR PARAMETER MODIFICATION

A link between mathematical and simulation models is established using modification of the planning parameters. The rate of convergence of the procedure is dependent on the modification of parameters. Therefore, it is important to have certain guidelines to adjust the parameters at every iteration.

Selection of Initial Parameters

Initial starting point is very critical to the iterative procedure. If good start point is selected, a faster convergence of the procedure can be expected. The initial parameters can be selected on the basis of the historical data on the system and the parameters of the problem under consideration. Further investigation is necessary to establish guidelines for initial parameter selection. If no reliable historical data is available, then procedure could be initiated with 100% utilization of all the resources.

Modification of Parameters

* Increase in MHS capacity (more number of vehicles) can be effective if vehicle utilization is large at the simulation model.

* Machine utilization factors should be considered for adjustment if simulation model cycle length and planning period differ by more dm a predetermined fraction, e.g., 0.05.

* Machine utilization should be reduced, if part waiting time is large. This adjustment requires some judgement because part waiting is also dependent on the number of pallets. If number of pallets increases, overall waiting time also increases. Therefore, if longer waiting time is contributed due to the number of pallets, than adjustment of utilization factors may not be desirable.

* While adjusting machine utilization parameters, the available machine capacity should be maintained at a level so that all the parts can be assigned. In both the problems, overall machine workload is approximately 70% of the total available time on the machines. That is, 30% of the time machines is idle to adjust scheduling delays. Most of the unassigned machine time was on the alternate machines (less efficient machines).

* The length of the planning period can be adjusted if the utilization factors and vehicle capacity do not achieve a viable solution in a given number of iterations.

CONCLUSIONS

In this paper we provide a procedure for operational planning of FMS which combines a mathematical planning model with a simulation model. The procedure is developed to solve part assignment and tool allocation problem in FMS. The procedure has three main components--an integer programming model, simulation model and parameter modification. Main objective of the procedure is to obtain the planning model results which are viable at the operational level.

It was demonstrated that the procedure would converge to a solution of a problem. However, no limits on the rate of convergence was established. The implementation of the procedure was illustrate with help of two examples. The results of these problems showed that the procedure could converge faster, hence, could be useful in real world situations. The examples illustrated that resource utilization factors had considerable impact on the viability of mathematical model results. Thus, effective linking of mathematical and simulation model is necessary to obtain viable results. The values of the utilization factors depend upon several operational elements. Estimates of the utilization factors can be obtained from historical results. The planning procedure can be used for further adjustment of the value of the utilization factors and other planning parameters.

Further examination on the optimality and the rate of convergence of procedure is needed. The procedure does not consider whole feasible region, instead it utilizes a point search. Every iteration represents a point in this search procedure. Therefore, some overall optimality testing criteria should be developed or else the procedure may terminate at a local optimal solution. Similarly, limits on the rate of convergence must be established, The practical utility of the procedure will be very limited if convergence of the procedure is slow. Nevertheless, two problems showed that a relatively faster convergence is plausible. The procedure in above two cases converges in 3 and 4 iterations respectively.

Appendix

The time minimization model can be written as follows (Leung et al., 1993): Minimize:

(1) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

(2) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

(3) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

(4) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

(5) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

(6) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

(7) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

(8) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where:

[X.sub.ijkrs] Quantity of part type i whose jth operation is to be processed on machine k using tool type s, after visiting machine r (for its j-1st operation)

[Y.sub.sk] Number of tools of type s loaded on machine k

[t.sub.ijks] Processing time of the jth operation of the ith part type on the kth machine using the sth tool type

[p.sub.s] Tool life of the sth tool type

[d.sub.kr] Travel distance between machine k and machine r

[beta] Fraction of unloaded travel

[S.sub.k] Magazine capacity of machine k

{[[PHI].sub.ks]} Set of machines k which can hold tool type s

[A.sub.s] Available tools of type s

Ns Number of slots required by a tool of type s

[Q.sub.i] Production requirement of part type i for a given planning period

{[[delta].sub.ikj]} Set of operations of part type i, which can be performed on machine k

[M.sub.k] Available time on machine k

[[alpha].sub.k] Maximum utilization of machine k

[mu] Capacity of material handling system

[xi] Maximum utilization of material handling system

[delta] A very small number

REFERENCES

Avonts, L. & Van Wassenhove, L. N. (1988). The part mix and routing mix problem in FMS: A coupling between an lp model and a closed queuing network, International Journal of Production Research, 26, 1891-1902.

Buzacott, J. A. & Yao, D.D. (1986). Flexible manufacturing systems: A review of analytical models, Management Science, 32, 890-904.

Carrie, A.S. & Petsopoulos, A.C. (1985). Operation sequencing in a FMS, Robotica, 3, 259-264.

Egbelu, P. J. & Tanchoco, J. M. A. (1984). Characterization of the automatic guided vehicle dispatching rules, International Journal of Production Research, 22, 359-374.

Gupta, Y. P., Gupta, M.C. & Bector, C.R. (1989). A review of scheduling rules in flexible manufacturing systems, International Journal of Computer Integrated Manufacturing, 2, 356-377.

Kusiak, A. (1985). Loading models in flexible manufacturing systems, In Flexible Manufacturing Systems and Allied Areas, Amsterdam: North-Holland Publishing Company.

Leung, L.C., Maheshwari S. K. & Miller, W. A. (1993). Concurrent part assignment and tool allocation in FMS with material handling considerations, International Journal of Production Research, 31, 117-138.

Leung, L.C. & Tanchoco, J. M. A. (1987). Multiple machine replacement within an integrated framework, The Engineering Economist, 32, 89-114.

Maheshwari, S. K. & Khator, S. K. (1993). Simultaneous evaluation and selection of strategies for loading and controlling of machines and material handling system in FMS, Working Paper, Dept. of Management, Hampton University, Virginia.

Montazeri, M. & Van Wassenhove, L. N. (1990). Analysis of scheduling rules for an FMS, International Journal of Production Research, 28, 785-802.

Nof, S. Y., Barash, M. & Solberg, J. J. (1979). Operational control of item flow in versatile manufacturing systems, International Journal of Production Research, 17, 479-489.

O'Grady, P. J.& Menon, U. (1986). A concise review of flexible manufacturing systems and FMS literature, Computers in Industry, 7, 155-167.

Sarin, S.C. & Chen, C. S. (1987). The machining loading and tool allocation problem in a flexible manufacturing system, International Journal Production Research, 25, 1081-1094.

Schriber, T. J. & Stecke, K.E. (1988). Machine utilizations achieved using balanced FMS production ratios in a simulation setting, Annals of Operations Research, 15, 229-267.

Shanker, K., & Tzen, Y. J. (1985). A loading and dispatching problem in a random flexible manufacturing system, International Journal of Production Research, 32, 579-595.

Stecke, K.E. (1983). Formulation and solution of nonlinear integer production planning for flexible manufacturing systems, Management Science, 29, 273-288.

Stecke, K.E. & Solberg, J.J. (1981). Loading and control policies for a flexible manufacturing systems, International Journal of Production Research, 19, 481-490.

Sharad K. Maheshwari, Hampton University

Table 1: Part Types and Operation Times (Min) for Problem 1

Part Operation Machine

 1 2 3 4

1 1 3 * * 4
 2 8 * * 10
 3 14 * 8 19
 4 * 9 12 *
2 1 * 18 24 *
 2 * * 13 17
 3 * 7 10 *
 4 * * 3 4
 5 * 13 16 *
 6 5 * * 6
3 1 * 1* 16 *
 2 6 * * 7
 3 * 11 16 *
 4 * 12 16 *
4 1 * 7 9 *
 2 10 * * 14
 3 * 17 23 *
 4 * 14 22 *

Table 2

Part Types and Operation Times (Min) for Pro

Part Operation Machine

 1 2 3 4

 5 1 6 * * 9
 2 14 19 * *
 3 11 * * 16
 4 7 * * 11
 5 11 * * 18
 6 1 6 * * 8
 2 * 11 14 *
 3 * 15 23 *
 4 8 * * 12
 5 * 4 7 *
 7 1 * 3 4 *
 2 3 5 * *
 3 * * 15 20
 4 * 5 7 *
 5 15 * * 22
 8 1 18 * * 27
 2 * 4 7 *
 3 * 4 6 *
 4 * 6 8 *
 5 * 8 13 *
 6 12 * * 19
 9 1 * * 6 8
 2 * 13 18 *
 3 8 * * 11
 4 7 * * 12
 5 * 12 17 *
 6 * 16 24 *

Table 3: Demand Type for Each Part type in Problems 1 and 2

 Problem 1

Part Type 1 2 3 4
Requirement 20 40 32 20

 Problem 2

Part Type 5 6 7 8 9
Requirement 24 18 12 24 30

Table 4: Iterative Procedure: Mathematical Model Results for Problem 1

Iteration Available Available Number Length
Number Machine Vehicle of Planning
 Capacity Capacity Vehicles Cycle

1 100% 80% 1 2400

2 90% 50% 1 2400

3 90% 35% 2 2400

Iteration MHS Total Maximum
Number Load Machine Machine
 Workload Workload

1 1038 6225 2360

2 1154 6693 2160

3 1154 6693 2160

Table 5

Iterative Procedure: Mathematical Model Results for Pro

Iteration Available Available Number Length
Number Machine Vehicle of Planning
 Capacity Capacity Vehicles Cycle

1 100% 80% 1 2400

2 90% 50% 1 2400

3 90% 35% 2 2400

4 80% 35% 2 2400

Iteration MHS Total Maximum
Number Load Machine Machine
 Workload Workload

1 1107 6182 2400

2 1194 6563 2160

3 1194 6563 2160

4 1244 6780 1920

Table 6

Iterative Procedure: Simulation Model Results for Problem 1

Scheduling Rules/System Parameters Iteration 1

PRR VDR PSZ PAL BUF MS VU WT

1 2 2 10 5 2847 0.95 109

1 2 3 10 5 2826 0.94 147

1 2 2 12 6 2841 0.94 191

1 2 3 12 6 2767 0.99 223

1 3 2 12 5 2930 0.92 221

1 3 3 12 5 2758 0.98 165

1 3 2 10 6 2753 0.99 121

1 3 3 10 6 2898 0.93 135

Iteration 2 Iteration 3

MS VU WT MS VU WT

2809 0.94 93 2443 0.60 67

2650 0.97 127 2482 0.59 104

2725 0.96 162 2501 0.59 141

2666 0.99 190 2395 0.66 146

2601 0.99 194 2474 0.59 159

2696 0.94 157 2494 0.66 139

2504 0.98 108 2405 0.62 91

2733 0.96 121 2484 0.58 99

Iteration 4 is not needed

PRR: Part Releasing Rules

PSQ: Part Sequencing Rules

MS: Makespan in Minutes.

1--LPR; VDR: Vehicle Dispatching Rules;

2--SPT; 3--SPT/TPT.

VU: Mean Vehicle Utilization.

PAL: Number of Pallets.

WT: Mean Waiting and Traveling Time for a Part.

2--MRQS, 3--MWIQ.

BUF: Buffer Spaces

Table 7

Iterative Procedure: Simulation Model Results for Problem 2

Scheduling Rules/System Iteration 1
Parameters

PRR VDR PSZ PAL BUF MS VU WT

1 2 3 10 5 3140 0.74 89

1 2 2 10 5 2883 0.85 102

1 2 3 12 6 3144 0.77 181

1 2 2 12 6 3156 0.76 151

1 3 3 12 5 3203 0.75 178

1 3 2 12 5 2869 0.84 145

1 3 3 10 6 3240 0.73 98

1 3 2 10 6 2972 0.78 100

Iteration 2 Iteration 3 Iteration 4

MS VU WT MS VU WT MS VU WT

2983 0.72 82 2785 0.41 73 2585 0.49 61

2842 0.78 91 2688 0.43 82 2438 0.52 67

3054 0.70 176 2917 0.39 169 2683 0.47 151

3094 0.72 145 2934 0.39 133 2697 0.46 104

3004 0.73 156 2894 0.40 131 2702 0.46 122

2800 0.78 140 2679 0.43 123 2429 0.53 106

3140 0.68 89 2974 0.38 80 2752 0.45 71

2898 0.80 93 2801 0.39 90 2578 0.48 88

PRR: Part Releasing Rules

PSQ: Part Sequencing Rules

MS: Makespan in Minutes

1--LPR; VDR: Vehicle Dispatching Rules

2--SPT; 3--SPT/TPT

VU: Mean Vehicle Utilization

PAL: Number of Pallets

WT: Mean Waiting and Traveling Time for a Part.

2--MRQS, 3--MWIQ.

BUF: Buffer Spaces