>As seen on:
>https://www.cut-the-knot.org/Curriculum/Combinatorics/CriticalPath.shtml
>
>There is an applet which determines an optimal schedule for
>a list of tasks based on a list of task priorities. The result is not necessarily an optimal schedule.
>
>There is no information on the algorithm to do this, and I
>am interested in learning how that is done. Building the
>network diagram is a highly documented topic, but finding
>any information on converting the tasks to a schedule with
>finite resources to perform the task has been difficult.
The applet has been written for
P. Tannenbaum, Excursions in Modern Mathematics, Prentice-Hall, 2004 (5th edition)
The algorithm is also described in
For All Practical Purposes by COMAP, 2001 (5th edition)
>I would like to be pointed either to the actual algorithm,
>code or any other papers that address this issue.
>
>My guess is that for each item in the priority list, every
>item in the critical path to that task is added to the queue
>for the active resource. The active resource is selected by
>comparing the lengths of scheduled tasks and choosing the
>shortest.
It is simpler. The tasks could be in one of four states: ineligible, ready, in execution, completed. Whenever a processor becomes available, the algorithm selects the first of the ready tasks and puts it in execution on that processor. For a given graph, the resulting schedule may (and probably will) depend on the priority list.
Printer-friendly copy
Email this topic to a friend
