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) 2001 - 2006 Cisco Systems, Inc. All Rights Reserved. 18% 19% Contributor(s): Mark Wallace, IC-Parc 20% 21% END LICENSE BLOCK 22% ---------------------------------------------------------------------- 23% 24% Complete search method for resource-constrained scheduling problems 25% 26% System: ECLiPSe Constraint Logic Programming System 27% Author/s: Mark Wallace, IC-Parc 28% Version: $Id: ic_probing_for_scheduling.pl,v 1.3 2009/07/16 09:11:27 jschimpf Exp $ 29% 30% Many thanks to Hani El Sakkout, on whose ideas this search 31% implementation is based, and on whose benchmarks it was tested. 32% 33% 34% Todo: 35% - add facilities to control propagation during probing 36% 37% (Hani's benchmarks run faster when ic is switched off during search! 38% - I'm not sure if this is still true with IC) 39% ---------------------------------------------------------------------- 40 41:- module(ic_probing_for_scheduling). 42 43:- export 44 45 probe_sched/5, 46 probe_cstr_sched/7, 47 fun_to_cons_var/3. 48 49:- lib(ic). 50:- lib(repair). 51:- lib(eplex). 52:- lib(ic_edge_finder). 53:- lib(linearize). 54:- lib(branch_and_bound). 55 56:- use_module(ic_probe). % For the probe count 57:- use_module(ic_make_overlap_bivs). 58:- use_module(ic_probe_support). % For the task structure: task(id,start,duration) 59:- use_module(ic_probe_search). 60 61/* 62probe_sched( 63 + Starts, 64 + Durations, 65 + Resources, 66 +MaxResource, 67 ? CostFunction 68 ) 69 70Starts: List of integers or ic variables (Task start times) 71Durations: List of integers or ic variables (Task durations) 72Resources: List of integers or ic variables (Task resource consumption) 73MaxResource: Integer - maximum available resource 74CostFunction: Expression in terms of task start times and durations, 75 to be minimised. 76 77This procedure initialises a cost variable. 78It builds a constraint on the cost, which will be passed to the "probe". 79Finally it initialises some options. 80*/ 81probe_sched(Starts,Durations,Resources,Resource,CostFun) :- 82 check_cost_fun(CostFun,Starts-Durations-Resources), 83 fun_to_cons_var(CostFun,Constraints,Cost), 84 ( 85 UserOptions = [granularity(1),priority(5)] -> true 86 ; 87 UserOptions = options with [granularity:1,priority:5] 88 ), 89 probe_cstr_sched(Starts,Durations,Resources,Resource, 90 Constraints,Cost,UserOptions). 91 92 93/* 94probe_cstr_sched( 95 + Starts, 96 + Durations, 97 + Resources, 98 ++MaxResource, 99 + Constraints, 100 - Cost, 101 ++Options) 102 103Starts, Durations, Resources, MaxResource: as above. 104Constraints: A list of constraints, each having the form 105 'Term1 =:=Term2', 'Term1 >=Term2', 'Term1>Term2', 106 'Term1 =<Term2' or 'Term1 <Term2'. 107Cost - a finite domain variable 108Options - an options structure: 109 Options= [granularity(G),priority(P)] 110 (or for compatibility Options= options(G,P)) 111 'G' is the temporal granularity 112 'P' is the priority of the probe. 113*/ 114 115 116probe_cstr_sched(Starts, 117 Durations, 118 Resources, 119 Resource, 120 Constraints, 121 Cost, 122 UserOptions) :- 123 create_options(UserOptions,Options), 124 ic_edge_finder:cumulative(Starts,Durations,Resources,Resource), 125 task_structure(Tasks,Starts,Durations,Resources), 126 run_probe(Tasks,Constraints,Resource,Cost,Options). 127 128/* For compatibility with initial release */ 129create_options(options(G,P), options(G,P)) :- !. 130create_options(List,options with [granularity:G,priority:P]) :- 131 ( remove1(granularity(G),List,List2) -> check_granularity(G) 132 ; G=1, List2=List 133 ), 134 ( remove1(priority(P),List2,Rest) -> check_priority(P) 135 ; P=5, Rest=List2 ), 136 ( Rest=[] -> true 137 ; write(error,'Error: unrecognised options: '), 138 writeln(error,Rest), 139 abort 140 ). 141 142check_granularity(G) :- 143 integer(G), G>0 -> true ; 144 writeln(error,'Error: granularity must be a positive integer'), 145 abort. 146check_priority(P) :- 147 integer(P), P>2 -> true ; 148 writeln(error,'Error: priority must be an integer greater than 2'), 149 abort. 150 151 152/* run_probe(Tasks,Constraints,Resource,Cost,Options) */ 153run_probe(Tasks,Constraints,Resource,Cost,Options) :- 154 set_probect(0), 155 set_up_probe(Tasks,Constraints,Cost,Options,Handle), 156 tent_init(Tasks), 157 make_overlap_bivs(Tasks,Bivs,BivSums,Resource,Options), 158 SearchGoal = 159 ( task_durs(Tasks,Options,Handle), 160 probe_search(Bivs,BivSums,Resource,Options,Handle), 161 set_to_tent(Tasks) 162 ), 163 Options = options with granularity:G, 164 bb_min((SearchGoal,set_to_min(Cost)),Cost, 165 bb_options with [delta:G] 166 ), 167 eplex:lp_cleanup(Handle), 168 get_probect(Count), 169 writeln(log_output,probes(Count)). 170 171tent_init(Tasks) :- 172 term_variables(Tasks,Vars), 173 ( foreach(Var,Vars) 174 do 175 ( has_tentative_value(Var) -> true 176 ; get_min(Var,Min), 177 Var tent_set Min 178 ) 179 ). 180 181has_tentative_value(Var) :- 182 Var tent_get Val, 183 nonvar(Val). 184 185 186% Implements a heuristic that tries not allowing any durations to be 187% increased while establishing resource feasibility. 188 189% If durations are allowed to increase, for the rare case when 190% constraints between tasks necessitate this. The check ensures there 191% is at least one duration that COULD increase! 192 193task_durs(Tasks,Options,Handle) :- 194 member(task with duration:D,Tasks), 195 get_max(D) > tent_get(D), 196 !, 197 constrain_task_durs(Tasks,Options,Handle). 198task_durs(_,_,_). 199 200 201constrain_task_durs(Tasks,Options,Handle) :- 202 ( foreach(task with duration:D,Tasks), 203 foreach(D=<Old_D,Constraints) 204 do 205 D tent_get Old_D 206 ), 207 add_con(Constraints,[ic,linear(Handle)],Options). 208constrain_task_durs(_,_,_). 209 210 211 212/* 213% Introduced because 'cumulative' cannot deal with variable durations 214my_cumulative(Starts,Durations,Resources,Resource) :- 215 ( 216% foreach(_S,Starts), 217 foreach(D,Durations), 218 foreach(MinD,MinDurations) 219% , foreach(_R,Resources) 220 do 221 get_min(D,MinD) 222 ), 223 cumulative(Starts,MinDurations,Resources,Resource). 224*/ 225 226check_cost_fun(CostFun,Tasks) :- 227 term_variables(CostFun,CostVars), 228 term_variables(Tasks,TaskVars), 229 member(Var,CostVars), 230 not member(Var,TaskVars), !, 231 write(warning_output, 'Warning: The cost function '), 232 write(warning_output, CostFun), 233 writeln(warning_output, ' has a variable that is not linked to the tasks!'). 234check_cost_fun(_,_). 235 236fun_to_cons_var(CostFun,[Cost=:=CostExpr|ConsList],Cost) :- 237 pos_expr_to_cons_var(CostFun,ConsList,CostExpr). 238 239pos_expr_to_cons_var(PosEpr1+PosExpr2,ConsList,LinExpr1+LinExpr2) :- !, 240 pos_expr_to_cons_var(PosEpr1,ConsList1,LinExpr1), 241 pos_expr_to_cons_var(PosExpr2,ConsList2,LinExpr2), 242 append(ConsList1,ConsList2,ConsList). 243pos_expr_to_cons_var(Integer*PosExpr,ConsList,Integer*LinExpr) :- !, 244 integer(Integer), 245 pos_expr_to_cons_var(PosExpr,ConsList,LinExpr). 246pos_expr_to_cons_var(abs(Term),[Var >= LinExpr,Var >= -LinExpr],Var) :- !, 247 linearize_expr(Term,LinExpr). 248pos_expr_to_cons_var(max(ExprList),ConsList,Var) :- !, 249 max_cons(ExprList,Var,ConsList). 250pos_expr_to_cons_var(Other,[],LinExpr) :- 251 linearize_expr(Other,LinExpr). 252 253linearize_expr(Term,LinExpr) :- 254 linearize(Term,ListExpr,NonLin), 255 check_lin(NonLin), 256 list_to_sum(ListExpr,LinExpr). 257 258check_lin([]) :- !. 259check_lin([NonLin|_NonLins]) :- 260 write(error,'Error: the cost function has a non-linear part: '), 261 writeln(error,NonLin), 262 abort. 263 264 265% Assume the list produced by linearize is always non-empty 266list_to_sum([Last],Last) :- !. 267list_to_sum([H|T],H+LinExpr) :- 268 list_to_sum(T,LinExpr). 269 270max_cons(List,Var,ConsList) :- 271 ( foreach(Term,List), 272 foreach(Con,ConsList), 273 param(Var) 274 do 275 linearize_expr(Term,LinExpr), 276 Con= (Var>=LinExpr) 277 ). 278 279%---------------------------------------------------------------------- 280% User documentation 281%---------------------------------------------------------------------- 282 283:- comment(categories, ["Constraints","Techniques"]). 284:- comment(summary, "Probing for Scheduling"). 285:- comment(author, "Mark Wallace, Hani El Sakkout"). 286:- comment(date, "$Date: 2009/07/16 09:11:27 $"). 287:- comment(copyright, "Cisco Systems, Inc."). 288 289:- comment(desc, html(" 290 This is a complete search method for resource-constrained scheduling 291 problems 292 </P><P> 293 The user interface is similar to the cumulative constraint, with a 294 list of task start times, durations and resources; and a maximum 295 resource limit. There is one extra argument, a cost function which 296 is to be minimised. 297 </P><P> 298 Probing for scheduling differs radically from the cumulative constraint 299 because it includes a search routine. In its behaviour it is an 300 optimisation procedure and not simply a constraint which enforces 301 consistency. 302 </P><P> 303 The search is focussed towards an optimal vlaue of the cost function. 304 </P> 305 ")). 306 307 308:- comment(eg, " 309% Example program: simple schedule optimisation 310 311:- lib(ic_probing_for_scheduling). 312:- lib(ic). 313 314ex1([X,Y,Z],Cost) :- 315 [OldX,OldY,OldZ]=[1,5,5], 316 Durations=[10,5,5], 317 Resources=[1,2,1], 318 MaxResource=2, 319 NewStarts=[X,Y,Z], 320 ic:(NewStarts::1..10), 321 CostFun= abs(X-OldX) + abs(Y-OldY) + abs(Z-OldZ), 322 probe_sched(NewStarts,Durations,Resources,MaxResource,CostFun), 323 Cost is CostFun. 324 325ex2([X,Y,Z],Cost) :- 326 [OldX,OldY,OldZ]=[1,5,5], 327 Durations=[10,5,5], 328 Resources=[1,2,1], 329 MaxResource=2, 330 NewStarts=[X,Y,Z], 331 ic:(NewStarts::1..10), 332 Constraints=[ 333 XDiff >= X-OldX, XDiff >= OldX-X, 334 YDiff >= Y-OldY, YDiff >= OldY-Y, 335 ZDiff >= Z-OldZ, ZDiff >= OldZ-Z, 336 Cost =:= XDiff+YDiff+ZDiff 337 ], 338 Options=[granularity(1),priority(5)], 339 probe_cstr_sched(NewStarts,Durations,Resources,MaxResource, 340 Constraints,Cost,Options). 341 342ex3(Starts,MaxResource,Cost) :- 343 Starts=[S1,S2,S3,S4], 344 ic:(S1::1..10), 345 ic:(S2::3..10), 346 ic:(S3::1..5), 347 ic:(S4::3..10), 348 [D1,D2,D3,D4]=[5,5,3,3], 349 Durations=[D1,D2,D3,D4], 350 Resources=[1,1,1,1], 351 CostFun= max([S1+D1,S2+D2,S3+D3,S4+D4]), 352 probe_sched(Starts,Durations,Resources,MaxResource,CostFun), 353 ic:(Cost =:= eval(CostFun)). 354 355"). 356 357:- comment(fun_to_cons_var/3, [ 358 summary: "Convert a cost expression to a variable and a list of constraints, 359suitable to pass into probe_cstr_sched/7", 360 amode: fun_to_cons_var(+,-,-), 361 362 args:[ "CostFun": "a cost function of the form accepted by probe_sched/5", 363 "ConsList": " a variable which will be instantiated to a list of constraints, 364suitable to pass into probe_cstr_sched/7", 365 "CostVar": "a variable constrained to take a value greater than or equal to 366the cost function"], 367 resat:no, 368 see_also:[probe_sched/5,probe_cstr_sched/7], 369 desc:html("<P> 370If the user needs to use probe_cstr_sched instead of probe_sched, this predicate can be used to convert the cost function to a list of constraints and a cost variable suitable for passing to probe_cstr_sched 371"), 372 eg:" 373fun_to_cons_var(abs(X-10)+abs(Y-3),ConsList,Var) 374"]). 375 376:- comment(probe_sched/5, [ 377 summary: "Find a resource-feasible schedule that minimises the 378cost function", 379 amode:probe_sched(+,+,+,+,?), 380 args:["Starts": " a list of (n) task start times (integers or 381finite domain variables)", 382 "Durations":"a list of (n) task durations (integers or 383finite domain variables)", 384 "Resources":"a list of (n) task resource needs (integers or 385finite domain variables)", 386 "MaxResource":"The available resource, not to be exceeded (integer)", 387 "CostFun":"An expression involving start times and durations 388to be minimised" 389 ], 390 resat:no, 391 see_also:[probe_cstr_sched/7,min_max/2,set_up_probe/5,make_overlap_bivs/5,probe_search/5,maxlist/2], 392 desc:html("<P> 393 This predicate finds start times for a set of tasks, which 394minimise the value of a given cost function. 395</P><P> 396The cost function is the only information the search algorithm can use to 397focus on the optimum. It cannot guide the search if the cost is a variable, 398only linked to the tasks start times by constraints. For this reason the 399cost function admits the special functions <B>abs</B> and <B>maxlist</B>. 400</P><P> 401The syntax for cost functions is: 402<PRE> 403CostFunction ::- PosExpr | PosExpr + PosExpr | Integer * PosExpr 404PosExpr ::- abs(LinearExpr) | maxlist([LinearExpr]) | LinearExpr. 405</PRE> 406</P><P> 407The algorithm is described in more detail in the documentation of 408<B>probe_cstr_sched/7</B>. 409</P> 410"), 411 eg:" 412probe_schedule(Starts,CostFun) :- 413 Starts=[X,Y,Z], 414 ic:(Starts::1..10), 415 Durations=[10,5,5], 416 Resources=[R1,R2,R3], 417 ic:(R1::1..2), R2=2, R3=1, 418 MaxResource=2, 419 [OldX,OldY,OldZ]=[1,5,5], 420 CostFun= abs(X-OldX)+abs(Y-OldY)+abs(Z-OldZ), 421 probe_sched(Starts,Durations,Resources,MaxResource,CostFun). 422" 423]). 424 425 426:- comment(probe_cstr_sched/7, [ 427 summary: "Find a resource-feasible schedule that minimises the 428cost, subject to the constraints", 429 amode:probe_cstr_sched(+,+,+,++,+,-,++), 430 args:["Starts": " A list of (n) task start times (integers or 431finite domain variables)", 432 "Durations":"A list of (n) task durations (integers or 433finite domain variables)", 434 "Resources":"A list of (n) task resource needs (integers)", 435 "MaxResource":"The available resource, not to be exceeded", 436 "Constraints": "A list of numeric equations and inequations, 437using functors '=:=', '>=', '>', '=<' and '<'.", 438 "Cost":"A numeric variable which will be minimised during search", 439 "Options":" A list, '[granularity(G),priority(P)]', 440 where 441 'G' is an integer specifying the time granularity, and 442 'P' is the priority of the probe demon." 443 ], 444 resat:no, 445 see_also:[probe_sched/5,min_max/2,set_up_probe/5,make_overlap_bivs/5,probe_search/5], 446 desc:html("<P> 447This offers the same functionality as <B>probe_sched/5</B>, but with added 448flexibility, and a more complex user interface. The extra arguments offer 449the user more control. 450</P><P> 451The <B>Cost</B> argument is a variable, and it must be linked to the task 452variables by the list of linear constraints. The user can add not only 453linear constraints on the cost function, but also constraints between the 454task variables. Only constraints made explicit in this list are 'seen' by 455the probe. <B>probe_cstr_sched</B> also posts them to the ic solver. 456</P><P> 457The options offer user control over 458the temporal granularity, and the priority of the probe. 459</P><P> 460The algorithm uses <B>min_max</B>, but directs the search using a probe 461which focusses the search on the optimum. The probe is a procedure 462that finds optimal solutions to a relaxed problem ignoring resource 463limits. For details see <B>setup_probe</B>. Additionally the algorithm 464sets up a binary variable between each pair of tasks, see 465<B>make_overlap_bivs</B>. Whenever the probe returns tentative start 466times, these are propagated to the overlap binary variables yielding a 467total resource usage which reveals any bottlenecks, where needed 468resources exceed thos available. <B>probe_search</B> then 469non-deterministically introduces a new constraint which reduces the 470bottleneck. 471The probe_sched call: 472<PRE> 473probe_sched(Ss,Ds,Rs,MaxR,abs(X-X1)+Y) 474</PRE> 475translates into the probe_cstr_sched call: 476<PRE> 477probe_cstr_sched(Ss,Ds,Rs,MaxR,[Cost=:=E1+Y,E1>=X-X1,E1>=X1-X],Cost, 478[granularity(1),priority(5)]) 479</PRE> 480Thus making the default granularity '1' and the default priority '5'. 481") 482]). 483 484 485 486 487 488