1% BEGIN LICENSE BLOCK
2% Version: CMPL 1.1
3%
4% The contents of this file are subject to the Cisco-style Mozilla Public
5% License Version 1.1 (the "License"); you may not use this file except
6% in compliance with the License.  You may obtain a copy of the License
7% at www.eclipse-clp.org/license.
8%
9% Software distributed under the License is distributed on an "AS IS"
10% basis, WITHOUT WARRANTY OF ANY KIND, either express or implied.  See
11% the License for the specific language governing rights and limitations
12% under the License.
13%
14% The Original Code is  The ECLiPSe Constraint Logic Programming System.
15% The Initial Developer of the Original Code is  Cisco Systems, Inc.
16% Portions created by the Initial Developer are
17% Copyright (C) 2006 Cisco Systems, Inc.  All Rights Reserved.
18%
19% Contributor(s): Mark Wallace, IC-Parc
20%
21% END LICENSE BLOCK
22:- use_module(probing_for_scheduling).
23:- lib(repair).
24:- lib(fd).
25
26ex1([X,Y,Z],Cost) :-
27        [OldX,OldY,OldZ]=[1,5,6],
28        Durations=[10,5,5],
29        Resources=[1,2,1],
30        MaxResource=2,
31        NewStarts=[X,Y,Z],
32        fd:(NewStarts::1..10),
33        CostFun= abs(X-OldX) + abs(Y-OldY) + abs(Z-OldZ),
34	probe_sched(NewStarts,Durations,Resources,MaxResource,CostFun),
35	Cost is CostFun.
36/* Expected result:
37[eclipse]: ex1([X,Y,Z],Cost)
38Found a solution with cost 9
39probes(7)
40
41[X,Y,Z] = [6, 1, 6]
42Cost = 9
43*/
44
45ex2([X,Y,Z],[OldX,OldY,OldZ],Durations,Resources,MaxResource,Options,Cost) :-
46        NewStarts=[X,Y,Z],
47        fd:(NewStarts::1..10),
48        Constraints=[
49                     XDiff >= X-OldX, XDiff >= OldX-X,
50                     YDiff >= Y-OldY, YDiff >= OldY-Y,
51		     ZDiff >= Z-OldZ, ZDiff >= OldZ-Z,
52		     Cost =:= XDiff+YDiff+ZDiff
53                    ],
54	probe_cstr_sched(NewStarts,Durations,Resources,MaxResource,
55                         Constraints,Cost,Options).
56
57/*
58[eclipse]: ex2([X,Y,Z],[1,5,6],[10,5,5],[1,2,1],2,[granularity(1),priority(5)],Cost).
59Found a solution with cost 9
60probes(7)
61
62X = 6
63Y = 1
64Z = 6
65Cost = 9
66
67
68[eclipse]: ex2([X,Y,Z],[1,5,6],[10,5,5],[1,2,1],2,[granularity(1),priority(2)],Cost).
69Found a solution with cost 9
70probes(14)
71
72X = 6
73Y = 1
74Z = 6
75Cost = 9
76
77[eclipse]: ex2([X,Y,Z],[1,5,6],[10,5,5],[1,2,1],3,[granularity(1),priority(5)],Cost).
78Found a solution with cost 4
79probes(5)
80
81X = 1
82Y = 1
83Z = 6
84Cost = 4
85
86[eclipse]: R1 :: 1..3, R2 :: 2..3, R3=1,
87           ex2([X,Y,Z],[1,5,6],[10,5,5],[R1,R2,R3],3,[granularity(1),priority(5)],Cost).
88Found a solution with cost 4
89probes(5)
90
91X = 1
92Y = 1
93Z = 6
94R1 = 1
95R2 = 2
96R3 = 1
97Cost = 4
98*/
99
100ex3(Starts,MaxResource,Cost) :-
101	Starts=[S1,S2,S3,S4],
102	fd:(S1::1..10),
103	fd:(S2::3..10),
104	fd:(S3::1..5),
105	fd:(S4::3..10),
106        [D1,D2,D3,D4]=[5,5,3,3],
107        Durations=[D1,D2,D3,D4],
108	Resources=[1,1,1,1],
109	CostFun= maxlist([S1+D1,S2+D2,S3+D3,S4+D4]),
110	probe_sched(Starts,Durations,Resources,MaxResource,CostFun),
111	Cost is CostFun.
112
113/*
114[eclipse]: ex3(Starts,1,Cost).
115
116No
117
118[eclipse]: ex3(Starts,2,Cost).
119Found a solution with cost 12
120Found a solution with cost 11
121Found a solution with cost 9
122probes(8)
123
124Starts = [1, 4, 1, 6]
125Cost = 9
126
127[eclipse]: ex3(Starts,3,Cost).
128Found a solution with cost 8
129probes(3)
130
131Starts = [1, 3, 1, 4]
132Cost = 8
133
134*/
135
136ex4(Reduction,Cost) :-
137	run_bench(Reduction,Cost).
138
139/*
140[eclipse]: ex4(0,Cost).
141Old resource: 8
142New resource: 8
143Found a solution with cost 0
144probes(1)
145
146Cost = 0
147
148[eclipse]: ex4(1,Cost).
149Old resource: 8
150New resource: 7
151Found a solution with cost 15
152probes(11)
153
154Cost = 15
155
156[eclipse]: ex4(2,Cost).
157Old resource: 8
158New resource: 6
159Found a solution with cost 105
160probes(181)
161
162Cost = 105
163
164[eclipse]: ex4(3,Cost).
165Old resource: 8
166New resource: 5
167Found a solution with cost 410
168Found a solution with cost 390
169Found a solution with cost 370
170Found a solution with cost 230
171Found a solution with cost 225
172Found a solution with cost 220
173probes(1065)
174
175Cost = 220
176
177*/
178
179
180setup_options(Options) :-
181	time_granularity(G),
182        probe_priority(P),
183	Options = [granularity(G),priority(P)].
184
185
186%%% Time granularity
187time_granularity( 5 ).
188
189%%%  Priority of linear probe demon
190probe_priority( 5 ).
191
192%%%  Amount by which start and end times can be changed
193max_time_change(300).
194
195%%% Information specific to this data set
196
197%%% Number of tasks
198task_count( 20 ).
199%%% The temporal horizon
200time_horizon( 285, 1260).
201
202/*
203> t(1, 2, 1055, 1155, 10).
204This declares an activity with a start time point of ID 1,
205and an end time point of ID 2, starting at minute 1055
206and terminating at minute 1155. The final parameter declares
207that the activity may be shrunk or grown by no more than 10 minutes.
208
209> c(id(1) #>= id(3) + t(10)).
210This declares the constraint that the time point with ID 1 must
211take place no sooner than the time point with ID 3 plus 10 minutes.
212
213*/
214
215
216t(1, 2, 1040, 1140, 10).
217t(3, 4, 335, 435, 10).
218t(5, 6, 315, 415, 10).
219t(7, 8, 555, 655, 10).
220t(9, 10, 595, 695, 10).
221t(11, 12, 865, 965, 10).
222t(13, 14, 860, 960, 10).
223t(15, 16, 685, 785, 10).
224t(17, 18, 820, 920, 10).
225t(19, 20, 650, 750, 10).
226t(21, 22, 510, 610, 10).
227t(23, 24, 835, 935, 10).
228t(25, 26, 880, 980, 10).
229t(27, 28, 980, 1080, 10).
230t(29, 30, 510, 610, 10).
231t(31, 32, 515, 615, 10).
232t(33, 34, 545, 645, 10).
233t(35, 36, 540, 640, 10).
234t(37, 38, 665, 765, 10).
235t(39, 40, 510, 610, 10).
236
237c(id(34) #<= id(36) + t(5)).
238c(id(31) #<= id(36) - t(125)).
239c(id(30) #<= id(32) - t(5)).
240c(id(28) #>= id(29) + t(570)).
241c(id(27) #>= id(39) + t(470)).
242c(id(27) #>= id(30) + t(370)).
243c(id(25) #= id(27) - t(100)).
244c(id(22) #<= id(39) + t(100)).
245c(id(21) #>= id(23) - t(325)).
246c(id(19) #>= id(24) - t(285)).
247c(id(19) #<= id(22) + t(40)).
248c(id(18) #>= id(23) + t(85)).
249c(id(17) #<= id(18) - t(100)).
250c(id(14) #<= id(38) + t(195)).
251c(id(13) #>= id(18) - t(60)).
252c(id(12) #<= id(26) - t(15)).
253c(id(12) #= id(25) + t(85)).
254c(id(10) #= id(34) + t(50)).
255c(id(9) #>= id(18) - t(325)).
256c(id(5) #>= id(29) - t(195)).
257c(id(3) #<= id(37) - t(330)).
258c(id(3) #<= id(31) - t(180)).
259c(id(3) #>= id(15) - t(350)).
260c(id(2) #>= id(40) + t(530)).
261c(id(1) #= id(6) + t(625)).
262
263
264run_bench(Reduction,Cost) :-
265	max_time_change(MaxChange),
266	task_count(TaskCount),
267        probe_bench(TaskCount,Reduction,MaxChange,Cost).
268
269probe_bench(TaskCount,ResourceReduction,MaxChange,Cost) :-
270        VarCount is 2*TaskCount,
271        functor(VarArray,vars,VarCount),
272        make_tasks(MaxChange,StartEndConstraints,VarArray,Tasks),
273        make_constraints(VarArray,SimpleTemporalConstraints),
274        append(StartEndConstraints,SimpleTemporalConstraints,Constraints),
275        max_overlap(Tasks,OldResource),
276        NewResource is OldResource-ResourceReduction,
277        write('Old resource: '), writeln(OldResource),
278        write('New resource: '), writeln(NewResource),
279        make_cost_fun(Tasks,MaxChange,Cost,CostCons),
280        append(Constraints,CostCons,AllCons),
281        setup_options(Options),
282        task_structure(Tasks,Starts,Durations,Resources),
283        probe_cstr_sched(Starts,Durations,Resources,NewResource,AllCons,Cost,Options).
284
285task_structure(Tasks,Starts,Durations,Resources) :-
286	(  foreach(task(Start,Duration),Tasks),
287           foreach(Start,Starts),
288           foreach(Duration,Durations),
289           foreach(Resource,Resources)
290        do
291	   Resource=1
292        ).
293
294max_overlap(Tasks,Resource) :-
295       (   foreach(Task1,Tasks),
296           foreach(Resource1,Resources),
297	   param(Tasks)
298       do
299           compute_resource(Task1,Tasks,Resource1)
300       ),
301       Resource is max_res_list(Resources).
302
303max_res_list(List,Max) :-
304	(  foreach(Value,List),
305           fromto(0,ThisMax,NextMax,Max)
306        do
307           (Value>ThisMax -> NextMax=Value ; NextMax=ThisMax)
308        ).
309
310compute_resource(task(S,_),Tasks,Resource) :-
311	OldStart is tent_get(S),
312	(   foreach(task(S2,D2), Tasks),
313	    fromto(0,ThisOlap,NextOlap,Resource),
314	    param(OldStart)
315        do
316	    ( OldStart2 is tent_get(S2),
317	      OldEnd2 is tent_get(S2)+tent_get(D2),
318	      ((OldStart2=<OldStart, OldEnd2>OldStart) ->
319		      NextOlap is ThisOlap+1
320                ;     NextOlap is ThisOlap
321              )
322            )
323        ).
324
325
326% Include cost of moving the End !!!
327make_cost_fun(Tasks,MaxChange,Cost,Cons) :-
328    (   foreach(task(S,Duration), Tasks),
329        fromto([],Diffs,[SDiff,EDiff|Diffs],AllDiffs),
330        fromto([],
331	       Constraints,
332               [ SDiff>=S-OldStart,
333                 SDiff>=OldStart-S,
334                 EDiff>=(S+Duration)-(OldStart+OldDuration),
335                 EDiff>=(OldStart+OldDuration)-(S+Duration)
336                |
337                 Constraints
338               ],
339               AllConstraints
340              ),
341         param(MaxChange)
342    do   ( fd:(SDiff::0..MaxChange),
343           fd:(EDiff::0..MaxChange),
344           S tent_get OldStart,
345           Duration tent_get OldDuration
346         )
347     ),
348     Cons = [Cost=:=sum(AllDiffs)|AllConstraints].
349
350make_tasks(Shift,SEConstraints,VarArray,Tasks) :-
351        Goal = t(_IdStart,_IdEnd,_OldStart,_OldEnd,_Shrink),
352	findall(Goal,call(Goal),InTaskList),
353        (  foreach(InTask,InTaskList),
354           foreach(SECons,SEConstraints),
355           foreach(Task,Tasks),
356           param(Shift,VarArray)
357        do make_task(InTask,Shift,SECons,VarArray,Task)
358        ).
359
360make_task(t(IdStart,IdEnd,OldStart,OldEnd,Shrink),Shift,SECons,VarArray,Task) :-
361	Task = task(S,Duration),
362        S tent_set OldStart,
363        make_time_domain(S,OldStart,Shift),
364        S is VarArray[IdStart],
365        make_time_domain(E,OldEnd,Shift),
366        E tent_set OldEnd,
367        E is VarArray[IdEnd],
368        OldDuration is OldEnd-OldStart,
369        Min is OldDuration-Shrink,
370        Max is OldDuration+Shrink,
371        Duration tent_set OldDuration,
372        fd:(Duration::Min..Max),
373        fd:(Duration#>=Min),
374        fd:(E #= S+Duration),
375        SECons= (E=:=S+Duration).
376
377make_time_domain(S,OldStart,Shift) :-
378	time_horizon( F, L),
379        MinStart is max(OldStart-Shift,F),
380        MaxStart is min(OldStart+Shift,L),
381	fd:(S::MinStart..MaxStart).
382
383make_constraints(VarArray,Constraints) :-
384    findall(InCon,c(InCon),InCons),
385    (  foreach(InCon,InCons),
386       foreach(OutCon,Constraints),
387       param(VarArray)
388    do extract_terms_from_expr(InCon,VarArray,OutCon)
389    ).
390
391
392extract_terms_from_expr(id(N),VarArray,R) :- !,
393    R is VarArray[N].
394extract_terms_from_expr(t(N),_,N) :- !.
395extract_terms_from_expr(InCompound,VarArray,OutCompound) :-
396    InCompound=..[Pred,Arg1,Arg2],
397    conv_pred(Pred,NewPred), !,
398    OutCompound=..[NewPred,NewArg1,NewArg2],
399    extract_terms_from_expr(Arg1,VarArray,NewArg1),
400    extract_terms_from_expr(Arg2,VarArray,NewArg2).
401
402conv_pred( '+', '+' ).
403conv_pred( '-', '-' ).
404conv_pred( '#=', '=:=' ).
405conv_pred( '#>=', '>=' ).
406conv_pred( '#<=', '=<' ).
407conv_pred(Other,_) :-
408    write('Unexpected operator in expression: '), writeln(Other), abort.
409
410
411
412
413
414