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