Dispatching Problem: Lookahead Policy (LH)
Let us continue with the size-aware setting, i.e.
service time of the new job and the backlogs are known
to dispatcher.
Lookahead (LH) policy takes also the job arriving next (in the near future)
into account when evaluating the different actions.
- Basic idea:
- In FPI,
we evaluate the cost of deviating
from the basic policy only for the new job.
- In LH, one considers the assignment of
both the current and the next arriving job [1].
This is similar to two policy iteration rounds.
- The specifics of the next job are unknown, so
an expectation
is computed!
- A good policy to start from is
the static SITA policy
- Resulting policy is near-optimal [1,2]
- Resulting policy:
- Animation on the right illustrates the LH dispatching policy for an example system:
- Two identical FCFS servers and exponentially distributed service times
- Objective is the minimize the mean sojourn time
- 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 when the system is sufficiently empty (for all jobs)
- LH employs controlled unbalancing that enables
short jobs to pass the long ones (cf. SITA)
- Actions of LH are very similar to those of the
optimal policy!.
|
|
Fig. LH policy
|
References:
| [1] |
E. Hyytiä,
Lookahead Actions in Dispatching to Parallel Queues,
in 31st International Symposium on Computer Performance,
Modeling, Measurement and Evaluation (IFIP Performance 2013),
September 2013, Vienna, Austria.
|
| [2] |
E. Hyytiä,
Optimal Routing of Fixed Size Jobs to Two Parallel Servers,
INFOR: Information Systems and Operational Research, 2013.
|
