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