Short Term Scheduling Using Discrete Event Simulation

October 1, 1996

Submitted to Southwestern Bell - Technology Resources, Inc.

Submitted by Jeffrey S. Smith and Brett A. Peters

Department of Industrial Engineering

Texas A&M University

College Station, TX 77843-3131

 

409/845–4335; 409/845–3574

Fax: 409/845–7079

jsmith@tamu.edu; bpeters@tamu.edu

 

Purpose and Objectives

The purpose of this project is to describe the current and future uses of discrete event simulation as potentially applicable to TRI’s clients. TRI is charged with introducing new technology that will potentially have a significant impact on TRI’s Southwestern Bell clients over the next five years. That is to say, TRI is responsible for monitoring the trends in technology and forecasting the significant tools that will become available over the next several years. This report describes the use of discrete event simulation in this light.

Background

Current Uses of Discrete Event Simulation

Simulation is generally used as an analysis and decision-making tool in three classes of problems: 1) design problems, 2) planning problems, and 3) operational problems. Design problems generally deal with system configuration issues and simulation tools are primarily used to evaluate candidate designs to aide in the design selection process. Planning problems generally deal with how existing or proposed systems will be used. Operational problems relate to the actual use of the system (Pritsker, 1992). Traditionally, the vast majority of simulation applications have dealt with system design and/or planing problems.

The primary reason for the emphasis on design and planning problems is that the computer power required to run operational level simulations has previously not been readily available. The lack of computer power manifested itself in two ways. First and foremost, the simulation tools did not lend themselves to the development of complex simulations. That is, the simulation languages were little more that traditional programming languages with some pre-programmed "simulation functionality" built-in. As a result, simulation developers were required to understand not only the modeling and statistical material required to successfully simulate a complex system, but also had to be expert programmers in order to translate the system specifications into viable simulation models.

The second manifestation of the lack of computer power was in the length of time required to actually run the simulations long enough to get meaningful (and valid) results.

With the advent of more powerful personal computers (PCs), the lack of sufficient computational power is becoming less and less of a factor in the development and use of discrete event simulations. The wide-spread availability of powerful PCs has served to reduce the significance of both of the problems described above. That is, simulation vendors are able to exploit the power of today’s PCs in order to provide sophisticated tools for the development and maintenance of complex simulation models, as well as for the analysis of the output of these models. Furthermore, once the models are developed, the PC’s inherent power has significantly reduced the length of time required to run the models.

As computers continue to come down in price while gaining computational power, these trends toward more and more complex systems to assist in building and maintaining models as well as reductions in simulation run time, should continue.

Discrete-Event Simulation Vendors

The number of discrete event vendors and products continues to grow at a high rate. Table 1 provides a comprehensive list of simulation vendor and products as of 1995 (IIE Solutions, 1995).

Short-Interval Scheduling Applications

Problem Description

In simple terms, short-interval scheduling involves developing schedules for relatively short planning horizons, and rescheduling when events that invalidate the existing schedule occur. Short-interval scheduling attempts to adapt to the dynamics of the system by developing a short-term plan that is based on the current system status. As the system status changes, the schedule is updated to reflect these changes. Thus, the short-interval scheduling problem must be solved quickly in order to adapt to changes in real time.

Current Approaches

Most current approaches to short-interval scheduling rely on simple rules for making decisions. The status of the system is observed and then a simple rule is invoked to determine what to do next. These rules could be of the form of specifying priorities for different types of tasks, e.g., always do an emergency commercial repair before a new residential installation, of specifying priorities for different jobs of the same type, e.g., ordering jobs based on the time promised to the customer, or of if … then type logic.

While these rules consider the current system status when making decisions, e.g., what orders are pending, the rules themselves are static. That is, the rules do not adapt to the dynamics of the system. It is conceivable that the "best" operating procedure will change as the system status changes, e.g., operating procedures after an emergency storm might be very different than after several days of good weather. While certain situations, like the weather, can be anticipated and built into the rules, many other situations that dramatically impact performance can not be assessed a priori. Furthermore, the number of combinations of different "situations" will be enormous for any moderate size system. Therefore, an adaptable, dynamic short-interval scheduling system is needed to react to the ever-changing system status.

New Directions/Enabling Technology

The following sections describe some of the most significant advances in simulation technology over the past several years. The focus of these sections is on those advances that are expected to impact the uses of simulation over the next several years.

