Fair path selection during simulation of decision nodes

An apparatus, method, and computer program product to simulate a business process model wherein a decision node may be modeled using a fair selection process or a random selection process, as selected by an end user. The fair selection process may provide a distribution of invocations among the outgoing paths of a decision node that substantially matches the probabilities assigned to those paths. A fair selection process may do this independent of the number of invocations of the decision node. A random selection process may provide random invocations among the outgoing paths of a decision node according the probabilities assigned to those paths.

BACKGROUND

1. Field of the Invention

This invention relates to process modeling and simulation and more particularly to simulating decision nodes in a process model.

2. Background of the Invention

Process modeling and simulation relates to the modeling and simulation of dynamic or static systems. Process models generally specify one or more tasks or activities of a process and the relationship between the different tasks or activities. As part of a process model, one or more events or conditions leading to the transition from one task or activity to the next may be specified. Such events or conditions may include sufficient detail to support simulation of the process module. During simulation of a process model, one or more scenarios or inputs may be applied to the process module to determine likely outcomes.

Certain process models may include one or more decision nodes. A decision node typically handles decision branching in a scenario or process model. Decision nodes are typically used when there are multiple possible outcomes. In general, each branch or outgoing path of a decision node may have a condition. The flow through a decision node may be directed to the path whose condition evaluates to true. Current methods for simulating decision nodes do not meet the needs of all end users.

In view of the foregoing, what is needed is an apparatus and method providing an end user greater control and choice when simulating the decision nodes of a process model.

SUMMARY

The invention has been developed in response to the present state of the art and, in particular, in response to the problems and needs in the art that have not yet been fully solved by currently available apparatus and methods. Accordingly, the invention has been developed to provide apparatus and methods for providing a fair selection process during simulation of a decision node.

Consistent with the foregoing, an apparatus and method to provide fair selection during simulation of a decision node is disclosed herein. According to one embodiment of the invention, such a method may include identifying a computer comprising a processor and a memory device operably connected to the processor. The memory device may store a simulation module executable by the processor. The memory device may also store a process model. The process model may include a decision node having two or more outgoing paths and a probability profile specifying a probability for each outgoing path.

The simulation module may receive a command to start a simulation session. During the simulation session, the decision node may be invoked multiple times. Each time the decision node is invoked, it may be simulated using a fair selection process. The fair selection process may provide a distribution of invocations among the outgoing paths of the decision node that substantially matches the probability profile. A fair selection process may do this independent of the number of times the decision node is invoked. Accordingly, even when a decision node is invoked a relatively few number of times, the distribution of invocations may substantially match the probability profile.

In selected embodiments, a fair selection process may comprise a series of steps executed by the simulation module each time the decision node is invoked. This series of steps may include indentifying both the present total number of invocations for each outgoing path and the present total number of invocations for the decision node (including the present invocation) since the start of the simulation session. Using this information, a delta may be calculated for each path of the outgoing paths.

In certain embodiments, a delta may equal the probability of a path (comprising a number between zero and one) times the total number of invocations for the decision node minus the total number of invocations for the path. The series of steps of a fair selection process may further include identifying an outgoing path having a delta that is greater than or equal to the deltas of the other outgoing paths. Once identified, that path may be invoked.

In other embodiments, a delta may indicate how much an actual number of invocations of an outgoing path is less than a probable number of invocations of the path, based on the probability assigned thereto. For example, a delta may equal the probability of an outgoing path (a number between zero and one) times a summation of the invocations of the outgoing paths minus the number of invocations of the outgoing path. In such embodiments, the series of steps of a fair selection process may further include identifying and invoking an outgoing path having a delta that is both greater than or equal to 0.5 and greater than or equal to the deltas of the other outgoing paths.

Alternatively, it may be determined that there are multiple outgoing paths that share the greatest delta or that no outgoing path has a delta that is greater than or equal to 0.5. In such situations, the series of steps may include invoking randomly among the outgoing paths, according to the probability profile. This may be done by invoking randomly among all of the outgoing paths or among only those outgoing paths that share the greatest delta.

In another embodiment of the invention, an alternative method for simulating a business process may include providing, by a simulation module running on a computer, at least two processes for simulating a decision node. The at least two processes may include a random selection process and a fair selection process.

While the simulation module is running on the computer, the simulation module may receive an input specifying that a decision node be simulated using the fair selection process and a command to start a simulation session. During the simulation session, the simulation module may invoke the decision node multiple times. Each time the decision node is invoked, it may be simulated using the fair selection process. The fair selection process may provide a distribution of invocations among the outgoing paths of the decision node that substantially matches the probability profile, independent of the number of times the decision node is invoked.

