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