Google OR-工具：员工排班 |最小化分配给员工的小时数与他应该工作的小时数之间的偏差

Question

我是 or-tools 的新手，我正在尝试实现类似于 here 中的员工调度示例的东西。

我有一个矩阵，表示哪个员工被分配到哪个班次：

IntVar[,] assign = new IntVar[numEmployees, numShifts];

一个员工每周应该工作几个小时，一个班次有一个单独的持续时间。这些数字存储在两个单独的数组中。

我将如何创建一个 objective 函数来最小化分配的轮班持续时间总和与员工每周工时之间的偏差，以便每个员工尽可能接近他的目标？

提前致谢:)

Answer 1

您可以计算另一组 IntVar 中每个员工每周的总小时数，然后计算它们与每周目标小时数之差的平方。 objective 将最小化偏差的总和。（最小二乘原理）。

下面是一个如何操作的示例代码：

using Google.OrTools.Sat;
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;

namespace SO69498730_MinimizeDeviation
{
    class Program
    {
        static void Main(string[] args)
        {
            try
            {
                Google.OrTools.Sat.CpModel model = new CpModel();
                ORModel myModel = new ORModel();
                myModel.initModel(model);
                IntVar[] decisionVariables = myModel.decisionVariables;

                // Creates a solver and solves the model.
                CpSolver solver = new CpSolver();
                VarArraySolutionPrinter solutionPrinter = new VarArraySolutionPrinter(myModel.variablesToPrintOut);
                solver.SearchAllSolutions(model, solutionPrinter);
                Console.WriteLine(String.Format("Number of solutions found: {0}",
                    solutionPrinter.SolutionCount()));
            }
            catch (Exception e)
            {
                Console.WriteLine(e.Message);
                Console.WriteLine(e.StackTrace);
                throw;
            }

            Console.WriteLine("OK");
            Console.ReadKey();
        }
    }

    class ORModel
    {
        const int numEmployees = 3;
        const int numShifts = 21;
        long[] hoursPerShift = new long[numShifts] { 9, 8, 7, 9, 8, 7, 9, 8, 7, 9, 8, 7, 9, 8, 7, 9, 8, 7, 9, 8, 7 };
        long[] targetWeeklyHours = new long[numEmployees] { 40, 40, 24 };
        const long totalShiftsNeeded = 15;
        IntVar[,] assign = new IntVar[numEmployees, numShifts];
        IntVar[] hoursPerWeek = new IntVar[numEmployees];
        IntVar[] diff = new IntVar[numEmployees];
        IntVar[] deviation = new IntVar[numEmployees];
        IntVar objective;

        public IntVar[] decisionVariables
        {
            get
            {
                return assign.Cast<IntVar>().ToArray();
            }
        }

        public IntVar[] variablesToPrintOut
        {
            get
            {
                List<IntVar> vars = new List<IntVar>(assign.Cast<IntVar>());
                vars.AddRange(hoursPerWeek);
                vars.AddRange(diff);
                vars.AddRange(deviation);
                vars.Add(objective);
                return vars.ToArray();
            }
        }

        public void initModel(CpModel model)
        {
            // Shifts per employee
            for (int i = 0; i < numEmployees; i++)
            {
                for (int j = 0; j < numShifts; j++)
                {
                    assign[i, j] = model.NewBoolVar($"Employee {i} shift {j}");
                }
            }

            // Total shifts to cover
            model.Add(LinearExpr.Sum(assign.Cast<IntVar>()) == totalShiftsNeeded);

            // Sum of hours for each employee
            long maxHours = hoursPerShift.Max() * numShifts;
            for (int i = 0; i < numEmployees; i++)
            {
                hoursPerWeek[i] = model.NewIntVar(0L, maxHours, $"Hours for employee {i}");
                List<LinearExpr> thisEmployeesHours = new List<LinearExpr>();
                for (int j = 0; j < numShifts; j++)
                {
                    thisEmployeesHours.Add(hoursPerShift[j] * assign[i, j]);
                }
                model.Add(LinearExpr.Sum(thisEmployeesHours) == hoursPerWeek[i]);
            }

            // Deviation = (hours per week for an employee - target hours per week) squared
            long maxDev = maxHours * maxHours;
            for (int i = 0; i < numEmployees; i++)
            {
                deviation[i] = model.NewIntVar(0L, maxDev, $"Deviation for employee {i}");
                diff[i] = model.NewIntVar(-maxDev, maxDev, $"Diff for employee {i}");
                model.Add(diff[i] == hoursPerWeek[i] - targetWeeklyHours[i]);
                IntVar[] multiplicands = new IntVar[] { diff[i], diff[i] };
                model.AddMultiplicationEquality(deviation[i], multiplicands);
            }

            // Objective: minimize sum of deviations
            objective = model.NewIntVar(0L, numEmployees * maxDev, "Objective");
            model.Add(LinearExpr.Sum(deviation) == objective);

            model.Minimize(objective);
        }
    }

    public class VarArraySolutionPrinter : CpSolverSolutionCallback
    {
        private int solution_count_;
        private IntVar[] variables;

