Simulation-based real-time scheduling in a flexible manufacturing system

Simulation-based real-time scheduling in a flexible manufacturing system

Journal of Manufacturing Systems Volume 13/No. 2 Simulation-Based Real-Time Scheduling in a Flexible Manufacturing System Min Hee Kim, Samsung Data S...

891KB Sizes 15 Downloads 62 Views

Journal of Manufacturing Systems Volume 13/No. 2

Simulation-Based Real-Time Scheduling in a Flexible Manufacturing System Min Hee Kim, Samsung Data Systems, Seoul, Korea Yeong-Dae Kim, Korea Advanced Institute of Science and Technology, Daejon, Korea

Abstract

ations are automated, and most operations are processed by NC machine tools, so processing times are nearly deterministic. This implies that the schedule result (performance) is predictable if there are no system disturbances. In some situations, therefore, fixed off-line scheduling may be enough, although the problem is analytically difficult. The dynamic and uncertain nature of system states, however, may make off-line scheduling impractical for FMSs. In general, FMSs are more sensitive to system disturbances than conventional manufacturing systems because of tighter synchronization, system integration, and interdependencies among automated components. Hence, they require an immediate response to changes in system states, and this can be achieved by real-time scheduling, where decisions are based on actual system states, such as arrival of parts, machine states (up or down), queues at machines, tool breakages, rushed jobs, and many other system disturbances. Very few general results are given by scheduling research. Performance of scheduling methodologies depends on the criterion chosen as well as on the configuration of the system. 2 Therefore, for any given system, one must carefully select a suitable performance measure according to the system's needs and then evaluate various scheduling methods on that measure. In this paper, we consider an FMS with the characteristics of an open job shop, where all production orders are requests from customers or downstream processes. We assume that the process plan for each part, configuration of the system, and system objective(s) are given. Also it is assumed that decisions on lot size and machine job assignments are made earlier in the decision process so that part routings are given as well. Notice that larger savings may be obtained if these decisions are

We present a simulation-based real-time scheduling methodology for a flexible manufacturing system. Developed is a scheduling mechanism in which the job dispatching rule varies dynamically based on information from discrete event simulation that evaluates a set of candidate rules. Major components of the scheduling mechanism are a simulation mechanism and a real-time control system. The simulation mechanism evaluates dispatching rules and selects the best dispatching rule for a given criterion. The real-time control system periodically monitors the shop floor and checks the performance value of the system. The selected dispatching rule is used until the difference between the actual performance value and the value estimated by simulation exceeds a given limit. Then a new simulation is performed with the remaining operations in the simulation mechanism to select a new rule. Results of computational tests show that the scheduling mechanism can be used effectively in real situations because it can fully use the information on the actual state of shop floors.

Keywords: Flexible Manufacturing Systems, Scheduling and Control, Simulation Methods, Scheduling and Sequencing Techniques

Introduction Decision-making problems in flexible manufacturing systems (FMSs) can be divided into four stages: design, planning (or system setup), scheduling, and control. ~ The FMS scheduling problem concerns the flow of parts and running the system in real time after setup. The problem includes determining an input sequence of parts and a sequence of operations at each machine tool given the system configuration and part mix. Different approaches can be taken to scheduling parts manufacturing systems. Operations are computer controlled, setups between consecutive oper-

85

Journal of Manufacturing Systems Volume 13/No. 2