Interactive Tool

One of the trends that is directly attributable to the increases in computational power readily available on the desktop is the increase in the interaction between the simulation user and the simulation during runtime and the simulation development environment during the simulation development/maintenance. As recently as the late 1980s, most simulations were written and run in a manner very similar to traditional programming languages. That is, they were generally written using only a text editor, they were compiled using the simulation language compiler, and they were executed as stand-alone programs. These programs generated output which was written to files and the data in these files was analyzed using a separate analysis package.

Today’s simulation packages, on the other hand, generally include fully interactive development environments that assist the user during the development and running of the simulation. A significant number of current simulation packages also include input and output data analysis functionality built-in to the simulation environment.

Incorporation of Computer Graphics

Computer graphics now play a significant role in the development, validation, verification, and marketing of discrete event simulation models. Current simulation environments allow users to build complete simulation models by "dragging and dropping" icons representing simulation constructs on a computer screen. For example, Figure xx shows the SIMAN code for a simple simulation that models random arrivals of parts to a machine, the queuing of these parts in front of the machine, the processing on the machine, and the departure of the parts from the system. Figure xx shows the exact same simulation in the Arena simulation modeling environment (the successor to SIMAN from Systems Modeling Corp.) which includes a graphics-based "drag and drop" interface.

While the incorporation of computer graphics into the simulation development environments has had a significant impact on the use of simulation, the incorporation of animation to allow users to "watch" the model execute has brought simulation to the forefront of system analysis tools.

Hybrid Analytical/Simulation Tools

While simulation is recognized as a powerful tool for accurately modeling a system and predicting its performance over the long-term, it has encountered some obstacles as a short-term planning tool. First, simulations have been historically designed to predict long-term steady-state behavior. Therefore, a different tool set and methodology is needed when estimating performance over the near term from a given system status. The issue of how to deal with the stochastic nature of the system must be resolved. We are no longer interested in "averaging out" the randomness in the system’s behavior, but instead must account for and/or react to it on a real-time basis. Second, simulation has traditionally required a long run time in order to get statistically valid results. While the increases in computer power have helped to shrink this time, further advances are still necessary in order for simulation to become a truly real-time planning tool.

To overcome some of these difficulties, several researchers have investigated hybrid tools that combine analytical tools (e.g., queueing models) with simulation. These hybrid models (or fast simulations) are used to speed-up the simulation process. They rely on the underlying system structure to increase the simulation speed.

While these tools hold promise, much further investigation and research is required. Several issues remain unresolved including the applicability of these tools for short-interval scheduling applications, the determination of how to divide the model between analytical tools and simulation, and the interpretation and understanding of short-term results generated by the hybrid tools. Certainly, this area deserves attention to see how it progresses and to determine where opportunities exist to exploit this technology.

SIMAN Model File

; Model statements for module: Arrive 1

CREATE, 1,0:expo(10):MARK(ArriveTime);

STATION, Arrive 1;

ASSIGN: Picture=Default;

DELAY: 0.;

ROUTE: 0.,Server 1;

; Model statements for module: Server 1

STATION, Server 1;

DELAY: 0.;

QUEUE, Server 1_R_Q:MARK(QueueTime);

SEIZE, 1:Server 1_R,1;

TALLY: Server 1_R_Q Queue Time,INT(QueueTime),1;

DELAY: expo(8);

RELEASE: Server 1_R,1;

DELAY: 0.;

ROUTE: 0.,Depart 1;

; Model statements for module: Depart 1

STATION, Depart 1;

DELAY: 0.;

COUNT: Depart 1_C,1;

TALLY: Depart 1_Ta,Interval(ArriveTime),1;

DISPOSE;

SIMAN Experiment File

PROJECT, Example Simulation,Jeffrey S. Smith,9/25/96;

ATTRIBUTES: ArriveTime:

QueueTime;

QUEUES: Server 1_R_Q,FIFO;

PICTURES: Default;

RESOURCES: Server 1_R,Capacity(1,),;

STATIONS: Arrive 1:

Depart 1:

Server 1;

COUNTERS: Depart 1_C;

TALLIES: Depart 1_Ta:

Server 1_R_Q Queue Time;

DSTATS: NQ(Server 1_R_Q),# in Server 1_R_Q:

