N-Step Ahead Minimum Inventory Variability Scheduling Policy

1. INTRODUCTION

1.0 Resource Scheduling Optimization

Industry’s never-ending quest for increased profits has lead them to conduct more research in the area of optimizing manufacturing practices. One such area, resource scheduling, has recently received its fair share of attention [1, 2, 13, 19, 20, 21, 22, 23, 24, 28, 29, 30].

It is the purpose of this paper to address one such alternative to optimizing scheduling, the Minimum Inventory Variability Policy^® (MIVP^®) algorithm [4, 5, 9, 10, 11, 12, 14, 15, 16, 17, 18, 31, 32]. This research is the continuation of the work initiated by R. Wiedmeyer [11] investigating the 1-Step Ahead MIVP^® using Extend^®. The MIVP^® algorithm has three levels of complexity and this research presently focuses on the second level using the K-Step Ahead MIVP^® scheduling policy. This policy was compared with First-In-First-Out (FIFO) scheduling rules and to 1-Step AheadMIVP^® using a discrete event simulation modeling software AutoMod^®/AutoSched^®. The 1-Step AheadMIVP^® and K-Step Ahead MIVP^® scheduling rules were written in Automod^® language and incorporated into the simulation software with the aid of support staff from AutoSimulations, Inc. (ASI). The FIFO scheduling rules from AutoMod^®/AutoSched^® were also used in the comparisons. The SEMATECH Dataset #1 of a two-product semiconductor manufacturing production factory (FAB) with known production inputs and outputs was used as the factory Dataset to do the comparisons.

Semiconductor manufacturing was chosen to test these scheduling rules and is known to be one of the most complex manufacturing environments because of its highly reentrant characteristic. Improvement in the area of resource scheduling during manufacturing will have a positive affect on several industries where semiconductor chips are utilized including consumer electronics, automotive sub-assemblies, military applications, and others.

2. Queueing Theory

2.1 First In First Out

This is the most common queueing and dispatching rule employed in the workplace. The idea is to work on the lot or job based on its ranking as to the order of their appearance at the machine in question. In this case its irrelevant to know which buffer the lot or job pertains to. The only criteria is the age of the lot with respect to all the other jobs waiting to be processed. The older the lot, the higher the priority in determining whether to process it or not.

2.2 Little’s Law

Little’s law in queueing theory [6] states that:

where is inventory, is the mean arrival rate of products for processing, is the total cycle time, namely the processing time plus waiting time involved. As a result, we have that for a fixed input or output, cycle time is proportional to the total system inventory.

We let be the average service (processing) rate and the server utilization (loading intensity), then

since products are fed in no faster than the processing rate.

2.3 Kingman’s Formula

To account for random variations in arrival and processing times, let denote the coefficient of variation of the inter-arrival times and let denote the coefficient of variation of the service times . We define

We say that describes the total systems variability. Assume that the inter-arrival times and service times are independent identically distributed (iid) random variables and the two streams are independent of each other. Assume that there is one server, so we consider GI/GI/1 queue [8] (general independent service times, and 1 server).

Kingman’s formula [7] states that

Hence, if is near 1, the inventory is very sensitive to variability. For fixed system variability , the inventory decreases as decreases.

Minimum inventory variability scheduling (MIVP^®) introduces maximum correlation between inter-arrivals times and service times to reduce the man-made scheduling variability.

2.4 Minimum Inventory Variability Policy^®

The idea behind Minimum Inventory Variability Policy^® (MIVP^®) is to schedule lots based on a heuristic algorithm that focuses on decreasing the man made variability of resource scheduling to reduce cycle-time. This policy takes into account the fact that a machine will share several operations in a typical highly reentrant factory like a semiconductor plant. The machine processes the jobs in an order in the queue according to a control law or schedule. In a minimum inventory variability schedule, we choose the scheduling policies in a way that we minimize the difference between the instantaneous inventory N(t) and the average inventory profile (see Figure 1. below), subject to the following constraints:

· a machine can only reduce inventory for the operation it is responsible

· increase inventory for the next down stream operation

It is the purpose of MIVP^® to minimize the deviation of N(t) from. It is not the purpose of this paper to inform the reader on the derivation of the algorithm but only to its adequacy in a simulated version of a manufacturing environment.

Let us consider minimizing the total cycle-time (from raw material to finished product) given a fixed input/output schedule. To minimize cycle time, one must reduce inventory or increase capacity according to Little’s Law, or reduce variability. A balanced production line then is one if given a fixed input and output schedule, the mean work-in-progress does not increase over time due to randomness of machine failures and repairs.

