Scheduling and Critical Path Algorithm: an Interactive Gizmo

Scheduling and Critical Path Algorithm

The applet below is designed to help practice scheduling and get comfortable with the notions of task, critical path, priority list, precedence relation and task processors. Tasks and precedence relations combine into directed graphs, or digraphs. In a digraph the function of the two vertices joined by an edge are distinct: the edge goes from one to the other. This is reflect in the depiction of digraph where edges are drawn as arrows pointing from of the vertices to another. In the applet, the digraphs always begin with the Start vertex and follow to the End vertex. These two are always present and can't be edited out.

The instructions for using the applet are available on a separate page and can also be read under the first tab directly in the applet. An older version of the applet is still available on the web.

This applet requires Sun's Java VM 2 which your browser may perceive as a popup. Which it is not. If you want to see the applet work, visit Sun's website at https://www.java.com/en/download/index.jsp, download and install Java VM and enjoy the applet.

What if applet does not run?

(This applet was created to accompany Excursions in Modern Mathematics, Seventh Edition, by Peter Tannenbaum © Pearson Education. Reproduced with permission.)

Terminology

Directed graph - a collection of vertices joined by directed edges. Here we only consider the digraphs with with two special vertices, Start and End.

Directed edge - an ordered pair of vertices, shown graphically as an arrow from the first vertex in the pair to the second.

Precedence relation - a directed edge whose vertices are conceived as tasks to be executed.

Task - a synonym of job, something that has to be executed. Each task can be executed by a single processor in a required period of time, a task duration.

Priority list - a sequence of tasks listed in a desired order of execution.

Processor - depending on the context, an organizational unit capable of executing tasks on priority list.

Critical path of a vertex - the longest (in sense of the total sum of the tasks durations) from that vertex to the End.

Critical path of a digraph - is the critical path of the Start vertex.

The tasks are scheduled for execution on one or more processors according to the existing precedence relations and a priority list. Precedence relations specify constraints that could not be violated. During the process of scheduling a priority list is taken into account within the constraints specified by the precedence relations. The scheduling algorithm may, in principle, produce different schedules for different priority lists but the same set of precedence relations.

71535703