Package jline.api.wfn

Class WorkflowNet

java.lang.Object
jline.lang.Model
jline.api.wfn.WorkflowNet
All Implemented Interfaces:
Serializable, Copyable
public class WorkflowNet extends Model
A Workflow Net (WF-net) model for performance analysis.

A WF-net (van der Aalst, 1997/98) is a Petri net with exactly one source place i (no incoming arcs), exactly one sink place o (no outgoing arcs), and every place and transition on a directed path from i to o. A case is one token put in i; it is complete when one token reaches o.

WorkflowNet does not have a solver of its own. It checks that the net is a WF-net and that it is sound, and then either analyses one case exactly or compiles the net into an ordinary Network:

  • validate(): structural WF-net conditions
  • checkSoundness(int): k-soundness on the reachability graph
  • getCycleTime(): exact phase-type law of the case duration of one case without contention (any sound net, PH timing)
  • getCycleTimeAnalysis(): moments, CDF, percentiles, expected firings per transition and expected token-time per place
  • getResourceLoads(double): per-resource load of an open stream of cases
  • toWorkflow(): equivalent Workflow, for block-structured nets
  • toNetwork("forkjoin"): fork-join queueing network, block-structured nets
  • toNetwork("spn"): stochastic Petri net with a case-counter place, any sound net
  • getCaseMetrics(NetworkSolver): case throughput, WIP, cycle time and resource utilisation from a solver of a compiled network

TIMING. A timed transition fires after a phase-type delay (Exp, Erlang, HyperExp, Coxian, Cox2, APH, PH) under race semantics with enabling memory: a transition disabled by a conflicting firing loses its progress. An immediate transition fires in zero time; among the enabled immediate transitions only those of the highest priority fire, chosen with probability proportional to their weights.

SEMANTICS OF THE TWO NETWORK TARGETS WITH MANY CASES. The fork-join target keeps case identity, since LINE joins only synchronise siblings of the same job. The SPN target uses uncoloured tokens, so an AND-join may pair tokens of different cases; its case-counter place gives the mean number of cases in the system and, by Little's law, the exact mean cycle time under that semantics. Percentiles are not available from it.

 WorkflowNet wfn = new WorkflowNet("SimpleWFN");
 WFNPlace i = wfn.addPlace("i");
 WFNPlace p = wfn.addPlace("p");
 WFNPlace o = wfn.addPlace("o");
 WFNTransition t1 = wfn.addTransition("Task1", new Exp(1.0));
 WFNTransition t2 = wfn.addTransition("Task2", new Exp(2.0));
 wfn.addArc(i, t1); wfn.addArc(t1, p);
 wfn.addArc(p, t2); wfn.addArc(t2, o);
 SoundnessReport report = wfn.checkSoundness();
 PH ph = wfn.getCycleTime();          // hypoexponential, mean 1.5

MATLAB twin: matlab/src/api/wfn/WorkflowNet.m.

