Scheduling algorithms
- To: mathgroup at smc.vnet.net
- Subject: [mg16922] Scheduling algorithms
- From: Eric Strobel <EStrobel at schafercorp.com>
- Date: Thu, 8 Apr 1999 02:32:33 -0400
- Sender: owner-wri-mathgroup at wolfram.com
First, let me preface things with a paraphrase of a rather famous Star Trek
line: "Dammit Jim, I'm a physicist, not an OR expert!!!"
I have a task scheduling problem to handle. I've looked around the Web and
found that there is an OR problem which is sort of similar (maybe it maps
exactly and I just don't understand the terminology) -- it is generally
represented as factory floor job scheduling. A search of MathSource (and
the
whole Mathematica site) has turned up nothing I recognize as applying. I'd like to
be able to solve this in Mathematica so I can easily educate others about the
solution.
A simplified version of the problem is as follows: Consider three machines
(A,B,C) given five identical tasks. A can perform a task in 4 seconds, B in
15, C in 20. Resource usage is measured by the aggregate runtime of the
machines. The first guess schedule might be to try to let every machine
stay
as busy as possible (I believe that's termed "greedy"). Other strategies
also suggest themselves. I tabulate 3 below... (obviously you'll want to
view with a fixed-width font)
Tasks for Cum. End
A B C runtime time
--- --- --- ------- ----
3 1 1 47 20
4 1 0 31 16
5 0 0 20 20
Depending upon the relative importance of resource utilization or speed of
completion, one would choose either the third or the second scheduling.
There are at least two complications beyond this. One, even for a single
machine, both the preparation time for the task and the duration of the work
can vary with time (in a manner which can be determined). Second, some
machines are not as resource limited (think of some machines running on
batteries while others are plugged into the wall).
Analogies that spring to mind are: 1) scheduling a group of telescopes (such
as the twin Keck telescopes) -- fainter objects require longer integration
times; there are slew/pointing times involved; and there are instrument
change times involved. 2) artillery scheduling -- more distant targets have
greater time-of-flight; if you've adjusted your fire for weather/wind,
hitting other targets nearby the first should be quicker than if you have to
slew the gun to a completely different direction (i.e. small changes in the
task have a qualitatively different 'prep' time than large changes);
time-of-
flight will change as targets move; some targets have higher priority than
others...
Clearly, I don't expect someone to hand me a notebook which solves the
entire
thing. (If anyone has such a notebook, PUBLISH!!! I get the impression
that
full treatment of this is a problem of long-standing in the OR field...)
But, if anyone can hook me up with notebooks which can get me up to speed/
point me in the right direction/etc., that would be greatly appreciated.
- Eric.