made optimally or near optimally. For example, careful process planning may simplify the problem and help find a good schedule more easily; however, we do not consider the above higher-level decision problems in this paper, but we deal with the lower-level operations scheduling problem that should be solved after those decisions are made. Many different scheduling and control methods for FMSs have been proposed and analyzed. Yamamoto and Nof 3 suggest a scheduling/ rescheduling method for real-time control of a computerized manufacturing system. In this method, an initial schedule is generated at the beginning of a work period, and schedule revisions are made when significant operational changes occur. Church and Uzsoy 4 analyze periodic and event-driven policies for rescheduling on single and parallel-machine models. These scheduling/ rescheduling methods implicitly treat the dynamic scheduling problem as a series of static problems that are solved on a rolling-horizon basis. Raman, Rachamadugu, and Talbot s analyze and suggest procedures for this type of dynamic scheduling problem. On the other hand, Yih and Thesen 6 formulate the real-time scheduling problem as semiMarkov decision models. There are several methods using artificial intelligence (AI) techniques for real-time scheduling and control, for example those by Maimon; 7 Maley, Ruiz-Meir, and Solberg; 8 Shaw; 9 and Sarin and Salgame, ~° among others. Maley, Ruiz-Meir, and Solberg conceptualize a closed-loop control structure for scheduling and control of a computerintegrated manufacturing system, and Sarin and Salgame develop an interactive, real-time, knowledge-based approach for dynamic scheduling. Maimon proposes a three-level control system (scheduler level, communication level, and process sequence level), while Shaw views scheduling as a process with two levels of decision making, assigning jobs to appropriate cells and scheduling jobs within each cell. A similar two-level hierarchical structure for scheduling methods is suggested in Mohd, Jose, and Mulligan. ll'lz Simulation is found to be very effective in the design, implementation, and operation of FMSs. Moreover, it can be used as a decision support system for real-time scheduling of manufacturing systems. Davis and Jones ~3 present a conceptual

example of this and propose a framework for addressing real-time scheduling problems in a stochastic environment. Also, simulation can be (and often is) used for evaluating scheduling methods on various system environments. Computer technology has significantly reduced computation time for this evaluation so that simulation may be used as a tool for real-time evaluation in many circumstances. A combination of AI and simulation may result in a much richer modeling capacity. Lyons, Duggan, and Bowden 14 discuss the design, development, and implementation of a pilot production activity control system in an electronics assembly environment as part of the ESPRIT (European Strategic Programme for Research and Development in Information Technology) project. Wu and Wysk ~s state that by combining a learning system with simulation, a manufacturing control system can be developed that learns from its historical performance and makes its own scheduling and control decisions by simulating alternating combinations of dispatching rules. Based on these concepts, they present a multipass scheduling algorithm that includes a mechanism controller and a flexible simulator. For a further review of various approaches to real-time scheduling in computer-integrated manufacturing systems, refer to Harmonosky and Robohn. 16 In this paper, we develop a scheduling mechanism based on the scheduling/rescheduling approach. In the mechanism, job dispatching rules are selected according to results from discrete event simulation. There are two major components, a simulation mechanism and a real-time control system. The simulation mechanism evaluates various dispatching rules and selects the best one for a given criterion. The real-time control system periodically monitors the shop floor and checks the system performance value. The best dispatching rule is used until the difference between the actual performance value and the value estimated by simulation exceeds a given limit (called "performance limit" in this paper); then a new simulation is performed with remaining operations in the simulation mechanism, and a new rule is selected.

Real-Time Scheduling Mechanism As noted earlier, it is assumed that we have results of planning problems, such as those of

86

Journal of Manufacturing Systems Volume 13/No. 2

machine grouping, allocation of pallets and fixtures, and assignments of operations and associated cutting tools to machines. Also, it is assumed that a performance measure of the system is given and that a set of candidate dispatching rules has been selected based on the shop floor environment, such as system objectives, system status, and characteristics of jobs and orders. These are inputs to the simulation mechanism. The system concept is illustrated in Figure 1. The two components and information flow in the system are controlled by a scheduling controller. It contains a rule selector, which calls the simulation mechanism when selection of a best dispatching rule is required. This selection is done at the beginning of each planning horizon and/or if periodic monitoring finds that the system is not running as expected because of (accumulation of minor) system disturbances or when there is a major system disturbance. Note that there is only one scheduling activity in each planning horizon if there are no changes in the system environment. The simulation mechanism includes a model constructed by information from decisions of the planning problem. When the rule selector calls the simulation mechanism, a series of discrete event simulations is performed with each rule in the dispatching rule set under the same conditions. With

shopfloor

I

