基于Google OR-Tools的员工排班约束不可行问题咨询

核心问题诊断 #

你的代码存在几个致命的约束逻辑错误，直接导致求解不可行：

1. 白班人员需求约束完全写错：你当前的代码要求每个员工必须做12天的8小时班，但一周只有7天，这是不可能满足的矛盾约束。正确逻辑应该是每天的白班（8小时）员工数量至少10人。
2. 连续工作约束逻辑错误：你添加的AddBoolOr约束完全不符合“连续工作若干天后休息”的需求，反而引入了无意义的限制，导致解空间被过度压缩。
3. 缺失关键约束：未实现周工作时长45-60小时、夜班人员比例需求的约束。

修复与优化方案 #

1. 修正白班人员需求约束 #

将错误的员工个人班次数量约束，替换为每日白班（shift=1，对应"8"）的总人数≥10：

// 每日白班（8小时）至少10人
foreach (int d in Range(numDays))
{
    var dayShiftWorkers = new List<BoolVar>();
    foreach (int e in Range(numEmployees))
    {
        dayShiftWorkers.Add(work[e, d, 1]);
    }
    model.Add(LinearExpr.Sum(dayShiftWorkers) >= 10);
}

2. 重构连续工作约束 #

假设要求最多连续工作5天，之后必须至少休息1天，直接约束连续工作天数不超过上限：

// 每个员工连续工作天数不超过5天
foreach (int e in Range(numEmployees))
{
    for (int d = 0; d <= numDays - 6; d++)
    {
        // 不能连续6天都工作（即d到d+5天中至少有1天休息）
        var consecutiveWork = new List<ILiteral>();
        for (int i = 0; i < 6; i++)
        {
            var isWorking = model.NewBoolVar($"is_working_{e}_{d+i}");
            // 工作即做8或12小时班次
            model.AddBoolOr(work[e, d+i, 1], work[e, d+i, 2]).OnlyEnforceIf(isWorking);
            model.AddBoolAnd(work[e, d+i, 0].Not()).OnlyEnforceIf(isWorking);
            consecutiveWork.Add(isWorking);
        }
        // 至少有一天不工作
        model.AddBoolOr(consecutiveWork.Select(b => b.Not()).ToArray());
    }
}

3. 添加周工作时长约束 #

计算每个员工每周的总工作时长，确保在45-60小时之间：

// 周工作时长45-60小时
foreach (int e in Range(numEmployees))
{
    LinearExpr totalHours = LinearExpr.Zero();
    foreach (int d in Range(numDays))
    {
        totalHours.AddTerm(work[e, d, 1], 8);
        totalHours.AddTerm(work[e, d, 2], 12);
    }
    model.Add(totalHours >= 45);
    model.Add(totalHours <= 60);
}

4. 添加夜班人员比例约束 #

假设12小时班次包含夜班工作，夜班人数即12小时班次的员工数，需为当日在岗（8+12小时班次）员工的10%-100%：

// 夜班人数为当日在岗人数的10%-100%（12小时班次视为夜班人员）
foreach (int d in Range(numDays))
{
    var onDuty = LinearExpr.Sum(Enumerable.Range(0, numEmployees)
        .Select(e => LinearExpr.Sum(work[e, d, 1], work[e, d, 2])));
    var nightWorkers = LinearExpr.Sum(Enumerable.Range(0, numEmployees)
        .Select(e => work[e, d, 2]));
    // 10%比例向上取整，避免小数问题
    model.Add(nightWorkers >= (int)Math.Ceiling(onDuty.Value * 0.1));
    model.Add(nightWorkers <= onDuty);
}

5. 移除错误的约束 #

删除你原来的“Max 3 days”和错误的白班人员约束：

// 移除这段错误代码
/*
foreach (int e in Range(numEmployees))
{
    foreach (int d in Range(2, numDays-2))
    {
        foreach (int s in Range(numShifts))
        {
            model.AddBoolOr(new ILiteral[] { work[e, d - 2, s], work[e, d, s].Not(), work[e, d + 2, s] });
        }
    }
}
*/

// 移除这段错误代码
/*
foreach (int e in Range(numEmployees))
{
    var temp = new BoolVar[numEmployees];
    foreach (int d in Range(numDays))
    {
            temp[e] = work[e, d, 1]; 
    }
    model.Add(LinearExpr.Sum(temp) == 12);
}
*/

完整优化后的代码 #

public class ShiftSchedulingSat
{
    static void Main(string[] args)
    {
        SolveShiftScheduling();
    }

