- Model:
- Two identical FCFS servers and exponentially distributed service times
- Size-aware setting: service time of the new job and the backlogs are known
- Objective is the minimize the mean sojourn time
- Instead of the first policy iteration (FPI), we carry out the Lookahead (LH) [1]:
- In FPI, actions evaluated involve only the current new job
- In LH, one considers the assignment of
both the current and the next arriving job
- The specifics of the latter are unknown
- A good starting point is the static SITA policy
- Resulting policy is near-optimal [1,2]
- Animation on the right illustrates the LH dispatching policy:
- The service time of the arriving job is varied (from small to high)
- The x-axis corresponds to backlog in queue 1, and y-axis to backlog in queue 2
- In solid brown area, LH assigns the new job to queue 1, and in other areas
to queue 2.
- The different tones in the latter are related to the performance difference
between the two decisions.
- Observations:
- Very short jobs are always assigned to the shorter queue (makes sense!)
- The shorter queue is preferred also whenthe system is sufficiently empty (for all jobs)
- When backlogs are a bit longer, the new job may be assigned also to the longer queue:
"Do not put two elephants in the same queue!"
- LH employs controlled unbalancing that enables
short jobs to pass the long ones (cf. SITA)
|
|
Fig. LH policy
|