MR(Server 1_R),Server 1_R Available:

NR(Server 1_R),Server 1_R Busy;

REPLICATE, 1,0.0,4800,Yes,Yes;

Figure 1. Example SIMAN simulation code.

Figure 2. Example Arena simulation

Reusable Simulation Modules/Objects

Simulation users are becoming more interested in developing reusable simulations and simulation modules. Arena’s templates and object-oriented simulation systems (e.g., Simple++) are examples of relatively new simulation technology that are directed at users interested in extending the simulation language/systems.

These systems attempt to exploit the similarity among different simulation models by creating reusable modules or objects that model a particular subsystem or perform a particular decision making function. These modules are generic in that they contain the "code" for a particular model, but are made specific based on the particular data from a given situation. These modules allow a simulation model to be easily constructed and/or modified as the system changes. They allow relatively complex decision making logic to be encapsulated in a reusable package and incorporated into a simulation model. This concept eliminates the need to have decision making logic "hard-coded" into the simulation, which is difficult to change and modify. Therefore, simulations built using modules or objects will be more amenable to the manipulation required in short-interval scheduling applications.

Use of External Data Sources

One of the most significant differences between traditional design-oriented simulations and operational planning simulations is the need for significant amounts of data at run time. While design-oriented simulations can require large amounts of data, this data is generally gathered prior to the model development stage and certainly before the model is run. Simulations used for operational decision making (e.g., short interval scheduling) generally incorporate the current state of the system into each run and, therefore, require more on-going access to current data. Consequently, in this environment, the structure of the data is known during the development of the simulation, but the actual data changes often on a day-to-day basis.

In response to these needs, commercial simulation systems are trying to simplify access to external data. The external data can be provided through a variety of methods such as simple data files, spreadsheets, proprietary databases, and commercial database servers. The following sections discuss external data access in the context of building and modifying models, and in the context of running models.

Accessing External Data During Model Building/Maintenance

The use of external data sources for model building/maintenance is typified by Arena’s module data input/export functions. These functions allow the user to read module data into Arena modules from external data sources and to write module data from Arena to external data sources. Arena accomplishes these tasks by using the Open Database Connectivity (ODBC) standard for data access methods. ODBC was originally developed by Microsoft and allows programs to access data without having to know the specific data/file format.

Reading model data during simulation development can simplify simulation development and maintenance in certain cases where resource capacities change from one simulation run to another. For example, when workforce levels change frequently and/or when machines or other resources are frequently reconfigured, it is often easier to use model read functionality to change the underlying model than to create ultimately flexible simulations.

Accessing External Data During Model Running

While the ability to construct/modify models using data from external data sources can be useful in some environments, the ability to access to external data sources during simulation runs will have more impact on the simulation-based operational planning domain. As described above, continuous access to system state information is a requirement for effective short interval scheduling. That is, when using simulation as an operational planning tool, it is imperative that the simulation model’s system state be the same as the actual system’s state. Due to the dynamic nature of manufacturing systems, this system state synchronization is only possible through communication. Without frequent synchronization, the actual and simulated system states will inevitably diverge. Synchronization can be performed through communication with shop floor control systems, manufacturing execution systems (MES), and human operators/managers.

Smith et al., (1994) describe a simulation-based shop floor control system in which the simulation makes decisions and interacts directly with an execution system to provide direction and synchronize the system state. This system uses an interprocess communication (IPC) mechanism implemented as two message queues, a task initiation queue (TIQ) and task completion queue (TCQ). Figure 3 illustrates this structure. The simulation specifies tasks to be performed by putting them in the TIQ. The execution system monitors the TIQ, removing and performing tasks as they appear in the queue. Upon the successful completion of a task, the execution system places a "task complete" message in the TCQ. This task initiation/task completion structure provides the synchronization between the simulation system state and the actual system state. The external data access provided by the system described by Smith et al. (1994) is based on interprocess communication using the TCP/IP network protocols. Furthermore, the described technology is now available as an add-on to the commercial version of Arena.

Figure 3. Example simulation-based control system.

A related but somewhat different capability is the ability to easily modify model parameter data based on external data sources as the simulation is running. Updating the expected processing time for an item based on the current state of the process, and updating the expected number of defective items based on immediately preceding inspections are two examples where this ability could be used. Incorporating data from external sources into decision making is also envisioned. For example, routing delivery or service vehicles based on current road/traffic conditions is possible given real-time access to the traffic data.