the outputs from the simulation, the rule selector selects the best one for a given performance measure. Then the selected rule goes to the scheduling controller and becomes an input to the control system. Jobs are dispatched according to this rule at the shop floor. At this moment, the scheduling mechanism saves the performance value that is estimated from the selected dispatching rule. This estimated value is another output from the simulation mechanism. The mechanism does not include unknown future machine breakdowns and rushed jobs, but does include the current and given system state. (Therefore, it may be considered as a deterministic simulation.) This is because randomly occurring machine breakdowns and rushed jobs may give wrong evaluation results. The real-time control system sends all scheduling controller information to the shop floor and dispatches jobs to machines accordingly. Also, the real-time control system periodically monitors and checks the actual performance value of the shop floor. If the difference between actual and estimated performance values exceeds a predetermined limit (performance limit) at a point of monitoring, a new series of discrete event simulations is performed with the remaining operations under the current state to select a new dispatching rule. If the difference is within the performance limit, the remaining process is continued with the current rule. Sometimes system disturbances occur, such as machine breakdowns, tool breakages, and arrivals of urgent jobs. These are categorized into two levels--major disturbances and minor disturbances. Major disturbances include arrivals of urgent jobs and major machine breakdowns, ones requiring long or unestimatable repair time. On the other hand, tool breakages and machine breakdowns for which the estimated repair time is short are considered minor disturbances. In case of a major disturbance, the scheduling controller calls the simulation mechanism to perform a new simulation with the new system environment. A new simulation is also performed when the system state is back to normal (in cases of major machine breakdowns). When a minor disturbance (machine failure or tool breakage) occurs, the realtime control system reroutes jobs from the disabled machine. Among machines that can process the job to be rerouted, a machine with the shortest queue

]

systemstates and! t actual performancei]dispatching

Y SimulationMechanism

ControlSystem [Perfo......... limit]

