We will need a primitive set to represent the tasks of the project. We can add such a set to the model using the set definition:

SETS:

  TASKS: TIME, ES, LS, SLACK;

ENDSETS

We have associated four attributes with the TASKS set. The definitions of the attributes are:

TIME

Time to complete the task

ES

Earliest possible start time for the task

LS

Latest possible start time for the task

SLACK

Difference between LS and ES for the task

The TIME attribute is given to us as data. We will compute the values of the remaining three attributes. If a task has a 0 slack time, it means the task must start on time or the whole project will be delayed. The collection of tasks with 0 slack time constitute the critical path for the project.

In order to compute the start times for the tasks, we will need the precedence relations. The precedence relations can be viewed as a list of ordered pairs of tasks. For instance, the fact that the DESIGN task must be completed before the FORECAST task could be represented as the ordered pair (DESIGN, FORECAST). Creating a two-dimensional derived set on the TASKS set will allow us to input the list of precedence relations. Specifically, we add the derived set definition PRED:

SETS:

  TASKS: TIME, ES, LS, SLACK;

  PRED( TASKS, TASKS);

ENDSETS

Next, we can input the TASKS set and task times in the data section by including:

DATA:

TASKS,  TIME =

  DESIGN    10

  FORECAST  14

  SURVEY     3

  DUMMY      0

  PRICE      3

  SCHEDULE   7

  COSTOUT    4

  TRAIN     10

;

ENDDATA

The set PRED is the sparse derived set with an explicit listing that we want to highlight in this example. The set is a subset derived from the cross of the TASKS set upon itself. The set is sparse because it contains only 8 out of a possible 49 members found in the complete cross of TASKS on TASKS. The set is said to be an "explicit list" set, because we will explicitly list the members we want included in the set. Explicitly listing the members of a sparse set may not be convenient in cases where there are thousands of members to select from, but it does make sense whenever set membership conditions are not well defined and the sparse set size is small relative to the dense alternative. Adding the initialization of PRED to the data set give us:

DATA:

TASKS,  TIME =

  DESIGN    10

  FORECAST  14

  SURVEY     3

  DUMMY      0

  PRICE      3

  SCHEDULE   7

  COSTOUT    4

  TRAIN     10

;

PRED =

   DESIGN, FORECAST,

   DESIGN, SURVEY,

   FORECAST, DUMMY

   FORECAST, SCHEDULE,

   SURVEY, PRICE,

   SCHEDULE, COSTOUT,

   PRICE, TRAIN,

   COSTOUT, TRAIN,

   DUMMY, PRICE

;

ENDDATA

Keep in mind that the first member of this set is the ordered pair (DESIGN, FORECAST)-not just the single task DESIGN. Therefore, this set has a total of 8 members that all correspond to a directed arc in the precedence relations diagram.

Now, with our sets and data established, we can turn our attention to building the formulas of the model. We have three attributes to compute: earliest start (ES), latest start (LS), and slack time (SLACK). The trick is computing ES and LS. Once we have these times, SLACK is merely the difference of the two.

Lets start by coming up with a formula to compute ES. A task cannot begin until all its predecessor tasks are completed. Thus, if we find the latest finishing time of all predecessors to a task, then we have also found its earliest start time. Therefore, in words, the earliest start time for task t is equal to the maximum over all predecessors of task t of the sum of the earliest start time of the predecessor plus its completion time. The corresponding LINGO notation is:

@FOR( TASKS( J)| J #GT# 1:

ES( J) = @MAX( PRED( I, J): ES( I) + TIME( I))

);

Note that we skip the computation for the first task by adding the conditional qualifier J #GT# 1. We do this because the first task has no predecessors. We will give the first task an arbitrary start time as shown below.

Computing LS is slightly trickier, but very similar to ES. In words, the latest time for task t to start is the minimum over all successor tasks of the sum of the successor's earliest start minus the time to perform task t. If task t starts any later than this, it will prohibit at least one successor from starting at its earliest start time. Converting into LINGO syntax gives:

@FOR( TASKS( I)| I #LT# LTASK:

LS( I) = @MIN( PRED( I, J): ES( J) - TIME( I))

);

Here, we omit the computation for the last task since it has no successor tasks.

Computing slack time is just the difference between LS and ES, and may be written as:

@FOR( TASKS( I): SLACK( I) = LS( I) - ES( I));

We can set the start time of the first task to some arbitrary value. For our purposes, we will set it to 0 with the statement:

ES( 1) = 0;

We have now input formulas for computing the values of all the variables with the exception of the latest start time for the last task. It turns out, if the last project were started any later than its earliest start time, the entire project would be delayed. So, by definition, the latest start time for the last project is equal to its earliest start time. We can express this in LINGO using the equation:

LS( 7) = ES( 7);

This would work, but it's probably not the best way to express the relation. Suppose you were to add some tasks to your model. You'd have to change the 7 in this equation to the new number of tasks was. The whole idea behind LINGO's set-based modeling language is the equations in the model should be independent of the data. Expressing the equation in this form violates data independence. Here's a better way to do it:

LTASK = @SIZE( TASKS);

LS( LTASK) = ES( LTASK);

The @SIZE function returns the size of a set. In this case, it will return the value 7, as desired. However, if we changed the number of tasks, @SIZE would also return the new, correct value. Thus, we preserve the data independence of our model's equations.