(a) Explain M|G|1 queuing system. Obtain Pollaczek-kinchine formula. (15 marks) (b) Use MODI method to solve the above…

(a) M|G|1 queue and the Pollaczek–Khinchine formula

In Kendall's notation M means Poisson arrivals at rate λ, G means independent service times S with a general distribution (mean 1/μ, variance σ²), and 1 means a single server. The discipline is FIFO with unlimited capacity. The traffic intensity is ρ = λ/μ and a steady state needs ρ < 1. Service is not memoryless, so the number in system is observed just after departures, where it forms an embedded Markov chain.

Let Xₙ be the number left behind by the n-th departure and Aₙ₊₁ the arrivals during the next service. With U = 1 if Xₙ > 0 and 0 otherwise,

Xₙ₊₁ = Xₙ − U + Aₙ₊₁.

Given S, A is Poisson(λS), so E(A) = ρ and E(A²) = ρ + λ²(σ² + 1/μ²) = ρ + λ²σ² + ρ². In steady state E(Xₙ₊₁) = E(Xₙ) = L gives E(U) = ρ. Squaring the recursion, with U² = U, XU = X and A independent of X and U:

0 = E(U) + E(A²) − 2L + 2L·ρ − 2ρ·ρ, so 2L(1 − ρ) = 2ρ − ρ² + λ²σ².

L = ρ + (λ²σ² + ρ²) / [2(1 − ρ)], and L_q = (λ²σ² + ρ²) / [2(1 − ρ)].

Poisson arrivals see time averages (PASTA), so departure-epoch means equal long-run means. Little's law gives W_q = L_q/λ and W = W_q + 1/μ. Check: for M|M|1, σ² = 1/μ² and L_q = ρ²/(1 − ρ); for M|D|1, σ² = 0 and L_q is half of that, so congestion grows with the variability of service.

(b) Transportation problem by the MODI method

Supply is 200 and demand is 185, so add a dummy store V with demand 15 and zero costs.

Initial solution by Vogel's method (cost 1510): A–I 25, A–II 5, A–III 20, B–III 55, B–V 15, C–II 30, D–III 30, D–IV 20. These are 8 cells = m + n − 1, so it is non-degenerate.

Iteration 1. Put u_A = 0 and use cᵢⱼ = uᵢ + vⱼ on occupied cells: v_I = 4, v_II = 6, v_III = 8, u_B = 2, u_D = 5, u_C = −2, v_V = −2, v_IV = 3. The net evaluations Δ = c − (u + v) of the empty cells are A–IV 10, A–V 2, B–I 7, B–II 3, B–IV 3, C–I 12, C–III 4, C–IV 12, C–V 4, D–I 0, D–II 0 and D–V −3. D–V enters. The loop is D–V(+), D–III(−), B–III(+), B–V(−), so θ = min(30, 15) = 15. The allocations become D–V 15, D–III 15, B–III 70, and B–V leaves.

Iteration 2. Now u = (0, 2, −2, 5) and v = (4, 6, 8, 3, −5). Every Δ is ≥ 0 (A–IV 10, A–V 5, B–I 7, B–II 3, B–IV 3, B–V 3, C–I 12, C–III 4, C–IV 12, C–V 7, D–I 0, D–II 0), so the solution is optimal.

Optimal plan: A sends 25 to I, 5 to II and 20 to III; B sends 70 to III; C sends 30 to II; D sends 15 to III and 20 to IV, with 15 units left unshipped from D (dummy).

Minimum cost = 4(25) + 6(5) + 8(20) + 10(70) + 4(30) + 13(15) + 8(20) = Rs 1465. The zero Δ at D–I and D–II show alternative optima of equal cost.

(c) Two-phase simplex

Standard form: 4x₁ + 6x₂ + 3x₃ + s₁ = 8; 3x₁ − 6x₂ − 4x₃ + s₂ = 1; 2x₁ + 3x₂ − 5x₃ − s₃ + a₁ = 4.

Phase I: minimise a₁. In the starting basis (s₁, s₂, a₁) the entering variable is x₂. The ratios are 8/6 and 4/3, a tie, so a₁ leaves.

After this pivot a₁ = 0 is non-basic, so a feasible basis exists and the a₁ column is dropped.

The basic solution is s₁ = 0, s₂ = 9, x₂ = 4/3 and x₁ = x₃ = 0.

Phase II: maximise z = 2x₁ + x₂ + x₃ from this basis, where z = 4/3. The zⱼ − cⱼ values are −4/3 for x₁, −8/3 for x₃ and −1/3 for s₃, and zero for the basic variables and s₂.

• x₃ enters; the only positive entry in its column is 13 in the s₁ row, with ratio 0, so s₁ leaves (a degenerate pivot, z unchanged).
• x₁ enters; the ratios are 9/7 (s₂ row) and 2 (x₂ row), so s₂ leaves.

The final basis is x₃ = 0, x₁ = 9/7 and x₂ = 10/21. All zⱼ − cⱼ are non-negative (16/39 for s₁, 4/21 for s₂, 29/273 for s₃), so it is optimal.

x₁ = 9/7, x₂ = 10/21, x₃ = 0, maximum z = 64/21 ≈ 3.05. Check: 4(9/7) + 6(10/21) = 8, 3(9/7) − 6(10/21) = 1 and 2(9/7) + 3(10/21) = 4, so all three constraints bind and x₃ is basic at zero level.