Project: DiSNet

Summary

One of the complex decision problems in the manufacturing and services
industry is  that of the  task  scheduling  for each  of the available
resources. Typically,  the time  available for  decision making is too
short, given the processing times of the individual operations. On the
other hand, if the system dimension is high and the number of tasks to
execute varies along time as function of dynamic arrival and departure
processes,  determining  the  optimal  decisions for  some performance
criterion may become  cumbersome.  The reason  being the complexity of
this type of problems, even  in situations where  time is not a strong
computational constraint.

For this type of problems, a  centralized decision-maker would have to
process  great  amounts  of  information.  On the other hand, the time
needed to do  it and then  distribute the information  relative to the
decisions  may be  insurmountable.  Therefore,  the usual  strategy to
define  scheduling policies  has mainly concentrated  in decentralized
decision schemes.  In this situation,  each server determines  its own
processing sequence as a function of local  information concerning the
tasks it is requested to process.

The question posed  for this type of strategy  is to know what type of
local information should be used when  trying to optimize the system's
performance  from  a  macroscopic  point  of  view  and  how  is  such
information to be used.

The  major  part  of  the  available  literature  for local scheduling
problems concentrates on work-conserving policies. That is, as long as
there exists at least one task to be  processed, the available servers
execute  it.  There  is  some  literature   suggesting  the  need  and
usefulness,  from  the  achievable  performances'  point  of view,  of
considering non  work-conserving  policies, where idleness  of servers
may be permitted at times where there is service to perform.

The main  reasons that  justify this type of  policies have to do with
the need to  filter bursts of  requests  from some sources  (of tasks)
which, if  served in their  totality, may  induce disturbances  in the
quality of service given to other better-behaved sources. On the other
hand,  serving bursts  of tasks  may induce  a higher  variance in the
overall  system,  negatively  affecting the  performance of  the whole
network of servers.

The main  objective of  this project  is to  develop local  scheduling
policies for systems modeled by  networks of queues, as is the case of
manufacturing systems  and data transmission  networks. It is aimed at
defining a super-class of local scheduling policies which contains non
work-conserving and work-conserving policies as sub-classes.

Once such a class  is defined and properly  parameterized,  it will be
possible to formulate  optimization problems whose  solutions may help
in understanding  the real advantage  of non work-conserving policies.
That is,  what is the  adequate degree  of work-conservation  for some
system configurations, as well as in what sense a system configuration
is determinant of the local  scheduling policy's character in terms of
its degree of work-conservation?