See Also:

  • Field Details

    • RESERVED_PREFIX

      public static final String RESERVED_PREFIX
      Names prefixed so that compiled networks never collide with user names
      See Also:

  • Constructor Details

    • WorkflowNet

      public WorkflowNet(String name)
      Create a new WorkflowNet.
      Parameters:
      name - model name

  • Method Details

    • addPlace

      public WFNPlace addPlace(String name)
      Add a place without tokens.
      Parameters:
      name - place name
      Returns:
      the new place

    • addPlace

      public WFNPlace addPlace(String name, int initialMarking)
      Add a place.

      INITIALMARKING is informational: the analyses always start from k tokens in the source place, as WF-net soundness does.

      Parameters:
      name - place name
      initialMarking - initial token count
      Returns:
      the new place

    • addTransition

      public WFNTransition addTransition(String name)
      Add a timed transition firing after an Exp(1) delay.
      Parameters:
      name - transition name
      Returns:
      the new transition

    • addTransition

      public WFNTransition addTransition(String name, Distribution distribution)
      Add a transition; an Immediate distribution makes it immediate.
      Parameters:
      name - transition name
      distribution - firing-time distribution
      Returns:
      the new transition

    • addTransition

      public WFNTransition addTransition(String name, Distribution distribution, TimingStrategy timing, Integer servers, Integer priority, Double weight)
      Add a transition. A null argument takes its default, as an empty argument does in the MATLAB twin.
      Parameters:
      name - transition name
      distribution - firing-time distribution (default Exp(1)); an Immediate distribution makes the transition immediate
      timing - TimingStrategy.TIMED or TimingStrategy.IMMEDIATE
      servers - concurrent firings allowed (default WFNTransition.INFINITE_SERVERS, i.e. no contention unless a resource is assigned)
      priority - firing priority of an immediate transition (default 1)
      weight - firing weight of an immediate transition (default 1)
      Returns:
      the new transition

    • addArc

      public WFNArc addArc(WFNNode source, WFNNode target)
      Add an arc of weight 1.
      Parameters:
      source - place or transition of this net
      target - transition or place of this net
      Returns:
      the new arc

    • addArc

      public WFNArc addArc(String source, String target)
      Add an arc between elements named SOURCE and TARGET, weight 1.
      Parameters:
      source - name of a place or transition
      target - name of a transition or place
      Returns:
      the new arc

    • addArc

      public WFNArc addArc(String source, String target, int weight)
      Add an arc between elements named SOURCE and TARGET.
      Parameters:
      source - name of a place or transition
      target - name of a transition or place
      weight - positive integer weight
      Returns:
      the new arc

    • addArc

      public WFNArc addArc(WFNNode source, WFNNode target, int weight)
      Add an arc from a place to a transition or vice versa.
      Parameters:
      source - place or transition of this net
      target - transition or place of this net
      weight - positive integer weight
      Returns:
      the new arc

    • setSource

      public void setSource(WFNPlace place)
      Declare the source place (checked by validate). @param place a place of this net

    • setSource

      public void setSource(String name)
      Declare the source place by name (checked by validate). @param name place name

    • setSink

      public void setSink(WFNPlace place)
      Declare the sink place (checked by validate). @param place a place of this net

    • setSink

      public void setSink(String name)
      Declare the sink place by name (checked by validate). @param name place name

    • setResource

      public WFNResource setResource(WFNTransition transition, String name)
      As setResource(WFNTransition, String, Integer, SchedStrategy) with defaults.

    • setResource

      public WFNResource setResource(WFNTransition transition, String name, Integer servers)
      As setResource(WFNTransition, String, Integer, SchedStrategy) with default scheduling.

    • setResource

      public WFNResource setResource(String transition, String name)
      As setResource(WFNTransition, String, Integer, SchedStrategy), transition by name.

    • setResource

      public WFNResource setResource(String transition, String name, Integer servers)
      As setResource(WFNTransition, String, Integer, SchedStrategy), transition by name.

    • setResource

      public WFNResource setResource(String transition, String name, Integer servers, SchedStrategy scheduling)
      As setResource(WFNTransition, String, Integer, SchedStrategy), transition by name.

    • setResource

      public WFNResource setResource(WFNTransition transition, String name, Integer servers, SchedStrategy scheduling)
      Assign a shared resource to a timed transition.

      A resource is shared by every task that names it and by every case. Calling it again with an existing NAME reuses that resource; SERVERS and SCHEDULING, when not null, update it.

      Parameters:
      transition - timed transition of this net
      name - resource name
      servers - number of servers (default 1 for a new resource)
      scheduling - scheduling strategy (default FCFS for a new resource)
      Returns:
      the resource

    • setArrivalProcess

      public void setArrivalProcess(Distribution process)
      Set the stream of cases for open analysis to an interarrival distribution.
      Parameters:
      process - interarrival distribution, or null to clear it

    • setArrivalProcess

      public void setArrivalProcess(String process)
      Set the stream of cases by type; only "none", which clears it, takes no parameter.
      Parameters:
      process - "none"

    • setArrivalProcess

      public void setArrivalProcess(String process, Object param)
      Set the stream of cases by type: ("poisson", rate), ("map", mapObject) or ("none", null).
      Parameters:
      process - stream type
      param - its parameter

    • setClosedCases

      public void setClosedCases(int k)
      Set k concurrent cases (closed analysis); 0 = open.
      Parameters:
      k - number of cases

    • setStateCap

      public void setStateCap(double cap)
      Set the largest state space explored by the analyses.
      Parameters:
      cap - state cap

    • getPlaces

      public List<WFNPlace> getPlaces()

    • getTransitions

      public List<WFNTransition> getTransitions()

    • getArcs

      public List<WFNArc> getArcs()

    • getResources

      public List<WFNResource> getResources()

    • getSourcePlace

      public WFNPlace getSourcePlace()

    • getSinkPlace

      public WFNPlace getSinkPlace()

    • getArrivalProcess

      public Distribution getArrivalProcess()

    • getClosedCases

      public int getClosedCases()

    • getStateCap

      public double getStateCap()

    • getPlace

      public WFNPlace getPlace(String name)
      Get a place by name.
      Parameters:
      name - place name
      Returns:
      the place

    • getTransition

      public WFNTransition getTransition(String name)
      Get a transition by name.
      Parameters:
      name - transition name
      Returns:
      the transition

    • getIncidence

      public Matrix[] getIncidence()
      Input and output arc weights, places x transitions.
      Returns:
      {Pre, Post}

    • validate

      public void validate()
      Check the structural WF-net conditions.

      Requires exactly one place without incoming arcs (the source i), exactly one place without outgoing arcs (the sink o), and every place and transition on a directed path from i to o, which is strong connectivity once the arc o -> i is added. A declared source or sink must be that place. On success sourcePlace and sinkPlace are set; on failure a LINE:input:Model error names the offending nodes.

    • checkSoundness

      public SoundnessReport checkSoundness()
      As checkSoundness(int, double) with k = 1 and the stateCap property.

    • checkSoundness

      public SoundnessReport checkSoundness(int k)
      As checkSoundness(int, double) with the stateCap property.

    • checkSoundness

      public SoundnessReport checkSoundness(int k, double stateCap)
      Decide k-soundness on the reachability graph.

      From the marking with K tokens in the source the net is k-sound when (1) the final marking, K tokens in the sink, is reachable from every reachable marking (option to complete), (2) no reachable marking puts K tokens in the sink together with other tokens (proper completion) and (3) every transition fires in some reachable marking (no dead transitions). The untimed net is explored, as soundness is a property of the net, not of its timing. A marking that strictly covers one of its ancestors proves the net unbounded, hence unsound. If STATECAP markings are explored first, the verdict is "unknown", never "sound".

      Parameters:
      k - number of tokens in the source
      stateCap - largest number of markings explored
      Returns:
      the report; SoundnessReport.isSound() is the verdict

    • getCycleTime

      public PH getCycleTime()
      Exact case cycle time of one case without contention.

      The reachability graph of the timed net from one token in the source becomes an absorbing CTMC whose absorbing state is the final marking; immediate transitions are folded out of it, so the case duration is exactly phase-type for any sound net with phase-type timing, series-parallel or not. Requires 1-soundness.

      Returns:
      the PH law of the case duration

    • getCycleTimeAnalysis

      public CycleTimeAnalysis getCycleTimeAnalysis()
      Full single-case analysis: PH law, moments, CDF, percentiles, expected firings per transition, expected token-time per place.
      Returns:
      the analysis

    • getResourceLoads

      public ResourceLoads getResourceLoads()
      Per-resource load of an open stream of cases at the rate of the arrival process.
      Returns:
      the loads

    • getResourceLoads

      public ResourceLoads getResourceLoads(double lambda)
      Per-resource load of an open stream of cases.

      One row per resource and per task with a finite server count: the offered load LAMBDA * sum_t E[firings of t] * E[time of t] divided by the servers, using the expected firings of one case. The open system is stable only if every load is below 1.

      Parameters:
      lambda - case arrival rate
      Returns:
      the loads

    • isBlockStructured

      public boolean isBlockStructured()
      True if the net reduces to a process tree.

      The net is reduced by five rules until nothing applies: fold a single-input single-output transition between two places into a place, fold a single-input single-output place between two transitions into a transition, merge parallel places (AND block), merge parallel transitions (XOR block, choices resolved by immediate transitions of equal priority, in proportion to their weights) and absorb a self-loop transition (geometric loop). It is block-structured if it reduces to one place.

      Returns:
      true if block-structured

    • toWorkflow

      public Workflow toWorkflow()
      Equivalent Workflow of a block-structured net.

      Each timed transition maps to an activity with its distribution and each block to the Workflow precedence of the same meaning. Immediate transitions take no time and disappear; where a fork or join needs an anchor that the net does not provide, an Immediate activity named wfn_aux_<n> is added. Workflow.Loop executes its body a geometric number of times >= 1, so a loop with work on its return path is refused. Workflow models an Immediate activity at rate GlobalConstants.Immediate, so its toPH() agrees with getCycleTime() up to that rate, not to machine precision.

      Returns:
      the workflow

    • toNetwork

      public Network toNetwork(String target)
      Compile the workflow net to a LINE Network, with the soundness gate on.
      Parameters:
      target - "forkjoin" or "spn"
      Returns:
      the network
      See Also:

    • toNetwork

      public Network toNetwork(String target, Object... options)
      Compile the workflow net to a LINE Network.

      TARGET "forkjoin" (block-structured nets): AND-split -> Fork, AND-join -> Join, XOR and loops -> probabilistic routing, a task -> Delay (no contention), a Queue of its own (finite servers) or the Queue of its resource. Tasks sharing a resource are told apart by class. Solvers: MVA (fork-join approximations), JMT, LDES.

      TARGET "spn" (any sound net): a stochastic Petri net with a case-counter place. A task on a resource becomes an immediate acquire followed by the timed task, which releases the resource; waiting tasks take a free server in random order, in proportion to their weights, whatever the resource scheduling (the fork-join target honours it). Its transitions create and destroy tokens (an AND-split makes two of one), which SolverSSA and SolverLDES simulate; SolverCTMC and SolverJMT do not support that.

      Open analysis (setArrivalProcess) gives a Source and a Sink; closed analysis (setClosedCases(k)) recirculates k cases through a zero-time restart. The soundness gate (k-soundness, k the number of closed cases or 1) is on by default; pass "checkSoundness", false to skip it on nets too large to explore.

      Parameters:
      target - "forkjoin" or "spn"
      options - name/value pairs: "checkSoundness", Boolean
      Returns:
      the network

    • getCaseMetrics

      public CaseMetrics getCaseMetrics(NetworkSolver solver)
      Case-level metrics from a solver of the network returned by the last toNetwork call: throughput, WIP, mean cycle time (Little's law), resource utilisation, per-task response times (forkjoin) or tokens in service (spn) and mean tokens per place (spn only).
      Parameters:
      solver - solver built on the last compiled network
      Returns:
      the metrics

    • savePNML

      public void savePNML(String filename)
      Write the net to PNML with one token in the source.

      Builds the plain Petri net (no case counter, no resources) and writes it with PnmlIO.save(jline.lang.Network, java.lang.String), so that fromPNML(String) reads it back with its timing.

      Parameters:
      filename - output path

    • fromPNML

      public static WorkflowNet fromPNML(String filename)
      As fromPNML(String, String) reading the first net.

    • fromPNML

      public static WorkflowNet fromPNML(String filename, String netName)
      Create a WorkflowNet from a PNML file.

      Reads the net with PnmlIO.load(java.lang.String) and converts it with fromNetwork(jline.lang.Network); the source and sink are found from the structure. A file from another tool is untimed and reads with every transition exponential at rate 1.

      Parameters:
      filename - input path
      netName - id of the net to read, or null for the first
      Returns:
      the workflow net

    • fromNetwork

      public static WorkflowNet fromNetwork(Network model)
      Create a WorkflowNet from a LINE Petri net.

      Copies the places, the transitions and their arcs of a single-class Network made of Place and Transition nodes. A transition must have exactly one mode and no inhibitor arcs or firing-rate dependence, since a WF-net transition has one firing rule. The result is validated.

      Parameters:
      model - the Petri net
      Returns:
      the workflow net

    • formatReport

      public static String formatReport(SoundnessReport report)
      One-line summary of a soundness report.
      Parameters:
      report - the report
      Returns:
      the summary