Data exchange standards represent the fundamental requirement for these dynamic data access capabilities. That is, required data is generated and stored by a wide variety of systems (e.g., shop floor control systems, manufacturing execution systems, etc.) and, developing proprietary interfaces to each of these individual systems is not cost effective. Another potential solution is to have an intermediate data interchange system that essentially converts from one exchange format to another. However, this is also a difficult task and requires significant programming/system development expertise.

The good news is that data exchange standards such as Microsoft’s Open Database Connectivity (ODBC) model and OLE Automation are gaining momentum as industry-wide standards. As a result, more and more companies are

Simulation-Based Scheduling

Commercial Finite Capacity Scheduling Solutions

Table 1 lists several simulation vendors. Most of these simulation systems were developed for design applications, i.e., long-term, predictive analysis. Several other commercial packages focus on short-term, finite capacity scheduling. These products include AutoSched (AutoSimulations), Factor (Prisker Corp.), PROVISA (AT&T Istel), and Preactor (Systems Modeling Corp.). Although the implementation differs between products, they each try to determine a schedule of near-term activities that is capacity feasible. That is, they assign activities to resources considering some capacity constraint on each resource. They typically provide a schedule, e.g., a Gantt chart, of activities to be performed by each resource. Furthermore, most of these products are aimed at manufacturing environments, although they could be applied in other situations as well.

Most of these products assume that the system is static and that the requirements are known. They do not allow for explicit modeling of uncertainty in the data or dynamic changes in the system status. Furthermore, they tend to employ some set of static rules for making decisions, as discussed in Section 3.2. Therefore, they suffer from an inability to dynamically react to changing conditions.

In addition, they are designed as interactive tools to be used by a human decision maker. As such, they are intended to aid the decision making process. They are not designed for an on-line, real-time application where the scheduler is linked directly to the control system to dispatch tasks and monitor system performance. Thus, a human decision maker is needed to control execution of the scheduling system and to interpret the results. Significant translation is often needed to convert the resulting "schedule" into an execution plan that can be given to the control system.

On-going Research

Several on-going efforts are addressing this area. System’s Modeling corporation has plans to develop a simulation-based version of Preactor. The intent is to link the Preactor scheduling system with the Arena simulation system to create a dynamic simulation-based scheduling system. This product is still in development and isn’t currently commercially available. However, it represents one attempt at developing commercial solutions.

In the academic community, there is also research directed at developing viable simulation-based scheduling systems. Specifically, several projects in this area are underway at Texas A&M. We are investigating the possibility of using simulation to overcome the difficulties of current scheduling systems. Building on the technologies outlined in Section 4, we are investigating the possibility of creating a simulation-based scheduling system that will be able to monitor the system status and make decisions in real-time. It will have the capability of interacting with external databases to obtain information as well as interacting with the control system to assign tasks and receive feedback about system status and performance. The simulation system will have the ability to "look ahead" by simulating the expected performance of the system in the near future given the current status of the system. The best decision, or decision-making policy, based on these look-ahead simulations can be implemented directly in the system. The idea is to have a scheduling system that is able to provide real-time responses to dynamic changes in the system status.

Conclusions

There have been few complete applications of short-term scheduling systems based on simulation. Simulation has traditionally been used for design applications where long-term analysis was required or for operational planning where a set of decision rules were tested prior to implementation in a control system. However, the stage seems set for significant advances in the use of simulation in the short-interval scheduling area. This report has surveyed this area and highlighted some of the enabling technologies that are currently (or will be in the near future) available. These technologies should allow next generation simulation-based scheduling systems to be developed. These systems hold great promise for improving the performance of systems operating in highly variable environments, which is crucial for success in today’s (and tomorrow’s) competitive marketplace.

References

Pritsker, A.B., "Simulation: The Premier Technique of Industrial Engineering," IE Magazine, Vol. 24, No. 7, July 1992, pp. 25-26.

Smith, J. S., Wysk, R. A., Sturrock, D., Ramaswamy, S., Smith, G., and Joshi S. B., "Discrete Event Simulation for Shop Floor Control," Proceedings of the 1994 Winter Simulation Conference, December, 1994, Lake Buena Vista, FL, pp. 962-969.

IIE Solutions, May 1995.