Unbalancing of a production line can be caused by unpredictable disturbances such as equipment failures and repairs, personnel decisions, power failures and, even bomb scares closing factories. These disturbances disrupt the stable flow of products and may result in large queues for some machines while other machines remain idle. Large queues, no matter what the cause, are referred to as bottlenecks, and days or weeks might be required to re-balance the production line. When a bottleneck occurs, it causes product to wait for service, thereby increasing its cycle time (CT). For our discussion, cycle time is defined to be the sum of the total processing time (TPT) and the total queueing time (TQT). TPT is defined as the sum of all the raw processing times for each step in a production flow and TQT is defined as the sum of all the queue waiting times for resource service for each step in a production flow. Millions of dollars can be spent on equipment to increase the capacity at a critical bottleneck resulting in reduced cycle time locally, but the overall cycle time of the product might not decrease. This local improvement approach might simply move the bottleneck to another location along the manufacturing line. Understanding that local changes to improve the service at overcrowded machines generally will not improve the total product cycle time is of utmost importance. We search to reduce CT by reducing the man-made variability through resource scheduling, product release policies, labor and machine utilization’s, using historical MTBF and MTTR.

2.5 Minimum Inventory Variability Policies^® (MIVP^®) for Resource Scheduling

If one were to look at a hypothetical product inventory profile like the one in Figure 1., one would be able to see the number of jobs, (or as is the case in semiconductor manufacturing, the number of lots N(t) at time t), that are waiting to be processed. Superimposed on this graph is the historical profile of the lots represented by .

With this policy, the dynamic inventory shown in Figure 1., will keep close to the long-term historical average inventory (the profile) in a stable factory. This leads to the reduction of the scheduling variability, reduction in total inventory, and reduction in mean cycle time. The result of the MIVP^® is the line balancing to reduce WIP variability. Large queues in front of a particular process resource will cause irregularity in the process flow, i.e., an unbalanced line. Some stations are overloaded and some are starved for operations in the production system. The mean cycle time will rise due to starvation even though the total system inventory stays approximately the same [1, 2, 4, 5, 9, 10, 11, 13, 14, 15, 18]. MIVP^® can reduce the line imbalance by pulling WIP into the queues having lower inventory as shown in Figure 1.

Figure 1. WIP CHART [4, 5, 9, 10, 11]

3. MIVP^® HEURISTICS

3.1 1-Step Ahead MIVP^®

Choose the items in the queue according to the following priorities:

Priority I: Operation such that

Priority II: Operation such that

and

Priority III: Operation such that

Priority IV: Operation such that

and

These are decision rules: If ..., then, else where is the historical average. If Priority I does not exist, go to Priority II, if this does not exist go to Priority III, and so on. If two items tie with the same priority, use FIFO or DDF or some other (pre-defined) allocation rule. Once a choice has been made, the wafer lot chosen is processed on Machine A. This decision set of rules then are applied simultaneously throughout the FAB by operators, which in-turn balances the total production line.

Figure 2. MIVP^® Priority Matrix and the selection order for Machine A in Fig. 1. for 1-step ahead [4, 5, 9, 10, 11, 14, 18]

For example, four process steps require the service of Machine A (Figure 1.). Which one do we choose? Machine A serving this four-process step is the feeder machine to the next machine in the process flow called bleeder machine. Applying the priority rules from our 1-Step Ahead MIVP^® we look down stream to the next queue in the process flow for all queues that have a job requiring the service of Machine A. A lot is then selected from a queue in this set of queues which will feed the bleeder machine leaving its instantaneous queue length below its historical average, . In our example, then we would choose process step 35 using the priority matrix of Figure 2. Of course, once we have selected a lot for processing by one of the priorities above, we start all over when machine A becomes available again. Therefore, the second priority would only be chosen if the first did not exist and the third priority would not be chosen unless the first and second did not exist, and so on. This example shows only four queues in contention for service of Machine A, but in reality with a reentrant line and multiple products, you can have many more. The matrix becomes a visual representation of selection order for any process, only the step numbers for the queues change.

3.2 K-Step Ahead MIVP^®

Choose the items in the queue according to the following priorities:

Priority I: Operation such that

and

Priority II: Operation such that

and

Otherwise, choose FIFO or DDF or some other pre-determined allocation rule. Based on this rule, if the instantaneous inventory in Figure 1. is larger than its average at operation for Machine A, the operation , etc., will be the one with its largest current inventory sum below average in the next K steps. Now observe Figure 3., the decision for Machine A is made by taking the average of the next 3 steps if k=3 and determining which step has the largest current inventory sum below the average inventory profile . For this example, the same choice is made as if we were using 1-Step Ahead MIVP^®, i.e., select the lot from the queue in step 36 for the next process for Machine A.

