Prolog company/employee scheduling problem-CodePudding

I have a semi complex shift scheduling problem in prolog. From what I saw it can be solved with CLF but I am not that familiar and the resources online didn't really help me.

The problem states that the company has 50 employees and that each employee can either work in the morning shift(M), the evening shift(E), the night shift(N) or have a rest day(R). The problem has 2 constraints: That at least 15 employees must work at the morning shift(M), 10 in the evening one(E) and 8 in the night one(N) and that no employee can work the night shift(N) and have a morning shift(M) the next day.

It asks to produce a 30 day schedule by satisfying the above constraints and that multiple solutions exist.

What could be some way to approach the problem and how could I implement it using code in prolog?

Thank you very much!

CodePudding user response：

Here's a full solution (using swi-prolog):

days_in_month(30).
employees_num(50).


go :-
    days_in_month(Days),
    length(M, Days),
    days(M),
    show_days(M).


days([D1, D2|T]) :-
    two_days(D1, D2),
    (T = [] ; days([D2|T])).


other_day_constraints(D) :-
    day_constraint(10, e, D),
    maplist(rest_if_not_work, D).


day_constraint(Min, Element, Lst) :-
    employees_num(EmpsNum),
    list_has_ge_elements_being(Min, Element, EmpsNum, Lst).


two_days(D1, D2) :-
    % Set the full number of employees, otherwise prevent_double_shift can shorten the list
    employees_num(EmpsNum),
    length(D1, EmpsNum),
    length(D2, EmpsNum),

    % Pass the 2-day constraint first
    day_constraint(8, n, D1),
    prevent_double_shift(D1, D2),
    day_constraint(15, m, D2),
    
    % Remainder of the day constraints
    day_constraint(15, m, D1),
    day_constraint(8, n, D2),

    other_day_constraints(D1),
    other_day_constraints(D2).


prevent_double_shift([], []).
prevent_double_shift([H1|T1], [H2|T2]) :-
    (H1 == n -> dif(H2, m) ; true),
    prevent_double_shift(T1, T2).


rest_if_not_work(E) :-
    (var(E) -> E = r ; true).


show_days([]).
show_days([D|T]) :-
    show_day(D),
    show_days(T).


show_day(D) :-
    forall(member(E, D), (upcase_atom(E, U), write(U))),
    nl.


% Potentially use E as the first element
list_length_abs(N, E, [E|_]) :-
    N > 1.
list_length_abs(0, _, []).
list_length_abs(1, E, [E]).


list_has_ge_elements_being(0, _E, MaxLen, L) :-
    !,
    MaxLen >= 0,
    % Don't need E
    list_length_abs(MaxLen, _, L).

list_has_ge_elements_being(Min, E, MaxLen, [H|T]) :-
    must_be(integer, MaxLen),
    MaxLen >= 1,
    must_be(integer, Min),
    Min >= 1,
    Min =< MaxLen,
    list_has_ge_elements_being_(Min, E, MaxLen, [H|T]).

list_has_ge_elements_being_(Min, E, MaxLen, L) :-
    Min =:= MaxLen ->
        length(L, Min),
        maplist(=(E), L)
    ; MaxLen =:= 1 ->
        list_has_ge_elements_being_maxlen1_(Min, L, E)
    ;   list_has_ge_elements_being_flex_(Min, E, MaxLen, L).


list_has_ge_elements_being_maxlen1_(0, [_], _).
list_has_ge_elements_being_maxlen1_(1, [E], E).

list_has_ge_elements_being_flex_(Min, H, MaxLen, [H|T]) :-
    % Loop while unifying the element
    succ(Min0, Min),
    succ(MaxLen0, MaxLen),
    % Check whether can terminate the list early
    (Min0 =:= 0 -> true ; list_has_ge_elements_being_(Min0, H, MaxLen0, T)).

list_has_ge_elements_being_flex_(Min, E, MaxLen, [H|T]) :-
    % Ensure that the element is not already the intended value
    \  E == H,
    succ(MaxLen0, MaxLen),
    list_has_ge_elements_being_(Min, E, MaxLen0, T).