        public VarArraySolutionPrinter(IntVar[] variables)
        {
            this.variables = variables;
        }
        public override void OnSolutionCallback()
        {
            using (TextWriter sw = Console.Out)
            {
                sw.WriteLine(String.Format("Solution #{0}: time = {1:F2} s;",
                solution_count_, WallTime()));
                foreach (IntVar v in variables)
                {
                    sw.Write(
                    String.Format(" {0} = {1}\r\n", v.ShortString(), Value(v)));
                }
                solution_count_++;
                sw.WriteLine();
            }
            if (solution_count_ >= 10)
            {
                StopSearch();
            }
        }
        public int SolutionCount()
        {
            return solution_count_;
        }
    }
}

如果所有班次的长度相同，而您只需要确保每个员工的轮班次数大致相同，那么您可以消除 deviation 变量并简单地最小化平方和每个员工的班次数。

这是上面的示例输出；求解器找到了 9 个不断递减 objective 的解，最后一个报告是：

...
Solution #8: time = 0,62 s;
 Employee 0 shift 0 = 0
 Employee 0 shift 1 = 0
 Employee 0 shift 2 = 1
 Employee 0 shift 3 = 0
 Employee 0 shift 4 = 0
 Employee 0 shift 5 = 1
 Employee 0 shift 6 = 0
 Employee 0 shift 7 = 0
 Employee 0 shift 8 = 1
 Employee 0 shift 9 = 0
 Employee 0 shift 10 = 0
 Employee 0 shift 11 = 1
 Employee 0 shift 12 = 0
 Employee 0 shift 13 = 0
 Employee 0 shift 14 = 0
 Employee 0 shift 15 = 0
 Employee 0 shift 16 = 0
 Employee 0 shift 17 = 1
 Employee 0 shift 18 = 0
 Employee 0 shift 19 = 0
 Employee 0 shift 20 = 1
 Employee 1 shift 0 = 0
 Employee 1 shift 1 = 0
 Employee 1 shift 2 = 1
 Employee 1 shift 3 = 0
 Employee 1 shift 4 = 0
 Employee 1 shift 5 = 1
 Employee 1 shift 6 = 0
 Employee 1 shift 7 = 0
 Employee 1 shift 8 = 0
 Employee 1 shift 9 = 0
 Employee 1 shift 10 = 0
 Employee 1 shift 11 = 1
 Employee 1 shift 12 = 0
 Employee 1 shift 13 = 0
 Employee 1 shift 14 = 1
 Employee 1 shift 15 = 0
 Employee 1 shift 16 = 0
 Employee 1 shift 17 = 1
 Employee 1 shift 18 = 0
 Employee 1 shift 19 = 0
 Employee 1 shift 20 = 1
 Employee 2 shift 0 = 0
 Employee 2 shift 1 = 1
 Employee 2 shift 2 = 0
 Employee 2 shift 3 = 0
 Employee 2 shift 4 = 1
 Employee 2 shift 5 = 0
 Employee 2 shift 6 = 0
 Employee 2 shift 7 = 0
 Employee 2 shift 8 = 0
 Employee 2 shift 9 = 0
 Employee 2 shift 10 = 0
 Employee 2 shift 11 = 0
 Employee 2 shift 12 = 0
 Employee 2 shift 13 = 0
 Employee 2 shift 14 = 0
 Employee 2 shift 15 = 0
 Employee 2 shift 16 = 0
 Employee 2 shift 17 = 0
 Employee 2 shift 18 = 0
 Employee 2 shift 19 = 1
 Employee 2 shift 20 = 0
 Hours for employee 0 = 42
 Hours for employee 1 = 42
 Hours for employee 2 = 24
 Diff for employee 0 = 2
 Diff for employee 1 = 2
 Diff for employee 2 = 0
 Deviation for employee 0 = 4
 Deviation for employee 1 = 4
 Deviation for employee 2 = 0
 Objective = 8

Number of solutions found: 9
OK

您必须添加您需要的任何其他约束，例如每个班次只涵盖一次等。

编辑：发布后，我意识到当操作数跨越正值和负值时，AddMultiplicationEquality 存在一些问题，这里就是这种情况（与目标工作周的偏差可以是正值也可以是负值）。在一些测试中，此处的模型表明存在明显解决方案的不可行性。

通过将objective改为“最小化偏差的最大绝对值”而不是“最小化偏差的平方和”可以避免这个问题。这将是计算 objective:

所需的代码部分

            // Deviation = Abs(hours per week for an employee - target hours per week)
            for (int i = 0; i < numEmployees; i++)
            {
                deviation[i] = model.NewIntVar(0, maxHours, $"Absolute deviation for employee {i}");
                diff[i] = model.NewIntVar(-maxHours, maxHours, $"Deviation for employee {i}");
                model.Add(diff[i] == hoursPerWeek[i] - targetWeeklyHours[i]);
                IntVar minusDiff = model.NewIntVar(-maxHours, maxHours, $"-Deviation for employee {i}");
                model.Add(minusDiff == -diff[i]);
                IntVar[] operands = new IntVar[] { diff[i], minusDiff };
                model.AddMaxEquality(deviation[i], operands);
            }

            // Objective: minimize the maximum deviation
            objective = model.NewIntVar(0L, numEmployees * maxHours, "Objective");
            model.AddMaxEquality(objective, deviation);

            model.Minimize(objective);

Google OR-工具：员工排班 |最小化分配给员工的小时数与他应该工作的小时数之间的偏差

Google OR-Tools: Employee Scheduling | Minimze the deviation between how many hours an employee is assigned and how many hours he is supposed to work

c#

optimization

constraint-programming

or-tools