This K-Step Ahead MIVP^® is the policy that we are comparing in the simulation model to the 1-Step Ahead MIVP^® and to FIFO to determine which is better for reduction of cycle time on the factory floor.

Figure 3. MIVP^® Priority Matrix and the selection order for Machine A in Fig. 1. for K-steps ahead = to 3 [32]

4. Research PREMISE

4.1 Scope

The scope of this research is to prove the adequacy of the Minimum Inventory Variability Policy^® (with K-Step Ahead MIVP^®) when compared to FIFO and the Minimum Inventory Variability Policy^® (1-Step Ahead MIVP^®). By comparing several important factors like product turn around time (TAT), or cycle time, and the variance of the cycle times. In order to achieve this comparison, a method by which to test this algorithm was needed.

A computer simulation model was employed that models a semiconductor manufacturing FAB. This model was validated and verified with the SEMATECH Dataset in order to achieve conditions as close as possible to real-life conditions.

The 1-Step Ahead MIVP^® and K-Step Ahead MIVP^® algorithms were developed in Automod^® language code to allow lots to be scheduled by them within the AutoMod^®/AutoSched^® environment. Once data had been gathered for replications that mimic conditions under FIFO, 1-Step Ahead MIVP^® and K-Step Ahead MIVP^® (e.g. k=1 through 10). Eleven sets of simulated data were collected, each covering 750 days of simulated factory production. The data points for each run was output every 25 days. The first 125 days were eliminated due to ramp-up conditions and the last 25 data points were used to perform the statistical calculations. The eleven sets of data included a baseline run for FIFO resource scheduling and ten additional runs for 1-step ahead to 10-steps ahead. It was found that 3-steps ahead gave the best results with this product mix. The conclusions for each multiple run were statistically obtained to satisfy a 95% confidence interval. Each simulation run took 24 hours on a 166 mega-hertz Pentium^® PC.

4.2 Limitations

Intuitively, one can see that the more specific one gets with a simulation model the more information will be included and therefore the more processing time. It was the purpose of this research to compare the results of 1-Step Ahead MIVP^® policy with that of an exact model built on Extend^®. Unfortunately, the implementation of K-Step Ahead MIVP^® on AutoMod^®/AutoSched^® could not be compared to the implementation of 1-Step Ahead MIVP^®on Extend^®. It was found that this was impossible because of the way the distribution functions in the two software packages were written. Therefore, it was decided to compare 1-Step Ahead MIVP^® with K-Step Ahead MIVP^® in the same AutoMod^®/AutoSched^® environment. It was not the purpose of this research to rewrite the distribution functions, but to use standard off the shelf software for this purpose. A discussion of different distribution functions can be found in [25, 27].

For the purposes of comparing cycle time and variance of cycle time, labor was not included in the model. Contamination concerns, or yield variability was another factor that was not addressed. Experience has shown that yield is one variability of great concern in semiconductor manufacturing that has great repercussions on product throughput [29]. Yield will be addressed using MIVP^® in another paper.

4.3 Background

In December of 1993, Y. Tang finished his research entitled “Simulation Model For Minimum Variability Policy Practiced In Semiconductor Manufacturing Plants” [10]. Tang, examined several different dispatching policies in the wafer FAB along with MIVP^®. His results indicated that dispatching policies showed dramatic differences. Five popular schedules are compared with 1-Step Ahead MIVP^®. These were FIFO (first in first out), SNQ (smallest number in queue), LNQ (largest number in queue), RAN (random priority), CYC (cyclic priority), as listed in Table 1. below, which shows the comparison of simulation experiments. MIVP^® had the most efficient production when simultaneous reductions in both the mean cycle time and standard deviation of cycle time were observed.

Table 1. The Comparison of Simulation Experiments[10]

Release or Launching Policy	Dispatching or Scheduling Policy	Mean Cycle Time (95% Conf. Interval) Hours	Standard Deviation of Mean Cycle Time Hours	Throughput Rate	Mean TQT Hours	% Improvement in Mean TQT (over FIFO)
Poisson	FIFO	373 (+ 12.5)	159.8	0.10003	337	Baseline-0
Poisson	SNQ	441 (+ 11.9)	239.6	0.09987	405	- 20.2
Poisson	LNQ	360 (+ 12.2)	167.9	0.10002	324	3.9
Poisson	RAN	369 (+ 13.4)	177.6	0.10001	333	1.2
Poisson	CYC	339 (+ 9.3)	161.6	0.09999	303	10.1
Poisson	MIVP^® 1-Step	324 (+ 7.8)	138.9	0.09983	288	14.5

