The BB approximation

The BB approximation is based on the assumption that the ``improvement'' of priority scheduling over FCFS is similar between a single server system and a multiserver system, specifically (4.2). However, our study in Section 4.4 implies that the improvement can be quite different, since prioritizing small jobs has the same effect as having multiple servers. Figure 4.7 illustrates the error in BB quantitatively.

In rows 1-2 of Figure 4.7, the job sizes have exponential distributions. In this case, for all classes, BB is exact when all the classes have the same mean size ($\alpha=1$), but it underestimates the mean delay when the higher priority classes are small ($\alpha < 1$) or large ($\alpha > 1$). This can be explained as follows. BB is based on the observation that the ``improvement'' of priority scheduling over FCFS under multiple servers is similar to the case of a single server (recall equation (4.2)). When all the classes have the same mean, priority scheduling provides the same mean delay as FCFS, regardless of the number of servers; hence (4.2) is exact, and so is BB. When high priority classes are small, priority scheduling improves the mean delay over FCFS because it allows small jobs to avoid waiting behind large jobs. However, the improvement under multiple servers is smaller than in the case of a single server, because having multiple servers also allows small jobs to avoid waiting behind large jobs under FCFS. Since BB assumes that the improvement is the same, it underestimates the mean delay. When class 1 is larger than class 2, prioritizing class 1 worsens the mean delay. However, the penalty due to prioritization under a single server is smaller than under multiple servers, since with a single server FCFS also forces large jobs to block small jobs, but multiple servers often allow small jobs to avoid waiting behind large jobs under FCFS. Again, since BB assumes that the improvement is the same, it underestimates the mean delay.

We can also observe that the error in BB is smaller under high load than low load ($\rho=0.3$, row 1). This is because under high load single server systems and multiserver systems behave similarly. Overall, the error in BB can be as high as 50% under low load ($\rho=0.3$) and 20% under high load ($\rho=0.8$).

For non-exponential job size distributions, BB is no longer exact even when all classes have the same job size distributions, as shown in Figure 4.7 rows 3-4. For $C^2=8$, preemptive priority scheduling and FCFS yield different mean delay. For example, for job size distributions with decreasing failure rate, low priority jobs with longer remaining time are more likely to be preempted by higher priority jobs, which can improve the overall mean delay. However, this improvement differs between single server systems and multiserver systems. BB therefore can yield error in predicting the mean delay.