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