In February 1996, R. Wiedmeyer’s “A Minimum Inventory Variance Policy Computer Simulation Using SEMATECH Semiconductor Manufacturing Data”, investigated 1-Step Ahead MIVP^® on a simulated semiconductor FAB Dataset. The Dataset was taken from a SEMATECH generic model of a dram chip manufacturer (this Dataset was in error and was not corrected by SEMATECH until after the project was completed). There was a machine missing in a crucial bottleneck section of the FAB, which became evident in the simulation. The WIP never stabilized, it continued to grow through all simulated production runs. Also the raw processing times were not correct which will improve the results presented. Even with the errors 1-Step Ahead MIVP^® demonstrated that it is the better policy when compared to FIFO. One possibly conclusion can be arrived at is that MIVP^® will improve dramatically over FIFO when a bottleneck occurs. We are in the process of rerunning this Dataset on Extend^® with the corrected values from SEMATECH to determine the comparative results. We also plan to remove the machine at the bottleneck and run the simulation to see if MIVP^® truly works better when a bottleneck condition occurs, caused by scheduling and emergency maintenance variabilitys. It was the first time that MIVP^® was applied to a complete factory-floor. Weidmeyer’s results in Table 2. were very promising in that total queue time was reduced as much as 46% for product A and 43% for product B [11] when 1-Step Ahead MIVP^® was compared to FIFO even though the factory was not stable.

Table 2. SEMATECH Model Comparisons of FIFO with 1-Step Ahead MIVP^® using Extend^®

Product A Product B

Mean Cycle Time, FIFO 1,222.0 hrs. 1,551.0 hrs.

Mean Cycle Time, MIVP^® 808.0 hrs. 1,043.0 hrs.

Raw processing Time 313.4 hrs. 358.6 hrs.

TQT, FIFO 908.6 hrs. 1192.4 hrs.

TQT, MIVP^® 494.6 hrs. 684.4 hrs.

Reduction by MIVP^® 414.0 hrs. 508.0 hrs.

Percentage Improvement FIFO 46% 43%

4.4 Equipment and Support

This K-Step Ahead MIVP^® research was conducted during 1996 on the AutoMod^® 7.5/AutoSched^® 4.0 simulation package by ASI. The new corrected Dataset for the simulation model was provided by SEMATECH. They have created a database of several generic semiconductor FABs available to all member companies and learning institutions. The FAB modeled in the following experiments was created from the corrected Dataset #1.

A thorough understanding of semiconductor processing and its logic was paramount to the verification and validation of this model. Two, three month, internships and one, eight month sabbatical in three of Motorola’s Semiconductor Products Sector FABs provided the authors with the necessary background and experience.

4.5 Research Objectives

The research objective was to find an adequate resource scheduling policy that performs well when subjected to random disturbances, which include, but, are not limited to, machine failures, random rework, and demand fluctuations.

The successful modeling of a semiconductor FAB was achieved. This model was validated and verified. 1-Step Ahead MIVP^® and K-Step Ahead MIVP^® rules were written in Automod^® language code and included as new resource schedulers in the AutoMod^®/AutoSched^® language.

5. Literature Review

5.1 Previous Research

There have been many researchers looking at resource scheduling such as Kumar et al [1, 2, 13, 30], Fargher et al [22], and Savell et al [28]. R. Uzsoy et al has completed a review of many works [19] and Mason et al compared four simulators [25]. Queueing networks by Chen et al [12], optimization by K. Akbay [20], last station bottleneck by Chandra et al [21], closed loop job release by Glassey et al [23], robustness by Lou et al [24], object oriented simulation by Najimi et al [26].

The most notable work in the field of minimum inventory resource scheduling was conducted first by Li, et al [4, 5, 10], Tang [9] and later by Wiedmeyer [11]. Their work set the stage for the continuation work that this research addresses. The previous work of Li, Tang and Collins [10] dealt with the implementation of the algorithm in two semiconductor FABs (Intel and Motorola) and more recently by Collins [31] in a Motorola FAB with positive results. Tang simulated his work via Siman^® and Wiedmeyer created a model similar to the one employed in this research that focused primarily on the adequacy of 1-Step ahead MIVP^® using Extend^®.

6. Methodology

6.1 Data Collection

There was two areas of data collection needed for this research. The first involved the collection of data for the construction of the simulation model. As mentioned earlier this data originated from SEMATECH Dataset #1., Table 3. below gives the parameters of the Dataset used for this research.

Table 3. SEMATECH Data Summary

Data Set Location