Alternatively, while the simulation module is running on the computer, the simulation module may receive an input specifying that a decision node be simulated using the random selection process and a command to start a simulation session. During the simulation session, the simulation module may invoke the decision node a number of times. Each time the decision node is invoked, it may be simulated using the random selection process. The random selection process may invoke randomly among the outgoing paths according to the probability profile.

In still another embodiment of the invention, an apparatus for simulating a business process may include a processor, a memory device operably connected to the processor, and a computer program stored on the memory device and executable by the processor. The computer program may provide simulation of a process model comprising a decision node having at least two outgoing paths extending downstream therefrom and a probability profile specifying a probability for each path. The computer program may include a fair selection module, a random selection module, and a user interface.

The fair selection module may be programmed to implement a fair selection process providing a distribution of invocations among the outgoing paths that substantially matches the probability profile, independent of the number of invocations of the decision node. The random selection module may be programmed to implement a random selection process providing random invocations among the at least two paths according to the probability profile. The user interface may be programmed to receive input from an end user indicating whether the fair selection process or the random selection process is to be used in simulating the decision node.

DETAILED DESCRIPTION

Any combination of one or more computer-usable or computer-readable medium(s) may be utilized. The computer-usable or computer-readable medium may be, for example but not limited to, an electronic, magnetic, optical, electromagnetic, infrared, or semiconductor system, apparatus, device, or propagation medium. More specific examples (a non-exhaustive list) of the computer-readable medium may include the following: an electrical connection having one or more wires, a portable computer diskette, a hard disk, a random access memory (RAM) device, a read-only memory (ROM) device, an erasable programmable read-only memory (EPROM or Flash memory) device, an optical fiber, a portable compact disc read-only memory (CDROM), an optical storage device, transmission media such as those supporting the Internet or an intranet, or a magnetic storage device. Note that the computer-usable or computer-readable medium could even be paper or another suitable medium upon which the program is printed, as the program can be electronically captured, via, for instance, optical scanning of the paper or other medium, then compiled, interpreted, or otherwise processed in a suitable manner, if necessary, and then stored in a computer memory.

In the context of this document, a computer-usable or computer-readable medium may be any medium that can contain, store, communicate, propagate, or transport the program for use by or in connection with the instruction execution system, apparatus, or device. The computer-usable medium may include a propagated data signal with the computer-usable program code embodied therewith, either in baseband or as part of a carrier wave. The computer-usable program code may be transmitted using any appropriate medium, including but not limited to wireless, wireline, optical fiber cable, radio frequency (RF), etc.

Referring toFIG. 1, in selected embodiments, an apparatus10may include one or more nodes12, computers12, clients12, or the like. A node12may include a processor14or central processing unit (CPU)14. A node12may also include a storage device16. One or more storage devices16may be operably connected to a processor14and may include a secondary storage device18(e.g., a hard drive) or other non-volatile storage device18, read-only memory (ROM)20, random access memory (RAM)22, or the like. These components14,16,18,20,22may exist in a single node12or may be distributed across multiple nodes12.

In selected embodiments, a node12may include one or more input devices24such as a keyboard, mouse, touch screen, scanner, memory device, communication line, and the like. A node12may also include one or more output devices26such as a monitor, printer, data storage device, and the like. A node12may further include a network card28, port30, or the like to facilitate communication through a network32. Internally, one or more busses34may operably interconnect the various components14,16,24,26,28,30of a node12to provide communication therebetween. Each node12of an apparatus10may contain more or less of the components described hereinabove.

An apparatus10may further include one or more servers36and the like to serve files, data, applications, etc. to nodes12connected thereto. An apparatus10may also include one or more routers38and the like. Accordingly, one network32may be connected to other networks40via one or more routers38.

Referring toFIG. 2, a process model may be an abstract description of a process (e.g., a business process). Process models generally specify one or more tasks or activities of a process and the relationship between the different tasks or activities. Models may be expressed according to a specific format. Exemplary formats include Activity Decision Flow (ADF), Unified Modeling Language (UML) activity diagrams, Business Process Execution Language (BPEL), and the like.

As part of a process model, one or more events or conditions leading to the transition from one task or activity to the next may be specified. Such detail may support simulation of the process model. During simulation, a process model may be analyzed to determine likely outcomes, bottlenecks, efficiencies, problems, and the like for the process being modeled.

