Tutorial 16: A queueing Petri net
A queueing Petri net (QPN) augments an ordinary stochastic Petri net with queueing places. Instead of becoming available to the output transitions immediately upon deposit, a token enters a scheduling station embedded inside the place, is served under that place's scheduling strategy, and only then moves to a depository from which the output transitions consume it. Queueing places let a single formalism capture both resource contention (the embedded queues) and synchronization and control flow (the transitions).
In LINE a Place becomes a queueing place as soon as a service process is assigned to a token color with setService; the scheduling strategy of the embedded queue is the optional third constructor argument. This tutorial models a finite population of N = 4 jobs alternating between a CPU and a think stage, each rendered as a queueing place. The CPU is a single-server FCFS queueing place with service rate 1.5; the think stage is an infinite-server queueing place with rate 0.5 (mean think time 2). Two immediate transitions move one token per firing between the places, so the token flow reproduces a machine-repairman (finite-population) model whose exact solution is available from SolverMVA on the equivalent Delay + Queue network.
N = 4;
model = Network('QueueingPetriNet');
% Block 1: two queueing places (setService installs the embedded queue)
cpu = Place(model, 'CPU', SchedStrategy.FCFS); % single-server queue
think = Place(model, 'Think', SchedStrategy.INF); % infinite-server queue
jobs = ClosedClass(model, 'Jobs', N, think, 0);
cpu.setService(jobs, Exp(1.5)); % embedded FCFS service, rate 1.5
think.setService(jobs, Exp(0.5)); % embedded think time, mean 2
% Block 2: two immediate transitions cycling one token per firing
toCPU = Transition(model, 'toCPU');
m1 = toCPU.addMode('m1');
toCPU.setTimingStrategy(m1, TimingStrategy.IMMEDIATE);
toCPU.setEnablingConditions(m1, jobs, think, 1);
toCPU.setFiringOutcome(m1, jobs, cpu, 1);
toThink = Transition(model, 'toThink');
m2 = toThink.addMode('m2');
toThink.setTimingStrategy(m2, TimingStrategy.IMMEDIATE);
toThink.setEnablingConditions(m2, jobs, cpu, 1);
toThink.setFiringOutcome(m2, jobs, think, 1);
% Block 3: topology and initial marking
P = model.initRoutingMatrix();
P.set(jobs, jobs, think, toCPU, 1.0);
P.set(jobs, jobs, toCPU, cpu, 1.0);
P.set(jobs, jobs, cpu, toThink, 1.0);
P.set(jobs, jobs, toThink, think, 1.0);
model.link(P);
think.setState(N); % all tokens start in the think place
cpu.setState(0);
% Block 4: solution. Queueing places are simulated by LDES
AvgTableLDES = SolverLDES(model, 'seed', 23000, 'samples', 2e5).avgTable()
% Exact cross-check on the equivalent Delay + M/M/1 network
ref = Network('ref');
delay = Delay(ref, 'Think');
queue = Queue(ref, 'CPU', SchedStrategy.FCFS);
cc = ClosedClass(ref, 'Jobs', N, delay, 0);
delay.setService(cc, Exp(0.5));
queue.setService(cc, Exp(1.5));
ref.link(Network.serialRouting(delay, queue));
AvgTableMVA = SolverMVA(ref).avgTable()int N = 4;
Network model = new Network("QueueingPetriNet");
// Block 1: two queueing places (setService installs the embedded queue)
Place cpu = new Place(model, "CPU", SchedStrategy.FCFS); // single-server queue
Place think = new Place(model, "Think", SchedStrategy.INF); // infinite-server queue
ClosedClass jobs = new ClosedClass(model, "Jobs", N, think, 0);
cpu.setService(jobs, new Exp(1.5)); // embedded FCFS service, rate 1.5
think.setService(jobs, new Exp(0.5)); // embedded think time, mean 2
// Block 2: two immediate transitions cycling one token per firing
Transition toCPU = new Transition(model, "toCPU");
Mode m1 = toCPU.addMode("m1");
toCPU.setTimingStrategy(m1, TimingStrategy.IMMEDIATE);
toCPU.setEnablingConditions(m1, jobs, think, 1);
toCPU.setFiringOutcome(m1, jobs, cpu, 1);
Transition toThink = new Transition(model, "toThink");
Mode m2 = toThink.addMode("m2");
toThink.setTimingStrategy(m2, TimingStrategy.IMMEDIATE);
toThink.setEnablingConditions(m2, jobs, cpu, 1);
toThink.setFiringOutcome(m2, jobs, think, 1);
// Block 3: topology and initial marking
RoutingMatrix P = model.initRoutingMatrix();
P.set(jobs, jobs, think, toCPU, 1.0);
P.set(jobs, jobs, toCPU, cpu, 1.0);
P.set(jobs, jobs, cpu, toThink, 1.0);
P.set(jobs, jobs, toThink, think, 1.0);
model.link(P);
think.setState(N); // all tokens start in the think place
cpu.setState(0);
// Block 4: solution. Queueing places are simulated by LDES
SolverLDES ldes = new SolverLDES(model, "seed", 23000);
ldes.options.samples = 200000;
ldes.avgTable().print();from line_solver import *
N = 4
model = Network('QueueingPetriNet')
# Block 1: two queueing places (set_service installs the embedded queue)
cpu = Place(model, 'CPU', SchedStrategy.FCFS) # single-server queue
think = Place(model, 'Think', SchedStrategy.INF) # infinite-server queue
jobs = ClosedClass(model, 'Jobs', N, think, 0)
cpu.set_service(jobs, Exp(1.5)) # embedded FCFS service, rate 1.5
think.set_service(jobs, Exp(0.5)) # embedded think time, mean 2
# Block 2: two immediate transitions cycling one token per firing
toCPU = Transition(model, 'toCPU')
m1 = toCPU.addMode('m1')
toCPU.setTimingStrategy(m1, TimingStrategy.IMMEDIATE)
toCPU.setEnablingConditions(m1, jobs, think, 1)
toCPU.setFiringOutcome(m1, jobs, cpu, 1)
toThink = Transition(model, 'toThink')
m2 = toThink.addMode('m2')
toThink.setTimingStrategy(m2, TimingStrategy.IMMEDIATE)
toThink.setEnablingConditions(m2, jobs, cpu, 1)
toThink.setFiringOutcome(m2, jobs, think, 1)
# Block 3: topology and initial marking
P = model.init_routing_matrix()
P.set(jobs, jobs, think, toCPU, 1.0)
P.set(jobs, jobs, toCPU, cpu, 1.0)
P.set(jobs, jobs, cpu, toThink, 1.0)
P.set(jobs, jobs, toThink, think, 1.0)
model.link(P)
think.set_state(N) # all tokens start in the think place
cpu.set_state(0)
# Block 4: solution. Queueing places are simulated by LDES
print(SolverLDES(model, seed=23000, samples=200000).avg_table())Expected Output
The metric reported for a queueing place is its token count: the total marking summed over the tokens waiting, in service and in the depository. For the CPU place this equals the mean number in an M/M/1 queue and for the think place the mean number in service at the infinite-server stage. The LDES simulation of the QPN matches the exact finite-population result to within simulation error:
AvgTableLDES = % SolverLDES simulation of the QPN
Station JobClass QLen RespT Tput
CPU Jobs 1.6189 1.3626 1.1881
Think Jobs 2.3811 2.0040 1.1881
AvgTableMVA = % exact SolverMVA on Delay + M/M/1
Think Jobs 2.3817 2.0000 1.1908
CPU Jobs 1.6183 1.3590 1.1908Queueing places are simulated by the LDES solver, which supports the FCFS, LCFS, SIRO and INF embedded scheduling strategies (single- or multi-server) with exponential, deterministic, immediate and renewal phase-type service. Because a queueing place embeds a service station inside a place, it cannot be represented as a single node in JMT; a queueing-place model is rejected by SolverJMT and must be expanded into a place plus an adjacent queueing station to be simulated there.