![]() |
LINE Solver (C++)
Templated C++ port of the LINE queueing solver
|
#include <line/api/wfn/workflow_net.h>
Public Types | |
| typedef lang::Distrib< double > | Dist |
Public Member Functions | |
| WorkflowNet (const std::string &name) | |
| WorkflowNet (WorkflowNet &&)=default | |
| WorkflowNet & | operator= (WorkflowNet &&)=default |
| WorkflowNet (const WorkflowNet &)=delete | |
| WorkflowNet & | operator= (const WorkflowNet &)=delete |
| const std::string & | name () const |
| std::size_t | num_places () const |
| std::size_t | num_transitions () const |
| const WFNPlace & | place (std::size_t i) const |
| WFNTransition & | transition (std::size_t i) |
| const WFNTransition & | transition (std::size_t i) const |
| const std::vector< WFNArc > & | arcs () const |
| std::size_t | num_resources () const |
| const WFNResource & | resource (std::size_t r) const |
| const WFNPlace * | source_place () const |
| The source place, set by validate when not declared; nullptr before. | |
| const WFNPlace * | sink_place () const |
| The sink place, set by validate when not declared; nullptr before. | |
| const Dist * | arrival_process () const |
| The interarrival law of cases (open analysis), or nullptr. | |
| long | closed_cases () const |
| double | state_cap () const |
| WFNPlace & | add_place (const std::string &name, double initial_marking=0.0) |
| addPlace(name, initialMarking). | |
| WFNTransition & | add_transition (const std::string &name, const Dist &distribution=Exp(1.0), double servers=std::numeric_limits< double >::infinity(), double priority=1.0, double weight=1.0) |
| addTransition(name, distribution, [], servers, priority, weight): the timing follows the law, IMMEDIATE for an Immediate law and TIMED for any other. | |
| WFNTransition & | add_transition (const std::string &name, const Dist &distribution, lang::TimingStrategy timing, double servers=std::numeric_limits< double >::infinity(), double priority=1.0, double weight=1.0) |
| addTransition(name, distribution, timing, servers, priority, weight). | |
| const WFNArc & | add_arc (const ElementRef &source, const ElementRef &target, double weight=1.0) |
| addArc(source, target, weight): from a place to a transition or from a transition to a place, given as elements of this net or by name. | |
| void | set_source (const ElementRef &place) |
| setSource(place): declare the source place (checked by validate). | |
| void | set_sink (const ElementRef &place) |
| setSink(place): declare the sink place (checked by validate). | |
| WFNResource & | set_resource (const ElementRef &transition, const std::string &name) |
| setResource(transition, name, servers, scheduling): assign a resource, shared by every task that names it and by every case. | |
| WFNResource & | set_resource (const ElementRef &transition, const std::string &name, double servers) |
| WFNResource & | set_resource (const ElementRef &transition, const std::string &name, double servers, lang::SchedStrategy scheduling) |
| void | set_arrival_process (const Dist &process) |
| setArrivalProcess(dist): any interarrival distribution for open analysis. | |
| void | set_arrival_process (const std::string &type) |
| setArrivalProcess('none'), or a type that needs a parameter, which is then refused. | |
| void | set_arrival_process (const std::string &type, double rate) |
| setArrivalProcess('poisson', rate). | |
| void | set_arrival_process (const std::string &type, const Dist &map) |
| setArrivalProcess('map', MAP). | |
| void | set_closed_cases (double k) |
| setClosedCases(k): k concurrent cases (closed analysis); 0 = open. | |
| void | set_state_cap (double cap) |
| setStateCap(cap): the largest state space explored by the analyses. | |
| const WFNPlace & | get_place (const std::string &name) const |
| getPlace(name). | |
| WFNTransition & | get_transition (const std::string &name) |
| getTransition(name). | |
| std::pair< Matrix< double >, Matrix< double > > | get_incidence () const |
| getIncidence(): input and output arc weights, places x transitions. | |
| void | validate () |
| validate(): exactly one place without incoming arcs (the source i), exactly one without outgoing arcs (the sink o), and every place and transition on a directed path from i to o. | |
| SoundnessReport | check_soundness (double k=1) |
| checkSoundness(k, stateCap): decide k-soundness on the reachability graph. | |
| SoundnessReport | check_soundness (double k, double state_cap) |
| Dist | get_cycle_time () |
| getCycleTime(): exact case cycle time of one case without contention. | |
| CycleTimeAnalysis | get_cycle_time_analysis () |
| getCycleTimeAnalysis(): the full single-case analysis. | |
| ResourceLoads | get_resource_loads (double lambda) |
| getResourceLoads(lambda): 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, from the expected firings of one case. | |
| ResourceLoads | get_resource_loads () |
| getResourceLoads(): LAMBDA is the rate of the arrival process. | |
| bool | is_block_structured () |
| isBlockStructured(): true if the net reduces to a process tree. | |
| workflow::Workflow< double > | to_workflow () |
| toWorkflow(): the equivalent Workflow of a block-structured net. | |
| std::shared_ptr< Network > | to_network (const std::string &target, bool check_soundness=true) |
| toNetwork(target, 'checkSoundness', tf): compile the net to a Network. | |
| CaseMetrics | get_case_metrics (NetworkSolver &solver) |
| getCaseMetrics(solver): case-level metrics from a solver built on the network returned by the last to_network call. | |
| void | save_pnml (const std::string &filename) |
| savePNML(filename): write the plain Petri net (no case counter, no resources) with one token in the source, so that from_pnml reads it back with its timing. | |
Static Public Member Functions | |
| static std::string | format_report (const SoundnessReport &report) |
| formatReport(report): one-line summary of a soundness report. | |
| static WorkflowNet | from_pnml (const std::string &filename, const std::string &net_name=std::string()) |
| WorkflowNet.fromPNML(filename, netName): read a net with pnml_load and convert it with from_network; the source and sink are found from the structure. | |
| static WorkflowNet | from_network (Network &model) |
| WorkflowNet.fromNetwork(model): copy the places, transitions and arcs of a single-class Network of Place and Transition nodes. | |
Static Public Attributes | |
| static constexpr const char * | ReservedPrefix = "wfn_" |
| Names prefixed so that compiled networks never collide with user names. | |
Definition at line 323 of file workflow_net.h.
| typedef lang::Distrib<double> line::wfn::WorkflowNet::Dist |
Definition at line 325 of file workflow_net.h.
|
inlineexplicit |
Definition at line 330 of file workflow_net.h.
References name().
Referenced by from_network(), from_pnml(), operator=(), operator=(), WorkflowNet(), and WorkflowNet().
|
default |
References WorkflowNet().
|
delete |
References WorkflowNet().
|
inline |
addArc(source, target, weight): from a place to a transition or from a transition to a place, given as elements of this net or by name.
WEIGHT is a positive integer.
Definition at line 415 of file workflow_net.h.
References line::ErrorKind::ErrorKind(), and line::InputError::InputError().
Referenced by from_network().
|
inline |
addPlace(name, initialMarking).
The initial marking is informational: the analyses always start from k tokens in the source place.
Definition at line 363 of file workflow_net.h.
References name().
Referenced by from_network().
|
inline |
addTransition(name, distribution, timing, servers, priority, weight).
Definition at line 387 of file workflow_net.h.
References line::ErrorKind::ErrorKind(), line::lang::IMMEDIATE, line::InputError::InputError(), name(), and line::lang::Distrib< T >::type.
|
inline |
addTransition(name, distribution, [], servers, priority, weight): the timing follows the law, IMMEDIATE for an Immediate law and TIMED for any other.
SERVERS is the number of concurrent firings (default Inf, i.e. no contention unless a resource is assigned); PRIORITY and WEIGHT rank and share the enabled immediate transitions.
Definition at line 377 of file workflow_net.h.
References add_transition(), line::lang::IMMEDIATE, name(), and line::lang::TIMED.
Referenced by add_transition(), and from_network().
|
inline |
Definition at line 343 of file workflow_net.h.
|
inline |
The interarrival law of cases (open analysis), or nullptr.
Definition at line 351 of file workflow_net.h.
|
inline |
Definition at line 614 of file workflow_net.h.
References line::wfn::SoundnessReport::dead_transitions, line::wfn::SoundnessReport::deadlocks, line::ErrorKind::ErrorKind(), line::wfn::SoundnessReport::improper_completion, line::InputError::InputError(), line::wfn::SoundnessReport::k, name(), line::wfn::SoundnessReport::no_option_to_complete, line::wfn::SoundnessReport::sound, state_cap(), line::wfn::SoundnessReport::state_space_size, line::wfn::SoundnessReport::unbounded, line::wfn::SoundnessReport::unbounded_or_too_large, line::wfn::SoundnessReport::unbounded_witness, validate(), line::wfn::SoundnessReport::verdict, and line::wfn::SoundnessReport::witnesses.
|
inline |
checkSoundness(k, 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".
Definition at line 612 of file workflow_net.h.
References check_soundness().
Referenced by check_soundness(), and to_network().
|
inline |
Definition at line 352 of file workflow_net.h.
|
inlinestatic |
formatReport(report): one-line summary of a soundness report.
Definition at line 700 of file workflow_net.h.
References line::wfn::SoundnessReport::k, line::wfn::SoundnessReport::state_space_size, line::wfn::SoundnessReport::verdict, and line::wfn::SoundnessReport::witnesses.
|
inlinestatic |
WorkflowNet.fromNetwork(model): copy the places, transitions and arcs of a single-class Network 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.
Definition at line 996 of file workflow_net.h.
References add_arc(), add_place(), add_transition(), line::Matrix< T >::cols(), line::qn::TransitionParam< T >::enabling, line::ErrorKind::ErrorKind(), line::qn::TransitionParam< T >::fireweight, line::qn::TransitionParam< T >::firing, line::qn::TransitionParam< T >::firingdep, line::qn::TransitionParam< T >::firingprio, line::qn::TransitionParam< T >::firingproc, line::qn::Network< T >::get_struct(), line::lang::IMMEDIATE, line::qn::TransitionParam< T >::inhibiting, line::qn::TransitionParam< T >::nmodeservers, line::lang::node_type_to_text(), line::lang::Place, line::Matrix< T >::rows(), line::qn::TransitionParam< T >::timing, line::lang::Transition, line::UnsupportedError::UnsupportedError(), validate(), and WorkflowNet().
Referenced by from_pnml().
|
inlinestatic |
WorkflowNet.fromPNML(filename, netName): read a net with pnml_load and convert it with from_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.
Definition at line 985 of file workflow_net.h.
References from_network(), line::io::pnml_load(), and WorkflowNet().
|
inline |
getCaseMetrics(solver): case-level metrics from a solver built on the network returned by the last to_network call.
The fork-join open cycle time follows the process tree; the closed one, and the SPN one, are Little's law on the case population.
Definition at line 909 of file workflow_net.h.
References line::NetworkSolver::avg_table(), line::wfn::WorkflowNet::Compiled::Res::busy, line::wfn::CaseMetrics::cycle_time, line::ErrorKind::ErrorKind(), line::InputError::InputError(), line::wfn::CaseMetrics::Tasks::InService, line::wfn::CaseMetrics::mode, line::NetworkSolver::model(), line::wfn::WorkflowNet::Compiled::Busy::name, line::wfn::WorkflowNet::Compiled::Res::name, line::wfn::CaseMetrics::Places::Place, line::wfn::WorkflowNet::Compiled::Busy::place, line::wfn::CaseMetrics::places, line::AvgTable::QLen, line::wfn::CaseMetrics::Places::QLen, line::wfn::CaseMetrics::Resources::Resource, line::wfn::CaseMetrics::resources, line::AvgTable::RespT, line::wfn::CaseMetrics::Tasks::RespT, line::wfn::CaseMetrics::Resources::Servers, line::wfn::WorkflowNet::Compiled::Res::servers, line::wfn::WorkflowNet::Compiled::Res::station, line::wfn::CaseMetrics::target, line::wfn::CaseMetrics::Tasks::Task, line::wfn::CaseMetrics::tasks, line::wfn::CaseMetrics::throughput, line::AvgTable::Tput, line::AvgTable::Util, line::wfn::CaseMetrics::Resources::Utilization, and line::wfn::CaseMetrics::wip.
|
inline |
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.
Definition at line 725 of file workflow_net.h.
References get_cycle_time_analysis(), and line::wfn::CycleTimeAnalysis::ph.
|
inline |
getCycleTimeAnalysis(): the full single-case analysis.
Definition at line 728 of file workflow_net.h.
References line::wfn::CycleTimeAnalysis::alpha, line::ErrorKind::ErrorKind(), line::wfn::CycleTimeAnalysis::Firings::ExpectedFirings, line::wfn::CycleTimeAnalysis::PlaceTime::ExpectedTokenTime, line::lang::GlobalConstants::FineTol, line::wfn::CycleTimeAnalysis::firings, line::wfn::CycleTimeAnalysis::mean, line::wfn::CycleTimeAnalysis::moments, name(), line::wfn::CycleTimeAnalysis::num_states, line::wfn::CycleTimeAnalysis::ph, line::wfn::CycleTimeAnalysis::PlaceTime::Place, line::wfn::CycleTimeAnalysis::place_time, line::wfn::CycleTimeAnalysis::Q, line::Matrix< T >::rows(), line::wfn::CycleTimeAnalysis::scv, line::Matrix< T >::size(), line::wfn::CycleTimeAnalysis::Firings::Transition, line::UnsupportedError::UnsupportedError(), line::wfn::CycleTimeAnalysis::variance, and line::wfn::CycleTimeAnalysis::zero_time_prob.
Referenced by get_cycle_time(), and get_resource_loads().
|
inline |
getIncidence(): input and output arc weights, places x transitions.
Definition at line 498 of file workflow_net.h.
|
inline |
getPlace(name).
Definition at line 483 of file workflow_net.h.
References line::ErrorKind::ErrorKind(), line::InputError::InputError(), and name().
|
inline |
getResourceLoads(): LAMBDA is the rate of the arrival process.
Definition at line 813 of file workflow_net.h.
References line::ErrorKind::ErrorKind(), get_resource_loads(), and line::InputError::InputError().
|
inline |
getResourceLoads(lambda): 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, from the expected firings of one case.
The open system is stable only if every load is below 1.
Definition at line 784 of file workflow_net.h.
References line::wfn::ResourceLoads::DemandPerCase, line::wfn::CycleTimeAnalysis::Firings::ExpectedFirings, line::wfn::CycleTimeAnalysis::firings, get_cycle_time_analysis(), line::wfn::ResourceLoads::Load, name(), line::wfn::ResourceLoads::Resource, line::wfn::ResourceLoads::Servers, and line::wfn::ResourceLoads::Stable.
Referenced by get_resource_loads().
|
inline |
getTransition(name).
Definition at line 490 of file workflow_net.h.
References line::ErrorKind::ErrorKind(), line::InputError::InputError(), and name().
|
inline |
isBlockStructured(): true if the net reduces to a process tree.
Five rules apply until nothing does: 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.
Definition at line 832 of file workflow_net.h.
References validate().
|
inline |
Definition at line 337 of file workflow_net.h.
Referenced by add_place(), add_transition(), add_transition(), check_soundness(), get_cycle_time_analysis(), get_place(), get_resource_loads(), get_transition(), set_resource(), set_resource(), set_resource(), validate(), and WorkflowNet().
|
inline |
Definition at line 338 of file workflow_net.h.
|
inline |
Definition at line 344 of file workflow_net.h.
|
inline |
Definition at line 339 of file workflow_net.h.
|
delete |
References WorkflowNet().
|
default |
References WorkflowNet().
|
inline |
Definition at line 340 of file workflow_net.h.
Referenced by set_sink(), and set_source().
|
inline |
Definition at line 345 of file workflow_net.h.
|
inline |
savePNML(filename): write the plain Petri net (no case counter, no resources) with one token in the source, so that from_pnml reads it back with its timing.
Definition at line 973 of file workflow_net.h.
References line::io::pnml_save(), and validate().
|
inline |
setArrivalProcess(dist): any interarrival distribution for open analysis.
Definition at line 458 of file workflow_net.h.
|
inline |
setArrivalProcess('none'), or a type that needs a parameter, which is then refused.
Definition at line 463 of file workflow_net.h.
|
inline |
setArrivalProcess('map', MAP).
Definition at line 467 of file workflow_net.h.
|
inline |
setArrivalProcess('poisson', rate).
Definition at line 465 of file workflow_net.h.
|
inline |
setClosedCases(k): k concurrent cases (closed analysis); 0 = open.
Definition at line 470 of file workflow_net.h.
References line::ErrorKind::ErrorKind(), and line::InputError::InputError().
|
inline |
setResource(transition, name, servers, scheduling): assign a resource, shared by every task that names it and by every case.
An existing NAME is reused; SERVERS and SCHEDULING, when given, update it.
Definition at line 446 of file workflow_net.h.
References name(), and transition().
|
inline |
Definition at line 449 of file workflow_net.h.
References name(), and transition().
|
inline |
Definition at line 452 of file workflow_net.h.
References name(), and transition().
|
inline |
setSink(place): declare the sink place (checked by validate).
Definition at line 439 of file workflow_net.h.
References place().
|
inline |
setSource(place): declare the source place (checked by validate).
Definition at line 436 of file workflow_net.h.
References place().
|
inline |
setStateCap(cap): the largest state space explored by the analyses.
Definition at line 477 of file workflow_net.h.
References line::ErrorKind::ErrorKind(), and line::InputError::InputError().
|
inline |
The sink place, set by validate when not declared; nullptr before.
Definition at line 349 of file workflow_net.h.
|
inline |
The source place, set by validate when not declared; nullptr before.
Definition at line 347 of file workflow_net.h.
|
inline |
Definition at line 353 of file workflow_net.h.
Referenced by check_soundness().
|
inline |
toNetwork(target, 'checkSoundness', tf): compile the net to a Network.
"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.
"spn": any sound net, as 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. Its transitions create and destroy tokens, which SolverSSA and SolverLDES simulate.
Open analysis (set_arrival_process) gives a Source and a Sink; closed analysis (set_closed_cases(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 false to skip it on nets too large to explore.
Definition at line 884 of file workflow_net.h.
References check_soundness(), line::ErrorKind::ErrorKind(), line::InputError::InputError(), and validate().
|
inline |
toWorkflow(): the equivalent Workflow of a block-structured net.
Each timed transition is an activity with its law and each block the Workflow precedence of the same meaning. Immediate transitions disappear; where a fork or join needs an anchor the net does not provide, an Immediate activity wfn_aux_<n> is added. Workflow::Loop repeats one 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 to_ph() agrees with get_cycle_time() up to that rate, not to machine precision.
Definition at line 850 of file workflow_net.h.
References line::ErrorKind::ErrorKind(), and line::UnsupportedError::UnsupportedError().
|
inline |
Definition at line 341 of file workflow_net.h.
Referenced by set_resource(), set_resource(), and set_resource().
|
inline |
Definition at line 342 of file workflow_net.h.
|
inline |
validate(): exactly one place without incoming arcs (the source i), exactly one without outgoing arcs (the sink o), and every place and transition on a directed path from i to o.
A declared source or sink must be that place. On success the source and sink are set; on failure a LINE:input:Model error names the offending nodes.
Definition at line 520 of file workflow_net.h.
References line::ErrorKind::ErrorKind(), line::InputError::InputError(), and name().
Referenced by check_soundness(), from_network(), is_block_structured(), save_pnml(), and to_network().
|
staticconstexpr |
Names prefixed so that compiled networks never collide with user names.
Definition at line 328 of file workflow_net.h.