    static void SolveShiftScheduling()
    {
        int numEmployees = 15;
        int numWeeks = 1;
        // Shift: "0"=休息, "8"=白班(8小时), "12"=白班+夜班(12小时)
        var shifts = new[] { "0", "8", "12" };
        var numDays = numWeeks * 7;
        var numShifts = shifts.Length;
        LinearExprBuilder obj = LinearExpr.NewBuilder();

        var model = new CpModel();

        // 三维变量：work[e,d,s]表示员工e在d天是否做s班次
        BoolVar[,,] work = new BoolVar[numEmployees, numDays, numShifts];
        foreach (int e in Range(numEmployees))
        {
            foreach (int d in Range(numDays))
            {
                foreach (int s in Range(numShifts))
                {
                    work[e, d, s] = model.NewBoolVar($"work{e}_{d}_{s}");
                }
            }
        }

        // 约束1：每日每个员工只能选择一个班次（休息/8小时/12小时）
        foreach (int e in Range(numEmployees))
        {
            foreach (int d in Range(numDays))
            {
                var dailyShifts = new BoolVar[numShifts];
                foreach (int s in Range(numShifts))
                {
                    dailyShifts[s] = work[e, d, s];
                }
                model.Add(LinearExpr.Sum(dailyShifts) == 1);
            }
        }

        // 约束2：每日白班（8小时）至少10人
        foreach (int d in Range(numDays))
        {
            var dayShiftWorkers = new List<BoolVar>();
            foreach (int e in Range(numEmployees))
            {
                dayShiftWorkers.Add(work[e, d, 1]);
            }
            model.Add(LinearExpr.Sum(dayShiftWorkers) >= 10);
        }

        // 约束3：夜班人数为当日在岗人数的10%-100%（12小时班次视为夜班人员）
        foreach (int d in Range(numDays))
        {
            var onDuty = LinearExpr.Sum(Enumerable.Range(0, numEmployees)
                .Select(e => LinearExpr.Sum(work[e, d, 1], work[e, d, 2])));
            var nightWorkers = LinearExpr.Sum(Enumerable.Range(0, numEmployees)
                .Select(e => work[e, d, 2]));
            // 10%比例向上取整，避免小数问题
            model.Add(nightWorkers >= (int)Math.Ceiling(onDuty.Value * 0.1));
            model.Add(nightWorkers <= onDuty);
        }

        // 约束4：员工周工作时长45-60小时
        foreach (int e in Range(numEmployees))
        {
            LinearExpr totalHours = LinearExpr.Zero();
            foreach (int d in Range(numDays))
            {
                totalHours.AddTerm(work[e, d, 1], 8);
                totalHours.AddTerm(work[e, d, 2], 12);
            }
            model.Add(totalHours >= 45);
            model.Add(totalHours <= 60);
        }

        // 约束5：每个员工连续工作天数不超过5天（避免连续工作过长）
        foreach (int e in Range(numEmployees))
        {
            for (int d = 0; d <= numDays - 6; d++)
            {
                // 不能连续6天都工作（d到d+5天中至少1天休息）
                var consecutiveWork = new List<ILiteral>();
                for (int i = 0; i < 6; i++)
                {
                    var isWorking = model.NewBoolVar($"is_working_{e}_{d+i}");
                    // 工作即做8或12小时班次
                    model.AddBoolOr(work[e, d+i, 1], work[e, d+i, 2]).OnlyEnforceIf(isWorking);
                    model.AddBoolAnd(work[e, d+i, 0].Not()).OnlyEnforceIf(isWorking);
                    consecutiveWork.Add(isWorking);
                }
                // 至少有一天不工作
                model.AddBoolOr(consecutiveWork.Select(b => b.Not()).ToArray());
            }
        }

        // 目标函数：最大化员工休息天数，平衡工作负载
        foreach (int e in Range(numEmployees))
        {
            foreach (int d in Range(numDays))
            {
                obj.AddTerm(work[e, d, 0], 1);
            }
        }
        model.Maximize(obj);

        // 求解器配置
        var solver = new CpSolver();
        solver.StringParameters = "num_search_workers:8, log_search_progress: true, max_time_in_seconds:60";

        var status = solver.Solve(model);

        // 输出结果
        if (status == CpSolverStatus.Optimal || status == CpSolverStatus.Feasible)
        {
            Console.WriteLine();
            var header = "          ";
            for (int w = 0; w < numWeeks; w++)
            {
                header += "M T W T F S S ";
            }
            Console.WriteLine(header);

            foreach (int e in Range(numEmployees))
            {
                var schedule = $"worker {e}: ";
                foreach (int d in Range(numDays))
                {
                    foreach (int s in Range(numShifts))
                    {
                        if (solver.BooleanValue(work[e, d, s]))
                        {
                            schedule += shifts[s] + " ";
                        }
                    }
                }
                Console.WriteLine(schedule);
            }

            Console.WriteLine("\nStatistics");
            Console.WriteLine($"  - status          : {status}");
            Console.WriteLine($"  - conflicts       : {solver.NumConflicts()}");
            Console.WriteLine($"  - branches        : {solver.NumBranches()}");
            Console.WriteLine($"  - wall time       : {solver.WallTime()}");
        }
        else
        {
            Console.WriteLine($"求解状态：{status}，无可行解");
        }
    }

    static ILiteral[] NegatedBoundedSpan(BoolVar[] works, int start, int length)
    {
        var sequence = new List<ILiteral>();
        if (start > 0)
            sequence.Add(works[start - 1]);
        foreach (var i in Range(length))
            sequence.Add(works[start + i].Not());
        if (start + length < works.Length)
            sequence.Add(works[start + length]);
        return sequence.ToArray();
    }

    static IEnumerable<int> Range(int start, int stop)
    {
        foreach (var i in Enumerable.Range(start, stop - start))
            yield return i;
    }

    static IEnumerable<int> Range(int stop)
    {
        return Range(0, stop);
    }
}

额外优化建议 #

1. 目标函数优化：当前目标是最大化休息天数，你可以根据实际需求调整，比如最小化12小时班次的人数，或平衡员工的工作时长差异。
2. 约束松弛：如果仍然不可行，可以暂时放宽部分约束（比如将周工作时长范围调整为40-65小时，或连续工作天数上限改为6天），逐步排查哪个约束导致不可行。
3. 变量简化：如果夜班和12小时班次强绑定，可以不用新增夜班变量，直接用12小时班次代表夜班人员，减少变量数量提升求解速度。

内容的提问来源于stack exchange，提问作者Predator1987