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