Path: utzoo!attcan!uunet!cs.utexas.edu!wuarchive!zaphod.mps.ohio-state.edu!sol.ctr.columbia.edu!cica!iuvax!ux1.cso.uiuc.edu!ux1.cso.uiuc.edu!m.cs.uiuc.edu!gillies
From: gillies@m.cs.uiuc.edu
Newsgroups: comp.theory
Subject: Re: Scheduling Info sought
Message-ID: <37800017@m.cs.uiuc.edu>
Date: 21 Oct 90 20:01:00 GMT
References: <1850@shodha.enet.dec.com>
Lines: 59
Nf-ID: #R:shodha.enet.dec.com:1850:m.cs.uiuc.edu:37800017:000:1989
Nf-From: m.cs.uiuc.edu!gillies    Oct 21 15:01:00 1990


/* ---------- "Scheduling Info sought" ---------- */

Hi,

I would like to do some research about scheduling resources.  Say for example, 
you have a set of resources that need to be used everyday.  Some of the 
resources work faster than others and some have more space than others.  
		^^^    ^^    ^^			 ^^   ^^^
	       "Uniform Resources"		"Variable-Sized"

Sometimes the resources break down and need to be fixed and other times they 
simply need to be taken down for preventative maintenance.
		^^^
	i.e., you have tasks which represent preventative maintenance.


I'm sure people have addressed this problem before.  Can anyone send me some 
references about the current research going on in this field?
--------------------------------------------------------------

First, let me say that this field is very old (30+ years).  There are
at least 500 papers on this and related subjects.  Second, there is
not a good current survey on resource scheduling.  Most of the
previous work has been done by management scientists in business
schools and transportation economists -- i.e., not computer
scientists.  I hope some day to write a good survey on the computer
work, emphasizing esp. the theoretical analysis of heuristics.  Until
then, you can look at #131 below (a good general survey on scheduling,
including resource scheduling).  My own paper (below) tells how to
analyze the worst-case performance of an arbitrarily complicated
resource scheduling problem, if precedence constraints are included,
and a greedy heuristic is used.



%Z     131
%X R
%A E. L. Lawler
%A J. K. Lenstra
%A A. H. G. Rinnooy Kan
%A D. B. Shmoys
%T Sequencing and Scheduling:  Algorithms and Complexity
%B Centre for Mathematics and Computer Science
%C Amsterdam
%D 1989

(And now a personal plug for my own work)

%Z     36
%X A
%A Donald W. Gillies
%A Jane W.-S. Liu
%T Greed In Resource Scheduling
%J 10th Annual IEEE Symposium on Real-Time Systems
%D December, 1989
%P 285 294
%V 10
%P beats me