MathGroup Archive 1999

[Date Index] [Thread Index] [Author Index]

Search the Archive

Scheduling algorithms

  • To: mathgroup at
  • Subject: [mg16922] Scheduling algorithms
  • From: Eric Strobel <EStrobel at>
  • Date: Thu, 8 Apr 1999 02:32:33 -0400
  • Sender: owner-wri-mathgroup at

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
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 

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
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);
flight will change as targets move; some targets have higher priority than 

Clearly, I don't expect someone to hand me a notebook which solves the
thing.  (If anyone has such a notebook, PUBLISH!!!  I get the impression
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.

  • Prev by Date: Re: Problem Display Format
  • Next by Date: Mie Scattering w/Mathematica
  • Previous by thread: How to do Simpson's Rule Riemann Sums with Mathematica 3.0?
  • Next by thread: Re: Scheduling algorithms