Information Technology Reference
In-Depth Information
BEGIN
FOR i := 1 TO jobs DO
min_start_time := 1;
FOR j := 1 TO job[i].tasks DO
SOME k := min_start_time TO deadline - job[i].task[j].length + 1
DO
(* job i engages the processor needed for task j from time k to
k + (length of task j) - 1.
If the processor is already engaged, the program backtracks.
*)
FOR h := k TO k + job[i].task[j].length - 1 DO
gantt[job[i].task[j].processor,h] = i;
END
END;
min_start_time := k + job[i].task[j].length;
(* set the minimum start time for the next task
to the end of the current task *)
END;
END
END JobShopScheduling;
In this program the \don't know" nondeterminism provided by the use of
the
SOME
statement is combined with the use of assignment.
Furthermore, as already mentioned, for each value of
i
and
j
the equality
gantt[job[i].task[j].processor,h] = i
acts both as an assignment and as
atest.
The array
gantt
should be uninitialized when the procedure is called. At
the end of the execution the variable
gantt
contains the rst feasible schedule
it nds.
Preinitialized values can be used to enforce some preassignments of jobs to
processors, or to impose a constraint that a processor is not available during
some periods of time. For example, if processor 2 is not available at time 5, we
just use the assignment
gantt[2,5] := 0
(where 0 is a dummy value) before
invoking the procedure
JobShopSchedule
.
As an example, suppose we have 3 jobs, 3 processors (
p
1
,
p
2
,and
p
3
), the
deadline is 20, and the jobs are composed as follows:
task 1 task 2 task 3 task 4
job tasks proc len proc len proc len proc len
1
4
5
5
5
3
p
1
p
2
p
3
p
2
2
3
6
6
4
p
2
p
1
p
3
3
4
6
4
4
1
p
3
p
2
p
1
p
2
The rst solution (out of the existing 48) for the array
gantt
that the pro-
gram nds is the following one, where the symbol
'-'
means that the value is
uninitialized, i.e., the processor is idle in the corresponding time point.
11111-222222---3333-
222222111113333-1113
333333-----111112222
Search WWH ::
Custom Search