% Job assignment problem
% file: jobs01.pl
% created: 2 Dec 2001 (assign.pl,gant.pl)
% edited: 5 May 2003
% author: Kenryo INDO (Kanto Gakuen University)

jobs([j1,j2,j3,j4]).
workers([w1,w2,w3,w4]).
cost(j1,[(w1,8),(w2,7),(w3,5),(w4,8)]).
cost(j2,[(w1,4),(w2,2),(w3,5),(w4,4)]).
cost(j3,[(w1,7),(w2,6),(w3,8),(w4,6)]).
cost(j4,[(w1,4),(w2,1),(w3,3),(w4,3)]).

plan(X,C):-
   X = [(j1,W1,C1),(j2,W2,C2),(j3,W3,C3),(j4,W4,C4)],
   assign(X,C).

assign([],0).
assign([(J,W,C)|Y],C1):-
    assign(Y,C2),
    jobs(Js),
    workers(Ws),
    member(J,Js),
    member(W,Ws),
    cost(J,Ps),
    member((W,C),Ps),
    \+ member((J,_,_),Y),
    \+ member((_,W,_),Y),
    C1 is C2 + C.

minimal_cost(P,C):-
    plan(P,C),
    \+ (plan(P1,C1), C1 < C).

/*  a sample output of the program
11 ?- minimal_cost(X,C).

X = [(j1, w3, 5),(j2, w1, 4),(j3, w4, 6),(j4, w2, 1)]
C = 16 ;

12 ?- plan(Assign,Cost).

Assign = [(j1, w4, 8),(j2, w3, 5),(j3, w2, 6),(j4, w1, 4)]
Cost = 23 ;

Assign = [(j1, w3, 5),(j2, w4, 4),(j3, w2, 6),(j4, w1, 4)]
Cost = 19 ;

Assign = [(j1, w4, 8),(j2, w2, 2),(j3, w3, 8),(j4, w1, 4)]
Cost = 22 ;

Assign = [(j1, w2, 7),(j2, w4, 4),(j3, w3, 8),(j4, w1, 4)]
Cost = 23 ;

Assign = [(j1, w3, 5),(j2, w2, 2),(j3, w4, 6),(j4, w1, 4)]
Cost = 17 
...
*/

return to front page.