example_lukumar_reentrant.m

%% Lu-Kumar Unstable Re-entrant Line Example
%
% This script demonstrates the Lu-Kumar re-entrant line network, a classic
% example showing that queueing networks can exhibit instability even when
% individual station utilizations are below 100%.
%
% The network has 2 stations and 4 job classes:
%   - Jobs enter as Class 1, served at Station 1
%   - Switch to Class 2, served at Station 2
%   - Switch to Class 3, served at Station 2 (same station, different class)
%   - Switch to Class 4, served at Station 1 (re-entry)
%   - Exit the network
%
% Key insight: Under FCFS, the network is stable when utilization < 1.
% Under certain priority policies (like giving priority to returning jobs),
% the network can become unstable due to virtual bottleneck effects.
%
% Reference:
%   Lu, S.H. and Kumar, P.R. (1991), "Distributed Scheduling Based on Due
%   Dates and Buffer Priorities", IEEE Trans. Automatic Control.
 
clear;
fprintf('=== Lu-Kumar Re-entrant Line Example ===\n\n');
 
%% Compare FCFS vs HOL Scheduling
fprintf('Creating models with different scheduling strategies...\n');
 
model_fcfs = gallery_lukumar_reentrant('FCFS');
model_hol = gallery_lukumar_reentrant('HOL');
model_ps = gallery_lukumar_reentrant('PS');
 
%% Print network information
fprintf('\nNetwork parameters:\n');
fprintf('  Arrival rate (lambda): 0.45\n');
fprintf('  Mean service time at Station 1 (Class 1): 1.0\n');
fprintf('  Mean service time at Station 2 (Class 2): 1.0\n');
fprintf('  Mean service time at Station 2 (Class 3): 1.0\n');
fprintf('  Mean service time at Station 1 (Class 4): 1.0\n');
fprintf('  Station 1 utilization: 0.90\n');
fprintf('  Station 2 utilization: 0.90\n\n');
 
%% Solve with JMT (simulation)
fprintf('Solving with JMT simulation...\n\n');
options = lineDefaults;
options.seed = 23000;
options.samples = 5e4;
 
%% FCFS Solution
fprintf('--- FCFS Scheduling (Stable) ---\n');
solver_fcfs = JMT(model_fcfs, options);
AvgTable_fcfs = solver_fcfs.getAvgTable();
disp(AvgTable_fcfs);
 
%% HOL Priority Solution
fprintf('\n--- HOL Priority Scheduling ---\n');
fprintf('Priority: Class4 > Class1 at Station1, Class2 > Class3 at Station2\n');
fprintf('(This priority policy can lead to instability in certain parameter regimes)\n\n');
solver_hol = JMT(model_hol, options);
AvgTable_hol = solver_hol.getAvgTable();
disp(AvgTable_hol);
 
%% PS Solution (for comparison)
fprintf('\n--- Processor Sharing (Stable) ---\n');
solver_ps = JMT(model_ps, options);
AvgTable_ps = solver_ps.getAvgTable();
disp(AvgTable_ps);
 
%% Summary
fprintf('\n=== Summary ===\n');
fprintf('The Lu-Kumar network demonstrates that scheduling discipline matters!\n');
fprintf('Even with station utilizations at 90%%, different scheduling policies\n');
fprintf('can lead to dramatically different queue lengths and response times.\n\n');
fprintf('Key observations:\n');
fprintf('1. FCFS is always stable when utilization < 1 in open networks\n');
fprintf('2. PS is also stable under the same conditions\n');
fprintf('3. Priority policies can create "virtual bottlenecks" that cause\n');
fprintf('   queue buildup even when physical utilization is below 100%%\n');