home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / lifeos2.zip / LIFE-1.02 / EXAMPLES / SCHEDULE.LF < prev    next >
Text File  |  1996-06-04  |  5KB  |  148 lines
  1. % Copyright 1992 Digital Equipment Corporation
  2. % All Rights Reserved
  3.  
  4. % Simple PERT scheduler written in Life.
  5. % Author: Bruno Dumant.
  6.  
  7. % usage: look at the sample inputs below
  8.  
  9. module("schedule") ?
  10. public( task,visAllTasks,sch_1,sch_2,sch_3,sch_4)?
  11.  
  12. %%%% Do the scheduling %%%%
  13. :: A:task( duration => D:real,
  14.            earlyStart => earlyCalc(R),
  15.            lateStart  => {1e10;real}, 
  16.            prerequisites => R:{[];list} ) | !, lateCalc(A,R).
  17.         
  18. % Pass 1: Calculate the earliest time that A can start.
  19. earlyCalc([]) -> 0.
  20. earlyCalc([B|ListOfTasks]) ->
  21.     max(B.earlyStart+B.duration,earlyCalc(ListOfTasks)).
  22.  
  23. % Pass 2: Calculate the latest time that A's prerequisites can start
  24. % and still finish before A starts.
  25. lateCalc(A,[]) -> true.
  26. lateCalc(A,[B:task|ListOfTasks]) -> lateCalc(A,ListOfTasks) | 
  27.     assign(LSB:(B.lateStart),
  28.            min(LSB, A.earlyStart-B.duration)).
  29.  
  30. % Wait until B is an integer before doing the assignment:
  31. assign(A,B:int) -> succeed | A<-B.
  32.  
  33. %%%% Prettyprint the output %%%%
  34. visAllTasks([A|B],N:{1;real}) :- !, visualize(A,N), visAllTasks(B,N+1).
  35. visAllTasks([]).
  36.  
  37. visualize(A,N:int) :-
  38.     write("Task ",N,": "),
  39.     visStart(A.earlyStart),visDuration(A.duration,"*"),nl,
  40.     write("            "),
  41.     % Only print lateStart if it fits on the screen (it could
  42.     % be infinite, after all!):
  43.     cond( A.lateStart=<50,
  44.           (visStart(A.lateStart),visDuration(A.duration,"-"),nl,nl),
  45.           nl
  46.     ).
  47.  
  48. visStart(N:int) :- visNcar(N," ").
  49. visDuration(N,S):- visNcar(N,S).
  50.  
  51. visNcar(0) :- !.
  52. visNcar(N,S) :- write(S), visNcar(N-1,S).
  53.  
  54.  
  55. % Sample input for the PERT scheduler:
  56. % The three examples sch_[123] are permutations of the
  57. % same problem, to illustrate that calculations in Life do not
  58. % depend on order of execution.
  59.  
  60. sch_1 :-
  61. A1=task(duration=>10),
  62. A2=task(duration=>20),
  63. A3=task(duration=>30),
  64. A4=task(duration=>18,prerequisites=>[A1,A2]),
  65. A5=task(duration=>8 ,prerequisites=>[A2,A3]),
  66. A6=task(duration=>3 ,prerequisites=>[A1,A4]),
  67. A7=task(duration=>4 ,prerequisites=>[A5,A6]),
  68. visAllTasks([A1,A2,A3,A4,A5,A6,A7]).
  69.  
  70. sch_2 :-
  71. A3=task(duration=>30),
  72. A7=task(duration=>4 ,prerequisites=>[A5,A6]),
  73. A5=task(duration=>8 ,prerequisites=>[A2,A3]),
  74. A1=task(duration=>10),
  75. A4=task(duration=>18,prerequisites=>[A1,A2]),
  76. A6=task(duration=>3 ,prerequisites=>[A1,A4]),
  77. A2=task(duration=>20),
  78. visAllTasks([A3,A2,A4,A7,A6,A5,A1]).
  79.  
  80. sch_3 :-
  81. A3=task(duration=>30),
  82. A7=task(duration=>4 ,prerequisites=>[A5,A6]),
  83. A5=task(duration=>8 ,prerequisites=>[A2,A3]),
  84. A1=task(duration=>10),
  85. A4=task(duration=>18,prerequisites=>[A1,A2]),
  86. A6=task(duration=>3 ,prerequisites=>[A1,A4]),
  87. A2=task(duration=>20),
  88. visAllTasks([A1,A2,A3,A4,A5,A6,A7]).
  89.  
  90.  
  91. % A dependency graph with large amounts of sharing:
  92. % This illustrates that the scheduler runs in linear time.  This is true
  93. % because each arithmetic operation is executed only once--it waits until
  94. % its argument becomes available and then does the operation.  This
  95. % pathological example is due to Herve' Touati.
  96.  
  97. sch_4 :-
  98.  
  99. A1=task(duration=>2, prerequisites=>[B1,C1]),
  100. B1=task(duration=>2, prerequisites=>[A2]),
  101. C1=task(duration=>2, prerequisites=>[A2]),
  102.  
  103. A2=task(duration=>2, prerequisites=>[B2,C2]),
  104. B2=task(duration=>2, prerequisites=>[A3]),
  105. C2=task(duration=>2, prerequisites=>[A3]),
  106.  
  107. A3=task(duration=>2, prerequisites=>[B3,C3]),
  108. B3=task(duration=>2, prerequisites=>[A4]),
  109. C3=task(duration=>2, prerequisites=>[A4]),
  110.  
  111. A4=task(duration=>2, prerequisites=>[B4,C4]),
  112. B4=task(duration=>2, prerequisites=>[A5]),
  113. C4=task(duration=>2, prerequisites=>[A5]),
  114.  
  115. A5=task(duration=>2, prerequisites=>[B5,C5]),
  116. B5=task(duration=>2, prerequisites=>[A6]),
  117. C5=task(duration=>2, prerequisites=>[A6]),
  118.  
  119. A6=task(duration=>2, prerequisites=>[B6,C6]),
  120. B6=task(duration=>2, prerequisites=>[A7]),
  121. C6=task(duration=>2, prerequisites=>[A7]),
  122.  
  123. A7=task(duration=>2, prerequisites=>[B7,C7]),
  124. B7=task(duration=>2, prerequisites=>[A8]),
  125. C7=task(duration=>2, prerequisites=>[A8]),
  126.  
  127. A8=task(duration=>2, prerequisites=>[B8,C8]),
  128. B8=task(duration=>2, prerequisites=>[A9]),
  129. C8=task(duration=>2, prerequisites=>[A9]),
  130.  
  131. A9=task(duration=>2, prerequisites=>[B9,C9]),
  132. B9=task(duration=>2, prerequisites=>[A10]),
  133. C9=task(duration=>2, prerequisites=>[A10]),
  134.  
  135. A10=task(duration=>2, prerequisites=>[B10,C10]),
  136. B10=task(duration=>2, prerequisites=>[A11]),
  137. C10=task(duration=>2, prerequisites=>[A11]),
  138.  
  139. A11=task(duration=>2, prerequisites=>[B11,C11]),
  140. B11=task(duration=>2, prerequisites=>[A12]),
  141. C11=task(duration=>2, prerequisites=>[A12]),
  142.  
  143. A12=task(duration=>2),
  144.  
  145. visAllTasks([A1,B1,C1,A2,B2,C2,A3,B3,C3,A4,B4,C4,A5,B5,C5,
  146.         A6,B6,C6,A7,B7,C7,A8,B8,C9,A9,B9,C9,A10,B10,C10,
  147.         A11,B11,C11,A12]).
  148.