Sinlulationmodel[ k . . . . . . . svstel~ ~i~;~ ...... I Estimatedperformance

J LSeheduling ControllerJ

Figure 1 Scheduling Mechanism

87

Journal of Manufacturing Systems Volume 13/No. 2

length is selected for rerouting. At this point a new simulation is not performed, but it may be done after periodic monitoring according to the difference between estimated and actual performance values. Note that a system without monitoring implies one in which a new schedule is obtained only in case of major disturbances. Performance of the suggested method may depend on two parameters: the length of a monitoring period and the performance limit for rescheduling. For the suggested real-time scheduling methodology, it is recommended to test several alternatives for the monitoring period and performance limit on the system considered and apply the best. Performance may depend not only on these parameters but also on the set of dispatching rules in the scheduling mechanism.

the due time of operation i (due time of the job in which operation i is included), t is the time at which priority rules are applied or an operation is to be selected for an available machine, w i is the remaining work of operation i (sum of processing times of successor operations including itself), and oi is the remaining operations of operation i (number of successor operations including itself). Also let x + denote max (0,x). The dispatching rules are described as follows:

Dispatching Rules

PDJT

SPT

SJT

When a machine becomes available, an operation that can be processed there must be assigned to it. If two or more operations are ready, one has to be selected according to some rule (called a "dispatching rule' ') that usually defines priorities (urgencies) of the operations. The following dispatching rules, described later, are included in the scheduling mechanism: SPT, SJT, PDJT, PMJT, FCFS, SLACK, S/RMOP, S/RMWK, EDD, MDD, MOD, COVERT, and ATC. These rules can be used for job shop scheduling problems that are static as well as dynamic. They were selected because they revealed good results for certain performance measures in previous research. Evaluation of these rules can be executed in a short time even on a personal computer, so all of the dispatching rules may be considered in the scheduling system. We now briefly describe these dispatching rules. See Panwalkar and Iskander; 17 Blackstone, Phillips, and Hogg; 18 Russell, Dar-E1, and Taylor; 19 Vepsalainen and Morton; 2° Kim; 21 and Ramasesh 22 for details of these rules and test results on the performance on various system configurations. The following section defines priorities of operations in the dispatching rules. A part to be processed is called a job. Each job consists of a set of operations, each of which can be processed on a certain set of machining centers. Here, Pl denotes processing time of operation i, d i is

PMJT

FCFS

SLACK S/RMOP

(Shortest processing time) Select an operation with the shortest processing time (Shortest job processing time) Select an operation with the shortest job processing time (sum of processing times of the operations for the job) Select an operation with the smallest ratio of processing time to job processing time Select an operation with the smallest value obtained by multiplying processing time by job processing time (First-come first-serve) Select an operation that arrived at the machine earliest Select an operation with the least slack (d,-- w,'-O (Slack per remaining operations) Select an operation with the smallest ratio of slack time to number of r e m a i n i n g o p e r a t i o n s , that is, (dt-wl-t)/o i

S/RMWK

(Slack per remaining work) Select an operation with the smallest ratio of slack time to remaining work, that is, (d~-w r- t)/w i

EDD MDD

MOD

(Earliest due date) Select an operation with the earliest due date (Modified due date) Select an operation with the minimum modified due date, which is defined as max { d i, t + w i } for operation i (Modified operation due date) Select an operation with the minimum modified operation due date, that is, max { dt--b ( w F p i ) , t + W i }

88

Journal of Manufacturing Systems Volume

COVERT

(Cost over time) Select an operation with the largest ratio of expected delay penalty to processing time, that is, select an operation with the maximum value of

tively, from an estimated performance value, the simulation mechanism was called. In addition, a scheduling mechanism without monitoring is included in the test to find the effect of periodic monitoring.

System Under Consideration The system considered is a flexible manufacturing system consisting of six horizontal machining centers, a washing machine, two load/unload stations, a workpiece stocker, and a stacker crane for material handling. The machining centers may contain different tools to process different operations. The workpiece stocker can store up to 90 pallets, and the stacker crane transports pallets between the machining center and stocker. A schematic representation of the system is depicted in Figure 2. Jobs arrive in batches at the beginning of each planning horizon according to production plans, except for urgent jobs that can arrive any time. Each job is processed on a series of machines as defined in the planning stage. Due dates are assigned to the jobs according to processing time, that is, the due date is equal to arrival time plus six times total processing time. Processing and transportation times are known and deterministic. Also, a next set of jobs is considered only after the set for the current planning horizon is completed if the jobs are not urgent. A workpiece released to the system is mounted and fixed onto a pallet by an operator at one of the load/unload stations. If the machining center to process the workpiece is idle, the loaded workpiece is transported to it by the stacker crane and processed; however, if the machining center is occu-

(dt..wrt) +

[{1

ATC

k.b.

wi

13/No. 2

} / Pi ] +

(Apparent tardiness cost) Select an operation with the largest apparent tardiness cost, that is, select an operation with the maximum value of exp [-{ dc-b (wt--pi)-pFt } + / k'p]/pi where p is the average processing time of the waiting operations.

In the last three rules, b and k are parameters that must be specified. They consider waiting time of operations in queues and machine utilization when estimating job completion time and are needed because the sum of processing times of an operation and its successors is not an accurate estimate of completion time of the corresponding job. b is called the lead-time estimation parameter that considers waiting time between operations, k is called the adjustment multiplier that adjusts expected waiting time to the worst case, for example, the 95th percentile of the cumulative probability distribution. See Russell, Dar-E1, and Taylor 19 and Vepsalainen and Morton 2° for more detail on these parameters.

Computational Experiments To find applicability of the proposed methodology to an FMS that produces machine tools, we performed simulation experiments. As suggested earlier, we tested several alternatives for the monitoring period and system performance limit. There may be various bases for the length of the monitoring period. In this research, mean operation processing time (MPT) was used for the basis. Lengths of the monitoring period tested were MPT × 5, MPT × 8, MPT × 10, andMPT × 12. Also, we tested four alternatives for performance limits--3, 5, 7, and 10%--which means that if an actual performance value deviated 3, 5, 7, or 10%, respec-

lllllllllllllllllllltll,,

< Workpieces slocker >

[IIIIIIIIILIIIIIIIIIII[IIIIIIIIIIIIIIItll

lll

< Contrcll cl~mputer >

[lllllli[ITIil~

< HMCs > < TI~I~I magazine >

Figure 2

Flexible Manufacturing System

89

Journal of Manufacturing Systems Volume 13/No. 2

pied, the loaded workpiece is transported to the stocker to wait. When a machining center completes a workpiece, it selects another to process next from those in its queue according to a dispatching rule. The completed workpiece goes to another machine for its next operation if that machine is available or to the stocker. If all operations of the workpiece have been completed, it is transported to the washing machine, washed, and then transported to a load/unload station to be unloaded. This flow is controlled by a control computer that has all of the information about workpieces at the machine queues, including arrival time, total processing time, remaining work, total number of operations, remaining number of operations, and due date. Three performance criteria are used in this system: mean flow time, mean tardiness, and a bicriterion measure combining the other two with weighting factors. The bi-criterion measure gives equal weights to mean flow time and mean tardiness because both objectives are considered important. Although these measures are used in this system, we can apply the suggested scheduling method to systems with other objectives, such as minimizing setup time or makespan, that may be considered more important in many systems.

2. Machines (primary and alternative) that can process each operation are randomly selected with equal probability, where the number of alternative machines is also randomly selected from 0, 1, and 2 with equal probability. An alternative machine may be used for an operation only when its primary machine is unavailable because of breakdown. 3. Processing time of an operation is exponentially distributed with given mean values (40, 50, or 60 minutes). 4. Loading and unloading times are generated from exponential distributions with means of 15 and 10 minutes, respectively. 5. Washing time is generated from EXP(10) (an exponential distribution with a mean of 10 minutes). 6. Transportation time is generated from EXP(2). 7. Urgent jobs arrive with an interarrival time generated from EXP(400). Due dates of an urgent job are equal to the arrival time plus job processing time. 8. Major breakdowns occur with an interfailure time of EXP(1500) for each machine in the system, and the repair time for each failure is generated from EXP(200). 9. Minor breakdowns, including tool breakages, occur with an interval generated from EXP(500) for each machine, and each repair time follows EXP(30).

Test Problems In the simulation experiments, nine replications are made characterized by three levels of number of jobs considered in a planning horizon (20, 30, and 40) and three levels of mean processing time (40, 50, and 60 minutes). The simulation is performed for the length of one planning horizon in each replication, except for the case in which the number of jobs considered is 20. In this case, two planning horizons are simulated. In each replication, we simulate implementation of 17 scheduling metho d s - 1 without monitoring and 16 from alternative combinations of length of monitoring periods (MlYr × 5, MPT × 8, MPT × 10, and MPT × 12)and the performance limits (3, 5, 7, and 10%). For the test, we randomly generated problem instances so that the resulting problems closely represent the system described above. Data for the problems are generated as follows:

The experimental model is programmed in SIMAN IV with subroutines written in FORTRAN and run on a personal computer with an 80486 processor. As mentioned earlier, the simulation mechanism suggested does not include machine breakdowns and urgent jobs; however, the simulation model that represents the real shop floor in the experiments contains randomly occurring system disturbances. Result In the MOD, COVERT, and ATC rules, we must select the most appropriate value for parameters b and k. Several values (1, 2, and 3 for both parameters) were tested on a number of randomly generated problems. For MOD, b = 1 gave the best results, and the combination of b = 3 and k = 1 was the best for COVERT, while ATC performed best

1. The number of operations for each job is generated from a discrete uniform distribution with a range 3 to 6.

90

Journal of Manufacturing Systems V o l u m e 13/No. 2

when b = 1 and k = 1. These parameter values are used for those rules in the simulation mechanism. Results are shown in Tables 1-3. In the tables, mean improvement percentages are given for each combination of monitoring periods and performance limits. Improvement percentages were computed with 100 (So-Sm)/So, where So is the solution value (mean tardiness, mean flow time, or value of the combined measure) without monitoring, and Sm is that with periodic monitoring. A statistical test was done to test significance of the improvements, although results are not shown in a table. Test results showed that there were differences between systems with and without periodic monitoring at the significance level of 0.01 in all three measures. Therefore, it can be said that there is an advantage to checking the system performance periodically and responding to a change in performance by rescheduling. To show the effects of different monitoring periods and performance limits, ANOVA (analysis of variance) tables are given in Table 4. Results show that different monitoring periods may give different performances in all three measures tested. As shown in Tables 1-3, monitoring periods of

lengths MPT × 8 and MPT x 10 gave better results than MPT x 5 and MPT x 12. This means that too-long monitoring periods result in worse performance of the system and also that too-frequent monitoring (and rescheduling) may negatively affect performance. System performance was affected by performance limits as well. The limits significantly affected performance of the scheduling mechanism in mean flow time and combined measure, although they had little effect on performance in mean tardiness. As with monitoring periods, systems with too-small and too-large limits were outperformed by those with limits of moderate size (7 and 5%). This might be because that with too-small limits the reschedulings are done so often that the actual system performance cannot be obtained as expected; schedules or scheduling rules selected from the simulation mechanism are good only when they are executed for a long-enough duration in many cases. Table 5 compares various dispatching rules included in this research. It shows the number of times each rule gave the best result at the initial simulation and at the points of subsequent simulations that were done in cases of system disturbances. Results are slightly different from what we can expect from other research on job shop scheduling, especially for mean tardiness. COVERT and ATC did not perform very well, and rules that do not consider due dates worked well enough. The reason seems to be that the due date of each job was set as a multiple of its job processing time, which makes the processing time carry some information about the due date. It should be noted that determining which rule works better than others is not important in our approach; we can test all these rules and select the best one with very little evaluation time.

Table 1

Mean Improvement Percentages in Mean Flow Time nit°rin[~ MPTx5

MPTx8

MPTx10

1.19

1.20

1.83

m a n e e Limits 3%

MPTxI21 Overall 0.91

1.28

5%

1.52

1.82

1.93

1.20

1.62

7%

1.62

2.08

1.91

1.31

1.73

10%

0.47

1.22

0.81

0.52

0.76

Overall

1.20

1.58

1.62

0.99

1.35

Table 2

Table 3

Mean Improvement Percentages in Mean Tardiness

Mean Improvement Percentages in the Composite Measure lit°ring

Monitoring Perfor-~riods manee Limits

MPTX5

3%

2.52

2.84

5.51

2.89

3.44

3%

0.54

5%

3.61

4.45

6.10

1.91

4.02

5%

1.41

MP'I~8

MPTx10

MPTX12

MPTx5

Overall

MPTx8

MPTX10

MPTx12

Overall

1.70

1.98

1.11

1.33

2.70

2.43

1.41

1.99

2.58

1.77

2.05

mance L i m i t s

7%

3.50

4.70

5.21

2.42

3.96

7%

1.49

2.36

10%

2.79

3.66

3.41

1.49

2.84

10%

0.01

1.18

1.07

0.27

0.63

Overall

3.11

3.91

5.06

2.18

3.56

Overall

0.86

1.99

2.02

1.14

1.50

91

Journal of Manufacturing Systems V o l u m e 13fNo. 2

Table 4

Table 5

Results of Statistical Tests

Comparison of Dispatching Rules (Number of Times Each Rule Was Selected)

(a) Analysis of variance for the effects on mean flow time Source of Variation

Sum of Squares

Degrees of Freedom

Mean Square

Dispatching rules

F

Tardiness

b

a

b

a

b

16

52

0

113

0

71

16

76

0

39

Composite

Performance Limit

1.329

3

.443

4.790**

SPT

Monitoring Period

0.889

3

.296

3.204*

SJT

0

23

Interaction

0.226

9

.025

0.272

Error

11.835

128

.092

PDJT

0

43

0

98

0

51

Total

14.279

143

PMJT

112

61

96

148

128

83

60

0

28

** There is difference in tile effects at siginilicance level of 0.01. * There is differencein the effects at sigrnificancelevel of 0.05.

(b) Analysis of variance for the effects on mean tardiness Source of Variation

Sum of Squares

Degrees of Freedom

Mean Square

F

Performance Limit

0.050

3

.017

O.163

Monitoring Period

1.305

3

.435

4.227**

Interaction

0.277

9

.031

Error

13.176

128

.103

Total

14.809

143

0.299

Sum of Squares

Degrees of Freedom

Mean Square

0

17

0

0

22

0

73

0

37

S/RMOP

0

28

0

95

0

51

S/RMWK

0

30

0

90

0

52

EDD

0

23

16

76

0

39

MDD

16

32

16

105

0

51

MOD

0

39

32

106

16

54

COVERT

0

50

0

120

0

67

ATC

0

22

0

82

0

33

suggested methodology can be used for real-time scheduling in many real manufacturing systems.

(el Analysis of variance for the effects on the combined measure

Source of Variation

FCFS SLACK

Tile number of times the rule gave the best solution at the initial simulation. The number of times the rule gave the best solution at subsequent simulations.

** There is difference in the effects at siginificance level of 0.01.

**

Flow time a

E

Performance Limit

1.217

3

.406

5.298**

Monitoring Period

1.067

3

.356

4.645**

Interaction

0.242

9

.027

0.351

Error

9.800

128

.077

Total

12.326

143

Concluding Remarks In this research, we presented a real-time scheduling and control mechanism designed for an FMS. The scheduling mechanism employs discrete event simulation to find a good schedule for a given system environment. This mechanism fully uses information of the current state of the shop floor to estimate system performance when a certain scheduling rule is executed. In the mechanism, rescheduling is done when the system seems to have disturbances and the system environment is thought to have changed significantly. These disturbances are sensed by the real-time control system during periodic monitoring through a comparison of actual system performance with that estimated by the simulation mechanism. Simulation experiments show that better results can be obtained by the scheduling mechanism with the monitoring period of moderate length and with the performance limit of 5 or 7% in the system considered in this research. The speed at which a control system makes decisions is directly related to the system's performance and is an important aspect of real-time

There is difference in the effects at siginificance level of 0.01.

Improvements shown in Tables 1-3 may not look impressive enough for the suggested methodology to be considered excellent; however, they show only the effect of periodic monitoring, not including the effect of using simulation mechanism for rule selection. The system without monitoring also used the simulation mechanism for rule selection. Therefore, one may expect much higher improvement (than those given in the tables) if we compare the suggested methods with others without the simulation mechanism. Another important good characteristic of the methodology is that it does not require long computation time. In the simulation mechanism, a run of the discrete event simulation (testing all dispatching rules and selecting the best) for a set of orders took less than 15 seconds on a personal computer. In view of its performance and speed, the

92

Journal of Manufacturing Systems Volume 13/No. 2

control. To maximize performance of a manufacturing system, an effective and timely means of scheduling and control needs to be developed. In the suggested approach, computation time required for evaluating candidate scheduling rules is short enough for the simulation mechanism to be used in real-time scheduling. Moreover, the predictive ability of simulation-based scheduling is better than most lookahead heuristics because details of an actual system can be included in operations scheduling. Hence, we can expect that the suggested simulation-based realtime scheduling methodology may be used practically and will give good results in many FMSs. This research may be extended in several ways. For instance, we may use another method for sensing system disturbances, such as by checking queue lengths, machine utilization, and/or completion times of operations. Also, other methods of defining monitoring periods may be considered. (In this research, we use mean operation processing time as a basis for the monitoring period.) In this paper, we implicitly assumed that major system disturbances did not occur too often and that a selected scheduling rule could be used for a reasonable time. The suggested methodology may not work as expected in systems in which machines are not reliable and urgent orders arrive often. Research on these unreliable systems may have to be done.

6. Y. Yih and A. Thesen, "Semi-Markov Decision Models for Real-time Scheduling," International Journal of Production Research (v29, n i l , 1991), pp2331-2346. 7. O.Z. Maimon, "Real-time Operational Control of Flexible Manufacturing Systems," Journal of Manufacturing Systems (v6, n2, 1987), pp125-136. 8. J.G. Maley, S. Ruiz-Meir, and J.J. Soiberg, "Dynamic Control in Automated Manufacturing: A Knowledge-Integrated Approach," International Journal of Production Research (v26, n i l , 1988), pp1739-1748. 9. M.J. Shaw, "Dynamic scheduling in Cellular Manufacturing Systems: A Framework for Networked Decision Making," Journal of Manufacturing Systems (v7, n2, 1988), pp83-94, 10. S.C. Sarin and R.R. Salgame, "Development of a KnowledgeBased System for Dynamic Scheduling," International Journal of Production Research (v28, n8, 1990), pp1499-1512. 11. N.K. Mohd, B.C. Jose, Jr., and J.H. Mulligan, Jr., "Performance Forecasts as Feedback for Scheduling Generation," Journal of Manufacturing Systems (vl 1, n5, 1992), pp326-333. 12. N.K. Mohd, B.C. Jose, Jr., and J.H. Mulligan, Jr., "Simulation Studies of Multilevel Dynamic Job Shop Scheduling Using Heuristic Dispatching Rules," Journal of Manufacturing Systems (vll, n5, 1992), pp346-358. 13. W.J. Davis and A.T. Jones, "A Real-time Production Scheduler for a Stochastic Manufacturing Environment," International Journal of Computer Integrated Manufacturing (v4, n3/4, 1988), pp53t-544. 14. G.J. Lyons, J. Duggan, and R. Bowden, "Project 477: Pilot Implementation of a Production Activity Control (PAC) System in an Electronics Assembly Environment," International Journal of Computer Integrated Manufacturing (v3, n3/4, 1990), pp196-205. 15. S.-Y.D. Wu and R.A. Wysk, "An Application of Discrete-event Simulation to On-line Control and Scheduling in Flexible Manufacturing," International Journal of Production Research (v27, n9, 1989), pp1603-1623. 16. C.M. Harmonosky and S.F. Robohn, "Real-time Scheduling in Computer Integrated Manufacturing: A Review of Recent Research," International Journal of Computer Integrated Manufacturing (v4, n6, 1991), pp331-340. 17. S.S. Panwalkar and W. Iskander, "A Survey of Scheduling Rules," Operations Research (v23, n5, 1977), pp961-973. 18. J.H. Blackstone, Jr., D.T. Phillips, and G.L. Hogg, "A Stateof-the-art Survey of Dispatching Rules for Manufacturing Job Shop Operations," International Journal of Production Research (v20, nl, 1982), pp27-45. 19. R.S. Russell, E.M. Dar-El, and B.W. Taylor III, "A Comparative Analysis of the COVERT Job Sequencing Rule Using Various Shop Performance Measures," International Journal of Production Research (v25, nl0, 1987), pp1523-1540. 20. A.P.J. Vepsalainen and T.E. Morton, "Priority Rules for Job Shops with Weighted Tardiness Costs," Management Science (v33, n8, 1987), pp1035-1047. 21. Y.-D. Kim, "A comparison of Dispatching Rules for Job Shops with Multiple Identical Jobs and Alternative Routings," International Journal of Production Research (v28, n5, 1990), pp953-962. 22. R. Ramasesh, "Dynamic Job Shop Scheduling: A Survey of Simulation Studies," OMEGA, The International Journal of Management Science (v18, nl, 1990), pp43-57.

Acknowledgment We thank Professor B.K. Choi for his ideas of using simulation in scheduling and control problems, which initiated this research. This research was supported in part by a Korean Ministry of Science and Technology grant to the Korea Advanced Institute of Science and Technology.

References 1. K.E. Stecke, "Design, Planning, Scheduling, and Control Problems of Flexible Manufacturing Systems," Annals of Operations Research (v3, 1985), pp3-12. 2 M. Montazeri and L.N. Van Wassenhove, "Analysis of Scheduling Rules for an FMS," International Journal of Production Research (v28, n4, 1990), pp785-802. 3. M. Yamamoto and S.Y. Nof, "Scheduling/Rescheduling in the Manufacturing Operating System Environment," International Journal of Production Research (v23, n4, 1985), pp705-722. 4. L.K. Church and R. Uzsoy, "Analysis of Periodic and Eventdriven Rescheduling Policies in Dynamic Shops," International Journal of Computer Integrated Manufacturing (v5, n3, 1992), pp153-163. 5. N. Raman, R.V. Rachamadugu, and F.B. Talbot, "Real-time Scheduling of an Automated Manufacturing Center," European Journal of Operational Research (v40, n2, 1989), pp222-242.

Authors' Biographies Min Hee Kim earned her BS at Korea University, Seoul, and MS at the Korea Advanced Institute of Science and Technology, both in industrial engineering. Currently she works for Samsung Data Systems Co., Ltd. Yeong-Dae Kim is an associate professor in the Department of Industrial Engineering at the Korea Advanced Institute of Science and Technology (KAIST). He received his BS from Seoul National University, MS from KAIST, both in industrial engineering, and his PhD in industrial and operations engineering from the University of Michigan. He is interested in the research areas of operations scheduling, production planning in flexible manufacturing systems, and production and inventory management.

93