Priority Queue Waiting Time

Problem

Non-preemptive priority M/G/1 queue. lambdas, mean_services and var_services are ordered from highest priority (index 0) to lowest. Return the expected waiting time for class class_index:

W_k = sum over i of lam_i * (var_i + mean_i^2) / (2 * (1 - sigma_{k-1}) * (1 - sigma_k))

where sigma_j is the cumulative utilization through class j. Return -1.0 when the denominator is nonpositive and 0.0 for invalid indices.

Hint

Low-priority classes are slowed by the work of all higher-priority classes.

Test cases

case 1

in: [[1,1],[0.2,0.2],[0.04,0.04],0]

expected: 0.10000000000000002

case 2

in: [[1,1],[0.2,0.2],[0.04,0.04],1]

expected: 0.1666666666666667

case 3

in: [[1,1],[0.6,0.2],[0.36,0.04],1]

expected: 5.000000000000001

case 4

in: [[2,2],[0.6,0.6],[0.36,0.36],1]

expected: 5.142857142857144

case 5

in: [[],[],[],0]

expected: 0

Starter codePython

def priority_queue_waiting_time(lambdas, mean_services, var_services, class_index):
    # Your code here
    pass

5 test cases · run your code against them in the editor