基于Prolog的企业50人30天员工排班问题求解与实现咨询

核心解决思路 #

• 约束分层处理：先处理每日/跨日的局部约束（早中晚班人数、夜班转天禁早班）缩小搜索空间，再验证全局的连续7天休息约束，提升搜索效率。
• 班次编码优化：将M/E/N/R映射为数字1/2/3/0，利用Prolog内置的计数工具快速统计班次数量，替代原代码中自定义的低效计数逻辑。
• 维度转换验证：把「每日员工排班表」转置为「员工每日班次序列」，方便按员工维度遍历所有连续7天的时间窗口，检查休息天数是否达标。

完整代码实现 #

% 基础配置
days_in_month(30).
employees_num(50).

% 班次与数字映射：简化CLP计数，r=0代表休息，m/e/n对应1/2/3
shift_code(m, 1).
shift_code(e, 2).
shift_code(n, 3).
shift_code(r, 0).

go :-
    days_in_month(Days),
    employees_num(EmpsNum),
    % 生成30天的排班表框架：每日对应50个员工的班次编码
    length(DailyShifts, Days),
    maplist(length_(EmpsNum), DailyShifts),
    % 依次应用所有约束
    apply_daily_constraints(DailyShifts),
    apply_interday_constraints(DailyShifts),
    apply_weekly_rest_constraints(DailyShifts),
    % 解码为可读的班次原子并输出
    maplist(decode_shift_list, DailyShifts, HumanReadableShifts),
    show_days(HumanReadableShifts),
    % 取消下方注释可生成多种解
    % fail; true.

% 辅助谓词：指定列表长度
length_(Len, List) :- length(List, Len).

% 1. 每日约束：早班≥15人，晚班≥10人，夜班≥8人
apply_daily_constraints([]).
apply_daily_constraints([Day|Rest]) :-
    count(1, Day, MCount), MCount ≥ 15,
    count(2, Day, ECount), ECount ≥ 10,
    count(3, Day, NCount), NCount ≥ 8,
    apply_daily_constraints(Rest).

% 2. 跨日约束：当日值夜班的员工，次日不得值早班
apply_interday_constraints([_]).
apply_interday_constraints([PrevDay, CurrDay|Rest]) :-
    maplist(prev_n_curr_not_m, PrevDay, CurrDay),
    apply_interday_constraints([CurrDay|Rest]).

prev_n_curr_not_m(PrevShift, CurrShift) :-
    (PrevShift = 3 -> CurrShift ≠ 1 ; true).

% 3. 连续7天休息约束：每个员工任意连续7天内至少2天休息
apply_weekly_rest_constraints(DailyShifts) :-
    % 转置排班表：从「每日员工」转为「员工每日」的班次序列
    transpose(DailyShifts, EmployeeShifts),
    maplist(employee_weekly_rest_check, EmployeeShifts).

employee_weekly_rest_check(Shifts) :-
    % 遍历所有连续7天的窗口（共30-7+1=24个）
    forall(between(1, 24, Start),
           (slice(Shifts, Start, 7, Window),
            count(0, Window, RestCount),
            RestCount ≥ 2)).

% 辅助谓词：截取列表中从Start位置开始的Len个元素
slice(List, Start, Len, Slice) :-
    length(Prefix, Start-1),
    append(Prefix, Temp, List),
    length(Slice, Len),
    append(Slice, _, Temp).

% 将数字编码解码为班次原子
decode_shift_list([], []).
decode_shift_list([Code|Codes], [Shift|Shifts]) :-
    shift_code(Shift, Code),
    decode_shift_list(Codes, Shifts).

% 输出排班表
show_days([]).
show_days([Day|Rest]) :-
    show_day(Day),
    show_days(Rest).

show_day(Day) :-
    forall(member(Shift, Day), (upcase_atom(Shift, U), write(U))),
    nl.

代码关键说明 #

1. 高效计数：用内置的count/4替代原代码自定义的计数逻辑，大幅提升约束检查效率。
2. 转置操作：通过transpose/2（SWI-Prolog内置谓词）转换排班表维度，让员工的连续班次序列更易处理。
3. 窗口验证：slice/4精准截取每个员工的连续7天班次窗口，结合count/4快速统计休息天数，确保满足全局约束。
4. 多解生成：取消go/0中fail; true.的注释，程序会自动遍历所有可能的解，输出多种排班方案。

内容的提问来源于stack exchange，提问作者Θεοφανης Γιαννακοπουλος