Process modeling and simulation may be applied to dynamic or static systems, which can include, but are not limited to, enterprise management systems, engineering systems, networked information technology systems, utility systems, utility computing systems, autonomic computing systems, on-demand systems, electric power grids, biological systems, medical systems, weather systems, financial market systems, and business process systems. Such systems can be modeled and simulated for a variety of purposes including monitoring, analysis, control, design, simulation, and management.

In selected embodiments, a node12may be configured to store and run an application42providing modeling, simulation, or a combination thereof for processes such as business processes. In certain embodiments, an application42providing such functionality may include a user interface44, drafting module46, simulation module48, and other modules50as desired or necessary. A user interface44may support communication between an end user and an application42. A drafting module46may support importing, creating, editing, and the like of one or more process models. A simulation module48may support simulation of a process model.

In selected embodiments, a simulation module48may include a fair selection module52, random selection module54, and other modules56as desired or necessary. A fair selection module52may support simulation using a fair selection process. In contrast, a random selection module54may support simulation using a random selection process.

Referring toFIG. 3, a process model58may provide a set of nodes60connected by flow of control, data, product, people, or the like. A core set of nodes60may include task, decision, merge, fork, and join nodes. Task nodes may be nodes60where actions are performed. Decision nodes60amay be nodes60where decisions are made and the flow of the process branches into distinct paths62. Merge nodes may be nodes60where branches62or paths62are brought together. Fork nodes may be nodes60where the flow of a process forks into multiple, parallel, paths62. Join nodes may be nodes60where the parallel flows of control from a previous fork node are brought together.

A decision node60amay have two or more outgoing paths62. In the illustrated embodiment, two decision nodes60ahave two outgoing paths62a,62b,62c,62d, while a third decision node60ahas three outgoing paths62e,62f,62g. Other arrangements of decision nodes60aand numbers of outgoing paths62are possible and within the scope of the present invention.

In selected embodiments, a process model58may include a probability profile. A probability profile may include individual probabilities assigned to each of the outgoing paths62of the decision nodes60awithin a process model58. The probabilities assigned may vary as desired or necessary to provide the simulation desired. In general, the sum of the probabilities for the outgoing paths62of a particular decision node60amay equal 100 percent. However, the probabilities for the individual outgoing paths need not follow any particular pattern. For example, for one decision node60a, the outgoing paths62a,62bmay have equal probabilities (50 percent each) assigned thereto. For other decision nodes60a, the outgoing paths62c,62dmay have unequal probabilities (e.g., 59 percent and 41 percent) assigned thereto. For still other decision nodes60a, the outgoing paths62e,62f,62gmay have still other probability arrangements (e.g., 49 percent, 49 percent, and 2 percent).

Referring toFIG. 4, during simulation, an application42may invoke various nodes60, paths62, or the like. An invocation may include an indication stored by a computer12that a particular node60has been reached or that a particular path62has been followed. Accordingly, a series of invocations may define the flow of data, control, product, people, or the like through a process model58.

For example, in one embodiment, a process model58(or a subset thereof) may model the flow of patients within a hospital. In the illustrated embodiment, a process model58includes a node60arepresenting patient arrival. Of the patients arriving, a portion may arrive by ambulance. Accordingly, the process model58may include a node60arepresenting arrival by ambulance. After arrival by ambulance, patients may move on to a nurse exam or beside registration. Thus, the process model may include nodes60for nurse exam and bedside registration. In the illustrated embodiment, the probabilities for the two outgoing paths62of the arrive by ambulance node60aare set to 50 percent. However, as set forth above, other probabilities and probability profiles are also possible.

During simulation of the illustrated process model58, only a portion of the invocations of the patient arrival node60awill result in invocations of the arrive by ambulance node60a. Similarly, only a portion of the invocations of the arrive by ambulance node60awill result in invocations of the nurse exam node60, etc. Thus, by recording invocations of the various nodes60, paths62, or both, an application42may collect data on how a process being modeled would perform in the real world.

Referring toFIG. 5, while continuing to refer generally toFIG. 4, in selected embodiments, an application42may support a method64for generating a process model58. The method64may include the steps of creating66nodes60and defining68the paths62connecting the nodes60. The method64may also include defining70the probabilities for the outgoing paths62of the decision nodes60a. Additionally, in selected embodiments, the method64may include a choice72of whether to simulate a decision node60ausing a random selection process or a fair selection process. This choice72may be presented on a node-by-node basis, globally across a process model58, for a subset of a process model58, or some combination thereof. Once the selection process is chosen72, the method64may then simulate the decision node60ain accordance therewith (i.e., using74the random selection process or using76the fair selection process, as specified).

