Scheduling monitoring tasks

As mentioned earlier, our goal is to schedule the allocated
monitoring tasks among *M* parallel
monitoring processes with the aim of minimizing the total delay
between the ideal time instants and the actual scheduled time
instants when a monitoring task must be executed.

Let page *i* be allocated *x*_{i} number of monitoring tasks
in an optimal resource allocation. Also, suppose the time instants
at which these *x*_{i}
monitoring tasks should be employed are
*t*_{1}, *t*_{2},
*t*_{3},..., *t*_{x}i, as
identified in the resource allocation phase. Let
be the average
fetching time for the
*i*^{th} page. The
scheduling problem can be easily mapped to parallel shop scheduling
problem. In this problem, each *job* has to be processed on
exactly one of *M* identical
*machines*. Each monitoring task could be regarded as a
*job* whereas the monitoring processes are equivalent to
machines. Suppose there are a total of *n* such jobs. In scheduling problems, the
time at which a job becomes available for processing is called the
*release time* (
) and the time for
which it needs a machine is called the *processing time*. So
in our case, ideal *monitoring* time instants
*t*_{1}, *t*_{2},
*t*_{3},..., *t*_{x}i would be the
*release times* and fetching times of pages correspond to
processing times (*p*_{j})
for jobs. Our goal is to minimize the delay *d*_{i} between ideal monitoring
time instant
and actual time
instant *s*_{i} of
scheduling. In our case all the jobs are equally important as there
is no weight assigned with each *monitoring*. So our problem
can be formulated in scheduling notation as
(
denotes the completion
time for job *j*), meaning that
*R* jobs of non-trivial release
times are available for scheduling at *M* machines with goal of minimizing the
average completion time. Minimizing the average completion time
leads to minimization of average delay time, because the total
completion time is

Cm_{i} |
|||

As
and
*p*_{i} are
constants, minimizing average completion time is same as minimizing
delay time. Note that
is the same as *s*_{i} + *p*_{i} because of
*non-preemptive* scheduling. Unfortunately even the simpler
problem
*R*| 1| *rel*_{j}0|*Cm*_{j} has been proved
to be *NP-Complete* [11]. So we
have to look for *approximation algorithms*. For completion
time problem there is an 1.58-approximation algorithm [11] which we used in our experiments as a
heuristic for optimizing average delay time (an approximation for
average completion time does not necessarily translate to the same
approximation for average delay time; the latter is harder to
approximate).