1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 | % % ECLiPSe sample code % Author: Joachim Schimpf % Licenced under CC-BY-4.0 : http://creativecommons.org/licenses/by/4.0/ % % This is a simple model for the Test Scheduling Problem from the CP2015 % Modelling Competition, described at http://csplib.org/Problems/prob073 % % Uses straightforward no-overlap constraints and a simple search heuristic. % % Data structure declarations :- local struct(task(name,dur,machs,nmach,res,nres,start,mach)). :- local struct(res(name,cap)). :- local struct(mach(name,id)). % Libraries used :- lib(ic). :- lib(ic_edge_finder). :- lib(branch_and_bound). :- lib(timeout). main :- % Instance = "instances/t40m10r3-2.pl", % opt=1725 Instance = "instances/t50m10r3-9.pl" , % opt=7279 % Instance = "instances/t100m50r10-11.pl", % opt=4970 % Instance = "instances/t500m50r5-5.pl", % opt=33848 get_data( Instance , Resources , Machines , Tasks ), model( Resources , Machines , Tasks , MakeSpan ), solve( Tasks , MakeSpan ), writeln(makespan= MakeSpan ). model( Resources , Machines , Tasks , MakeSpan ) :- % Initialize machine variables, define task ends and makespan ( foreach (task{start: S ,dur: D ,machs: Ms ,mach: M }, Tasks ), foreach ( S , Starts ), foreach ( E , Ends ), foreach ( D , Durs ) do M #:: Ms , % machine variable E #= S + D % end time ), MakeSpan #= max( Ends ), LowerBound is integer(ceiling(sum( Durs )/length( Machines ))), MakeSpan #>= LowerBound , % Initialize start times Starts #:: 0..sum( Durs )-min( Durs ), % Non-overlap on global resources ( foreach (res{name: RN }, Resources ), param ( Tasks ) do ( foreach (task{res: Rs ,start: S ,dur: D }, Tasks ), fromto ( Starts , Starts1 , Starts2 ,[]), fromto ( Durs , Durs1 , Durs2 ,[]), param ( RN ) do ( memberchk( RN , Rs ) -> Starts1 = [ S | Starts2 ], Durs1 = [ D | Durs2 ] ; Starts1 = Starts2 , Durs1 = Durs2 ) ), ( Starts ==[] -> true ; disjunctive( Starts , Durs ) ) ), % Non-overlap on machines ( fromto ( Tasks ,[ T1 | Ts ], Ts ,[]) >> ( foreach ( T2 , Ts ), param ( T1 )) do task{start: S1 ,dur: D1 ,mach: M1 } = T1 , task{start: S2 ,dur: D2 ,mach: M2 } = T2 , M1 #= M2 => ( S1 + D1 #=< S2 or S2 + D2 #=< S1 ) ). solve( Tasks , MakeSpan ) :- % Order tasks with many resources/few machines/long duration first sort(dur of task, >=, Tasks , Tasks1 ), sort(nmach of task, =<, Tasks1 , Tasks2 ), sort(nres of task, >=, Tasks2 , OrderedTasks ), % branch-and-bound, allowing 10s for each improvement bb_min ( timeout(label( OrderedTasks ), 10, (writeln(timeout),fail)), MakeSpan , bb_options{strategy:restart} % faster % bb_options{strategy:dichotomic} % better ). % Assign machines and earliest feasible start time label( Tasks ) :- ( foreach (task{start: Start ,mach: Machine }, Tasks ), count ( _I ,1, _ ) do indomain( Machine , random), once indomain( Start , min) % incomplete labeling here! ). % Collect instance data: Resources, Machines, Tasks get_data( Instance , Resources , Machines , Tasks ) :- compile( Instance ), findall (res{name: N ,cap: C }, resource( N , C ), Resources ), findall (mach{name: N }, embedded_board( N ), Machines ), ( foreach (mach{id: I }, Machines ), count ( I ,1, NMach ) do true ), findall (task{name: N ,dur: D ,machs: Ms ,nmach: NM ,res: Rs ,nres: NR }, ( test( N , D , MNames , Rs , _ , _ ), length( Rs , NR ), ( MNames ==[] -> NM = NMach , Ms = 1.. NMach ; length( MNames , NM ), ( foreach ( MName , MNames ), foreach ( M , Ms ), param ( Machines ) do memberchk(mach{name: MName ,id: M }, Machines ) ) ) ), Tasks ). |