/**********************************************************************

This is the bridge scheduling problem as described in
Pascal van Hentenryck: Constraint Satisfaction in Logic Programming

**********************************************************************/

:- lib(ic).
:- lib(branch_and_bound).

:- local struct(task(start,duration,need,use)).

solve(End_date) :-
	Tasks = [
	    L, T1, T2, T3, T4, T5, M1, M2, M3, M4, M5, M6,
	    S1, S2, S3, S4, S5, S6, A1, A2, A3, A4, A5, A6, P1, P2,
	    B1, B2, B3, B4, B5, B6, V1, V2,
	    AB1, AB2, AB3, AB4, AB5, AB6, UA, UE, PA, PE
	],
	PA = task with [duration : 0, need : []],
	A1 = task with [duration : 4, need : [PA], use : excavator],
	A2 = task with [duration : 2, need : [PA], use : excavator],
	A3 = task with [duration : 2, need : [PA], use : excavator],
	A4 = task with [duration : 2, need : [PA], use : excavator],
	A5 = task with [duration : 2, need : [PA], use : excavator],
	A6 = task with [duration : 5, need : [PA], use : excavator],
	P1 = task with [duration : 20, need : [A3], use : pile-driver],
	P2 = task with [duration : 13, need : [A4], use : pile-driver],
	UE = task with [duration : 10, need : [PA]],
	Start_of_F = task with [duration : 0, need : []],
	S1 = task with [duration : 8, need : [A1,Start_of_F], use : carpentry],
	S2 = task with [duration : 4, need : [A2,Start_of_F], use : carpentry],
	S3 = task with [duration : 4, need : [P1,Start_of_F], use : carpentry],
	S4 = task with [duration : 4, need : [P2,Start_of_F], use : carpentry],
	S5 = task with [duration : 4, need : [A5,Start_of_F], use : carpentry],
	S6 = task with [duration : 10, need : [A6,Start_of_F], use : carpentry],
	B1 = task with [duration : 1, need : [S1], use : concrete-mixer],
	B2 = task with [duration : 1, need : [S2], use : concrete-mixer],
	B3 = task with [duration : 1, need : [S3], use : concrete-mixer],
	B4 = task with [duration : 1, need : [S4], use : concrete-mixer],
	B5 = task with [duration : 1, need : [S5], use : concrete-mixer],
	B6 = task with [duration : 1, need : [S6], use : concrete-mixer],
	AB1 = task with [duration : 1, need : [B1]],
	AB2 = task with [duration : 1, need : [B2]],
	AB3 = task with [duration : 1, need : [B3]],
	AB4 = task with [duration : 1, need : [B4]],
	AB5 = task with [duration : 1, need : [B5]],
	AB6 = task with [duration : 1, need : [B6]],
	M1 = task with [duration : 16, need : [AB1], use : bricklaying],
	M2 = task with [duration : 8, need : [AB2], use : bricklaying],
	M3 = task with [duration : 8, need : [AB3], use : bricklaying],
	M4 = task with [duration : 8, need : [AB4], use : bricklaying],
	M5 = task with [duration : 8, need : [AB5], use : bricklaying],
	M6 = task with [duration : 20, need : [AB6], use : bricklaying],
	End_of_M = task with [duration : 0, need : [M1,M2,M3,M4,M5,M6]],
	L = task with [start : 30, duration : 2, need : [], use : crane],
	T1 = task with [duration : 12, need : [M1,M2,L], use : crane],
	T2 = task with [duration : 12, need : [M2,M3,L], use : crane],
	T3 = task with [duration : 12, need : [M3,M4,L], use : crane],
	T4 = task with [duration : 12, need : [M4,M5,L], use : crane],
	T5 = task with [duration : 12, need : [M5,M6,L], use : crane],
	UA = task with [duration : 10, need : [UE]],
	V1 = task with [duration : 15, need : [T1], use : caterpillar],
	V2 = task with [duration : 10, need : [T5], use : caterpillar],
	PE = task with [duration : 0, need : [T2,T3,T4,UA,V1,V2], start:End_date],

	% Distance constraints  -------------------
	end_to_end_max(S6, B6, 4),
	end_to_end_max(S5, B5, 4),
	end_to_end_max(S4, B4, 4),
	end_to_end_max(S3, B3, 4),
	end_to_end_max(S2, B2, 4),
	end_to_end_max(S1, B1, 4),
	end_to_start_max(A6, S6, 3),
	end_to_start_max(A5, S5, 3),
	end_to_start_max(P2, S4, 3),
	end_to_start_max(P2, S4, 3),
	end_to_start_max(P1, S3, 3),
	end_to_start_max(A2, S2, 3),
	end_to_start_max(A1, S1, 3),
	start_to_start_min(UE, Start_of_F, 6),
	end_to_start_min(End_of_M, UA, -2),

	% Precedence constraints  -------------------
	( foreach(task with [start:Si,need:NeededTasks], Tasks) do
	    Si #>= 0,
	    ( foreach(task with [start:Sj,duration:Dj], NeededTasks), param(Si) do
		Si #>= Sj+Dj
	    )
	),

	( foreach(task with start:S,Tasks), foreach(S,Starts) do true ),

	% Search and optimisation -------------------

        
	bb_min((
                   no_overlaps(Tasks),	% disjunctions
                   labeling(Starts)
               ), End_date, bb_options with [strategy:step]).


% some auxliliary definitions

start_to_start_min(task with [start:S1], task with [start:S2] , Min) :-
	S1+Min #=< S2.

end_to_end_max(task with [start:S1,duration:D1], task with [start:S2,duration:D2], Max) :-
	S1+D1+Max #>= S2+D2.

end_to_start_max(task with [start:S1,duration:D1], task with [start:S2], Max) :-
	S1+D1+Max #>= S2.

end_to_start_min(task with [start:S1,duration:D1], task with [start:S2], Min) :-
	S1+D1+Min #=< S2.


% tasks can't overlap if they use the same resource
% this is where the disjunctions are

no_overlaps(Tasks) :-
	( fromto(Tasks, [Task0|Tasks0], Tasks0, []) do
	    ( foreach(Task1,Tasks0), param(Task0) do
		Task0 = task with [start:S0, duration:D0, use:R0],
		Task1 = task with [start:S1, duration:D1, use:R1],
		( R0 == R1 ->
		    no_overlap(S0, D0, S1, D1)
		;
		    true
		)
	    )
	).

no_overlap(Si,Di,Sj,_Dj) :-
	Sj #>= Si+Di.
no_overlap(Si,_Di,Sj,Dj) :-
	Si #>= Sj+Dj.