Re: Scheduling algorithms

• To: mathgroup at smc.vnet.net
• Subject: [mg16995] Re: [mg16922] Scheduling algorithms
• From: "Hans J.-I. Michel" <hans at dorsai.org>
• Date: Sat, 10 Apr 1999 02:13:32 -0400
• Sender: owner-wri-mathgroup at wolfram.com

```-----Original Message-----
From: Eric Strobel <EStrobel at schafercorp.com>
To: mathgroup at smc.vnet.net
Subject: [mg16995] [mg16922] Scheduling algorithms

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

After some thought I am choosing the least complicated path. I will point
you in what I hope is a good direction.

My assumption is by OR you mean Operations Research (OR).

Your problem is sometimes called Job Shop problems (Flow Shop, Body Shop,
Time Table problem, etc.).

In terms of Mathematica and a potential solution path to your particular
problem; I highly recommend [Steven Skiena. Implementing Discrete
Mathematics: Combinatorics and Graph Theory with Mathematica.
Addison-Wesley: 1990. (ISBN 0-201-50943-1)]. I think many, if not all, of
his Notebooks/Packages are available in DiscreteMath`Combinatorica`.
Of interest to you should be the traveling salesman problem. (Lin's
Algorithm)

Furthermore try James Freeman. Simulating a Basic Genetic Algorithm. The
Mathematica Journal 1993 (Spring): 3(2):52--56. The package is called
GeneticAlgorithm.m. Should be available in MathSource.

Crude break down of the field but not entirely accurate.
Optimization

Static Cases

Graphs -> Directed Graphs -> etc. (All Weighted)

(Make use Linear Programming, as in the example you provided, that could be
solve using things learned in a Linear Algebra or Discrete Math class.)

Dynamic Cases

Find optimal solutions using randomization (psuedo-random) using heuristic
algorithms. Basically choose random weights, then apply appropriate static
case algorithm. Usually using Genetic Algorithms, or Markov Chains, or
Simulated Annealing, etc..

(Makes use of Dynamic Programming, Stochastic Processes to provide the
randomization or probability vectors using things learned in Combinatory
Algebra or Applied Math class.)

Check out
(Not Mathematica related)
Genetic Algorithm Digest http://www.aic.nrl.navy.mil/galist

Operations Research (OR) Library
anonymous ftp to mscmga.ms.ic.ac.uk
Web http://mscmga.ms.ic.ac.uk

Optimization and 2LP programming
http://www.brooklyn.cuny.edu/ search on 2LP and you'll get the lab.
Check out Ken McAloon and Carol Tretkoff. Optimization and Computational
Logic. John Wiley & Son: 1996.

If you having a hard time understanding the notation in this field. You are
on the right track, trying many examples will help in eventually
understanding Combinatory Algebras.

Good Luck

```

• Prev by Date: ListDensityPlot[ ] and DensityGraphics
• Next by Date: ListDensityPlot[ ] and DensityGraphics
• Previous by thread: Scheduling algorithms
• Next by thread: Mie Scattering w/Mathematica