1% Ret = MMAPPH1NPPR(D, sigma, S, ...)
3% Returns various performane measures of a continuous time
4%
MMAP[K]/PH[K]/1 non-preemptive priority queue, see [1]_.
8% D : list of matrices of shape (N,N), length (K+1)
9% The D0...DK matrices of the arrival process.
10% D1 corresponds to the lowest, DK to the highest priority.
11% sigma : list of row vectors, length (K)
12% The list containing the initial probability vectors of the service
13% time distributions of the various customer types. The length of the
14% vectors does not have to be the same.
15% S : list of square matrices, length (K)
16% The transient generators of the phase type distributions representing
17% the service time of the jobs belonging to various types.
19% The rest of the function parameters specify the options
20% and the performance measures to be computed.
22% The supported performance measures and options in
this
25% +----------------+--------------------+----------------------------------------+
26% | Parameter name | Input parameters | Output |
27% +================+====================+========================================+
28% |
"ncMoms" | Number of moments | The moments of the number of customers |
29% +----------------+--------------------+----------------------------------------+
30% |
"ncDistr" | Upper limit K | The distribution of the number of |
31% | | | customers from level 0 to level K-1 |
32% +----------------+--------------------+----------------------------------------+
33% |
"stMoms" | Number of moments | The sojourn time moments |
34% +----------------+--------------------+----------------------------------------+
35% |
"stDistr" | A vector of points | The sojourn time distribution at the |
36% | | | requested points (cummulative, cdf) |
37% +----------------+--------------------+----------------------------------------+
38% |
"prec" | The precision | Numerical precision used as a stopping |
39% | | | condition when solving the Riccati and |
40% | | | the matrix-quadratic equations |
41% +----------------+--------------------+----------------------------------------+
42% |
"erlMaxOrder" | Integer number | The maximal Erlang order used in the |
43% | | | erlangization procedure. The
default |
44% | | | value
is 200. |
45% +----------------+--------------------+----------------------------------------+
46% |
"classes" | Vector of integers | Only the performance measures |
47% | | | belonging to these
classes are |
48% | | | returned. If not given, all
classes |
49% | | | are analyzed. |
50% +----------------+--------------------+----------------------------------------+
52% (The quantities related to the number of customers in
53% the system include the customer in the server, and the
54% sojourn time related quantities include the service
59% Ret : list of the performance measures
60% Each entry of the list corresponds to a performance
61% measure requested. Each entry
is a matrix, where the
62% columns belong to the various job types.
63% If there
is just a single item,
64% then it
is not put into a list.
68% .. [1] G. Horvath,
"Efficient analysis of the MMAP[K]/PH[K]/1
69% priority queue", European Journal of Operational
70% Research, 246(1), 128-139, 2015.
72function varargout = MMAPPH1NPPR(D, sigma, S, varargin)
81 for i=1:length(varargin)
82 if strcmp(varargin{i},
'erlMaxOrder')
83 erlMaxOrder = varargin{i+1};
84 eaten = [eaten, i, i+1];
85 elseif strcmp(varargin{i},
'prec')
86 precision = varargin{i+1};
87 eaten = [eaten, i, i+1];
88 elseif strcmp(varargin{i},
'classes')
90 eaten = [eaten, i, i+1];
94 global BuToolsCheckInput;
96 if isempty(BuToolsCheckInput)
97 BuToolsCheckInput =
true;
100 if BuToolsCheckInput && ~CheckMMAPRepresentation(D)
101 error(
'MMAPPH1PRPR: The arrival process is not a valid MMAP representation!');
106 if ~CheckPHRepresentation(sigma{k},S{k})
107 error(
'MMAPPH1PRPR: the vector and matrix describing the service times is not a valid PH representation!');
125 M(i) = M(i) + length(sigma{i});
128 % step 1. solution of the workload process of the joint queue
129 % ===========================================================
131 Qwpp = zeros(N*sum(M));
132 Qwmp = zeros(N,N*sum(M));
133 Qwpm = zeros(N*sum(M),N);
137 Qwpp(kix:kix+bs-1,kix:kix+bs-1) = kron(eye(N),S{i});
138 Qwmp(:,kix:kix+bs-1) = kron(D{i+1},sigma{i});
139 Qwpm(kix:kix+bs-1,:) = kron(eye(N),s{i});
143 % calculate fundamental matrices
144 [Psiw, Kw, Uw] = FluidFundamentalMatrices (Qwpp, Qwpm, Qwmp, Qwmm,
'PKU', precision);
146 % calculate boundary vector
147 Ua = ones(N,1) + 2*sum(Qwmp*inv(-Kw),2);
148 pm = linsolve ([Uw,Ua]
', [zeros(1,N),1]')
';
150 ro = ((1-sum(pm))/2)/(sum(pm)+(1-sum(pm))/2); % calc idle time with weight=1, and the busy time with weight=1/2
156 lambda(i) = sum(pi*D{i+1});
160 Qwmp = {}; Qwzp = {}; Qwpp = {};
161 Qwmz = {}; Qwpz = {}; Qwzz = {};
162 Qwmm = {}; Qwpm = {}; Qwzm = {};
164 % step 2. construct a workload process for classes k...K
165 % ======================================================
169 Qkwpp = zeros(N*Mlo*Mhi+N*Mhi);
170 Qkwpz = zeros(N*Mlo*Mhi+N*Mhi, N*Mlo);
171 Qkwpm = zeros(N*Mlo*Mhi+N*Mhi, N);
172 Qkwmz = zeros(N, N*Mlo);
173 Qkwmp = zeros(N, N*Mlo*Mhi+N*Mhi);
179 Qkwzp = zeros(N*Mlo, N*Mlo*Mhi+N*Mhi);
180 Qkwzm = zeros(N*Mlo, N);
181 Qkwzz = zeros(N*Mlo);
188 Qkwpp(kix:kix+bs-1,kix:kix+bs-1) = kron(eye(N),kron(eye(M(j)),S{i}));
189 Qkwpz(kix:kix+bs-1,kix2:kix2+bs2-1) = kron(eye(N),kron(eye(M(j)),s{i}));
190 Qkwzp(kix2:kix2+bs2-1,kix:kix+bs-1) = kron(D{i+1},kron(eye(M(j)), sigma{i}));
197 Qkwpp(kix:kix+bs-1,kix:kix+bs-1) = kron(eye(N),S{i});
198 Qkwpm(kix:kix+bs-1,:) = kron(eye(N),s{i});
199 Qkwmp(:,kix:kix+bs-1) = kron(D{i+1},sigma{i});
205 Qkwzz(kix:kix+bs-1,kix:kix+bs-1) = kron(Dlo, eye(M(j))) + kron(eye(N), S{j});
206 Qkwzm(kix:kix+bs-1,:) = kron(eye(N), s{j});
210 Psikw = FluidFundamentalMatrices (Qkwpp+Qkwpz*inv(-Qkwzz)*Qkwzp, Qkwpm+Qkwpz*inv(-Qkwzz)*Qkwzm, Qkwmp, Qkwmm, 'P', precision);
213 Qwzp{k} = Qkwzp; Qwmp{k} = Qkwmp; Qwpp{k} = Qkwpp;
214 Qwmz{k} = Qkwmz; Qwpz{k} = Qkwpz; Qwzz{k} = Qkwzz;
215 Qwmm{k} = Qkwmm; Qwpm{k} = Qkwpm; Qwzm{k} = Qkwzm;
218 % step 3. calculate Phi vectors
219 % =============================
220 lambdaS = sum(lambda);
221 phi{1} = (1-ro)*kappa*(-D0) / lambdaS;
230 pk(k) = sum(lambda(1:k))/lambdaS - (1-ro)*kappa*sum(sDk,2)/lambdaS;
236 V1 = Qwzpk(vix:vix+bs-1,:);
237 Ak{ii} = kron(I,sigma{ii}) * inv(-kron(sDk,eye(M(ii)))-kron(I,S{ii})) * (kron(I,s{ii}) + V1*Psiw{k+1});
242 Bk = Qwmpk * Psiw{k+1};
243 ztag = phi{1}*(inv(-D0)*D{k+1}*Ak{k} - Ak{1} + inv(-D0)*Bk);
245 ztag = ztag + phi{i+1}*(Ak{i}-Ak{i+1}) + phi{1}*inv(-D0)*D{i+1}*Ak{i};
247 Mx = eye(size(Ak{k}))-Ak{k};
249 phi{k+1} = [pk(k), ztag(2:end)]*inv(Mx); % phi(k) = Psi^(k)_k * p(k). Psi^(k)_i = phi(i) / p(k)
251 q0{k+1} = phi{1}*inv(-D0);
254 qLii = (phi{ii+1} - phi{ii} + phi{1}*inv(-D0)*D{ii+1}) * kron(I,sigma{ii}) * inv(-kron(sDk,eye(M(ii)))-kron(I,S{ii}));
255 qL{k+1} = [qL{k+1}, qLii];
259 % step 4. calculate performance measures
260 % ======================================
265 sD0k = sD0k + D{i+1};
268 % step 4.1 calculate distribution of the workload process right
269 % before the arrivals of class k jobs
270 % ============================================================
271 Kw = Qwpp{k}+Qwpz{k}*inv(-Qwzz{k})*Qwzp{k} + Psiw{k}*Qwmp{k};
272 BM = []; CM = []; DM = [];
274 BM = blkdiag(BM,kron(I,S{i}));
275 CM = [CM; kron(I,s{i})];
276 DM = blkdiag(DM,kron(D{k+1},eye(M(i))));
278 Kwu = [Kw, (Qwpz{k}+Psiw{k}*Qwmz{k})*inv(-Qwzz{k})*DM; zeros(size(BM,1),size(Kw,2)), BM];
279 Bwu = [Psiw{k}*D{k+1}; CM];
281 iniw = [q0{k}*Qwmp{k}+qL{k}*Qwzp{k}, qL{k}*DM];
287 norm = sum(pwu) + sum(iniw*inv(-Kwu)*Bwu);
291 % step 4.2 create the fluid model whose first passage time equals the
292 % WAITING time of the low prioroity customers
293 % ==================================================================
295 Qspp = zeros(KN+N*sum(M(k+1:end)));
296 Qspm = zeros(KN+N*sum(M(k+1:end)), N);
297 Qsmp = zeros(N, KN+N*sum(M(k+1:end)));
298 Qsmm = sD0k + D{k+1};
302 Qspp(KN+kix:KN+kix+bs-1,KN+kix:KN+kix+bs-1) = kron(I,S{i});
303 Qspm(KN+kix:KN+kix+bs-1,:) = kron(I,s{i});
304 Qsmp(:,KN+kix:KN+kix+bs-1) = kron(D{i+1},sigma{i});
307 Qspp(1:KN,1:KN) = Kwu;
309 inis = [iniw, zeros(1,N*sum(M(k+1:end)))];
311 % calculate fundamental matrix
312 Psis = FluidFundamentalMatrices (Qspp, Qspm, Qsmp, Qsmm, 'P', precision);
314 % step 4.3. calculate the performance measures
315 % ==========================================
317 while argIx<=length(varargin)
318 if any(ismember(eaten, argIx))
321 elseif strcmp(varargin{argIx},'stMoms
')
322 % MOMENTS OF THE SOJOURN TIME
323 % ~~~~~~~~~~~~~~~~~~~~~~~~~~~
324 numOfSTMoms = varargin{argIx+1};
325 % calculate waiting time moments
327 wtMoms = zeros(1,numOfSTMoms);
329 A = Qspp + Psis*Qsmp;
330 B = Qsmm + Qsmp*Psis;
334 bino = bino * (n-i+1) / i;
335 C = C + bino * Pn{i+1}*Qsmp*Pn{n-i+1};
339 wtMoms(n) = sum(inis*P*(-1)^n) / 2^n;
341 % calculate RESPONSE time moments
342 Pnr = {sum(inis*Pn{1})*sigma{k}}; %{sigmaL};
343 rtMoms = zeros(1,numOfSTMoms);
345 P = n*Pnr{n}*inv(-S{k}) + (-1)^n*sum(inis*Pn{n+1})*sigma{k} / 2^n;
347 rtMoms(n) = sum(P)+sum(pwu)*factorial(n)*sum(sigma{k}*inv(-S{k})^n);
351 elseif strcmp(varargin{argIx},'stDistr
')
352 % DISTRIBUTION OF THE SOJOURN TIME
353 % ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
354 stCdfPoints = varargin{argIx+1};
359 Psie = FluidFundamentalMatrices (Qspp-lambdae*eye(size(Qspp)), Qspm, Qsmp, Qsmm-lambdae*eye(size(Qsmm)), 'P', precision);
361 pr = (sum(pwu) + sum(inis*Psie)) * (1-sum(sigma{k}*inv(eye(size(S{k}))-S{k}/2/lambdae)^L));
363 A = Qspp + Psie*Qsmp - lambdae*eye(size(Qspp));
364 B = Qsmm + Qsmp*Psie - lambdae*eye(size(Qsmm));
367 C = C + Pn{i+1}*Qsmp*Pn{n-i+1};
371 pr = pr + sum(inis*P) * (1-sum(sigma{k}*inv(eye(size(S{k}))-S{k}/2/lambdae)^(L-n)));
377 elseif strcmp(varargin{argIx},'ncMoms
') || strcmp(varargin{argIx},'ncDistr
')
378 W = inv(-kron(sD-D{k+1},eye(M(k)))-kron(I,S{k}))*kron(D{k+1},eye(M(k)));
379 iW = inv(eye(size(W))-W);
380 w = kron(eye(N),sigma{k});
381 omega = inv(-kron(sD-D{k+1},eye(M(k)))-kron(I,S{k}))*kron(I,s{k});
382 if strcmp(varargin{argIx},'ncMoms
')
383 % MOMENTS OF THE NUMBER OF JOBS
384 % ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
385 numOfQLMoms = varargin{argIx+1};
386 % calculate queue length moments at departures
388 QLDPn = {inis*Psii{1}*w*iW};
390 A = Qspp + Psis*Qsmp;
391 B = Qsmm + Qsmp*Psis;
392 C = n*Psii{n}*D{k+1};
395 bino = bino * (n-i+1) / i;
396 C = C + bino * Psii{i+1}*Qsmp*Psii{n-i+1};
400 QLDPn{n+1} = n*QLDPn{n}*iW*W + inis*P*w*iW;
403 QLDPn{n+1} = (QLDPn{n+1} + pwu*w*iW^(n+1)*W^n)*omega;
405 % now calculate it at random time instance
407 qlMoms = zeros(1,numOfQLMoms);
408 iTerm = inv(ones(N,1)*pi - sD);
410 sumP = sum(QLDPn{n+1}) + n*(QLDPn{n} - QLPn{n}*D{k+1}/lambda(k))*iTerm*sum(D{k+1},2);
411 P = sumP*pi + n*(QLPn{n}*D{k+1} - QLDPn{n}*lambda(k))*iTerm;
415 qlMoms = MomsFromFactorialMoms(qlMoms);
418 elseif strcmp(varargin{argIx},'ncDistr
')
419 % DISTRIBUTION OF THE NUMBER OF JOBS
420 % ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
421 numOfQLProbs = varargin{argIx+1};
422 Psid = FluidFundamentalMatrices (Qspp, Qspm, Qsmp, sD0k, 'P', precision);
425 dqlProbs = (XDn+pwu*w)*omega;
426 for n=1:numOfQLProbs-1
427 A = Qspp + Psid*Qsmp;
428 B = sD0k + Qsmp*Psid;
431 C = C + Pn{i+1}*Qsmp*Pn{n-i+1};
435 XDn = XDn*W + inis*P*w;
436 dqlProbs = [dqlProbs; (XDn+pwu*w*W^n)*omega];
438 iTerm = inv(-(sD-D{k+1}));
439 qlProbs = lambda(k)*dqlProbs(1,:)*iTerm;
440 for n=1:numOfQLProbs-1
441 P = (qlProbs(n,:)*D{k+1}+lambda(k)*(dqlProbs(n+1,:)-dqlProbs(n,:)))*iTerm;
442 qlProbs = [qlProbs; P];
444 Ret{end+1} = sum(qlProbs,2)';
448 error ([
'MMAPPH1NPPR: Unknown parameter ' varargin{argIx}])
453 % step 3. calculate the performance measures
454 % ==========================================
457 while argIx<=length(varargin)
458 if any(ismember(eaten, argIx))
461 elseif strcmp(varargin{argIx},
'stMoms') || strcmp(varargin{argIx},
'stDistr')
462 Kw = Qwpp{k}+Qwpz{k}*inv(-Qwzz{k})*Qwzp{k} + Psiw{k}*Qwmp{k};
463 AM = []; BM = []; CM = []; DM = [];
465 AM = blkdiag(AM, kron(ones(N,1),kron(eye(M(i)),s{k})));
466 BM = blkdiag(BM,S{i});
468 DM = blkdiag(DM,kron(D{k+1},eye(M(i))));
470 Z = [Kw, [AM;zeros(N*M(k),size(AM,2))]; zeros(size(BM,1),size(Kw,2)), BM];
471 z = [zeros(size(AM,1),1); kron(ones(N,1),s{k}); CM];
472 iniw = [q0{k}*Qwmp{k}+qL{k}*Qwzp{k}, zeros(1,size(BM,1))];
473 zeta = iniw/sum(iniw*inv(-Z)*z);
474 if strcmp(varargin{argIx},
'stMoms')
475 % MOMENTS OF THE SOJOURN TIME
476 % ~~~~~~~~~~~~~~~~~~~~~~~~~~~
477 numOfSTMoms = varargin{argIx+1};
478 rtMomsH = zeros(1,numOfSTMoms);
480 rtMomsH(i) = factorial(i)*zeta*inv(-Z)^(i+1)*z;
482 Ret{end+1} = rtMomsH;
483 elseif strcmp(varargin{argIx},
'stDistr')
484 % DISTRIBUTION OF THE SOJOURN TIME
485 % ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
486 stCdfPoints = varargin{argIx+1};
489 rtDistr = [rtDistr, zeta*inv(-Z)*(eye(size(Z))-expm(Z*t))*z];
491 Ret{end+1} = rtDistr;
494 elseif strcmp(varargin{argIx},
'ncMoms') || strcmp(varargin{argIx},
'ncDistr')
501 F(kix:kix+bs-1,kix:kix+bs-1) = kron(D{k+1},eye(M(i)));
502 L(kix:kix+bs-1,kix:kix+bs-1) = kron(sD0k,eye(M(i))) + kron(I,S{i});
504 L(kix:kix+bs-1,N*sum(M(1:k-1))+1:end) = kron(I,s{i}*sigma{k});
506 B(kix:kix+bs-1,N*sum(M(1:k-1))+1:end) = kron(I,s{i}*sigma{k});
510 R = QBDFundamentalMatrices (B, L, F,
'R', precision);
511 p0 = [qL{k}, q0{k}*kron(I,sigma{k})];
512 p0 = p0/sum(p0*inv(eye(size(R))-R));
513 if strcmp(varargin{argIx},
'ncMoms')
514 % MOMENTS OF THE NUMBER OF JOBS
515 % ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
516 numOfQLMoms = varargin{argIx+1};
517 qlMoms = zeros(1,numOfQLMoms);
519 qlMoms(i) = sum(factorial(i)*p0*R^i*inv(eye(size(R))-R)^(i+1));
521 Ret{end+1} = MomsFromFactorialMoms(qlMoms);
522 elseif strcmp(varargin{argIx},
'ncDistr')
523 % DISTRIBUTION OF THE NUMBER OF JOBS
524 % ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
525 numOfQLProbs = varargin{argIx+1};
527 for i=1:numOfQLProbs-1
528 qlProbs = [qlProbs; p0*R^i];
530 Ret{end+1} = sum(qlProbs,2)
';
534 error (['MMAPPH1NPPR: Unknown parameter
' varargin{argIx}])