A random selection process may provide random invocations among the outgoing paths62of a decision node60aaccording to the probability profile assigned thereto. Accordingly, should a user choose72to simulate the illustrated arrive by ambulance node60ausing74a random selection process, the end result of whether a patient flows to a nurse exam node60or a bedside registration node60may be determined like the flip of a coin. Thus, with five invocations of the arrive by ambulance node60a, there are six possible ratios for invocations of the nurse exam node60versus invocations of the bedside registration node60(i.e., 0:5, 1:4, 2:3, 3:2, 4:1, and 5:0). Using a random selection process, a high number of invocations of the arrive by ambulance node60aare required to “guarantee” that the distribution of invocations among the outgoing paths62will more or less reflect the assigned probabilities.

In contrast, by using76a fair selection process, an end user may be sure to receive a distribution of invocations among the outgoing paths62of a decision node60athat substantially matches the probabilities assigned to those outgoing paths62. Using76a fair selection process, an end user may receive such a “fair” distribution without regard to (independent of) the number of times a decision node60ais invoked.

In process model simulation, invocations are not typically split. For example, it may not be logical to split an invocation at the arrive by ambulance node60, sending some portion of a patient to a nurse exam60and the remaining portion of the patient to a bedside registration60. Thus, invocations may be counted in whole numbers.

Counting in whole numbers may influence what may be considered a substantial match to the probabilities assigned to the outgoing paths62of a decision node60a. For example, an end user may choose72to simulate the illustrated arrive by ambulance node60ausing76the fair simulation process. However, during a simulation session, the arrive by ambulance node60amay only be invoked three times. In such a situation, there is no way to use whole numbers and reflect the 50 percent probability assigned to each outgoing path62. Accordingly, the best a fair simulation process may do is distribute invocations amount the paths62such that two invocations are directed to one path62and one invocation is directed to the other path62. Under such circumstances, a two-to-one distribution may be considered a substantial match to the 50 percent probabilities assigned.

Referring toFIG. 6, a fair selection process78may use any of a number of mathematical methodologies to distribute invocations among the outgoing paths62of a decision node60a. Some mathematical methodologies may be more complex than others. Moreover, different mathematical methodologies may produce different levels of adherence to the assigned probabilities.

In selected embodiments, a fair selection process78may include the steps of identifying80the total number of invocations of a decision node60aand identifying82the total number of invocations of each outgoing path62of the decision node60a. With this information, the process78may include calculating84a delta for each outgoing path62of the decision node60a.

A delta may be a number characterizing the distance between the number of invocations a path62has actually received and an expected (or most probable) number of invocations for the path62. For example, if a decision node60awith two outgoing paths62having respective probabilities of 30 percent and 70 percent were invoked ten times, then the expected or probable number of invocations would be 3 and 7, respectively.

A delta may be calculated in any suitable manner. In one embodiment, a delta may be equal to the probability of a path62times the number of invocations of the node60aminus the number of invocations of the path62. In such an embodiment, the probability of the path62may include a number between zero and one (i.e., be equal to the probability in percent format divided by 100). Additionally, the number of invocations of the node60amay include the present invocation. Accordingly, the number of invocations of the node60amay be equal to one more than a summation of the invocations of the outgoing paths62.

In an alternative embodiment, a delta may indicate how much an actual number of invocations of an outgoing path62is less than a probable number of invocations of the outgoing path62. That is, a delta may be equal to the probability of a path62times a summation of the invocations of the outgoing paths62minus the number of invocations of the path62. In such an embodiment, the probability of the path62may again include a number between zero and one (i.e., be equal to the probability in percent format divided by 100).

The manner in which a delta is calculated84may affect how it is used in the subsequent steps of a fair selection process78. For example, after calculating84a delta for each outgoing path62using the first method illustrated (Method A), a fair selection process78may directly invoke86an outgoing path62having a delta that is greater than or equal to the deltas of the other outgoing paths62. Alternatively, after calculating84a delta for each outgoing path62using the second method illustrated (Method B), a fair selection process78may directly invoke86an outgoing path62having a delta that is both greater than 0.5 and greater than or equal to the deltas of the other outgoing paths62.

In selected embodiments, rather than directly invoking a particular path62after calculating84a delta for each outgoing path, a fair selection process78may determine88whether multiple outgoing paths62share the greatest delta. If there is not a shared greatest delta, the outgoing path62with the greatest delta (or greatest delta over 0.5) may be invoked86. However, if multiple paths62share the greatest delta, a path62may be invoked90at random according to the assigned probabilities. In selected embodiments, any outgoing path62corresponding to the node60amay be randomly invoked90. In other embodiments, only those outgoing paths62sharing the greatest delta may be randomly invoked90.