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

Question

I am new to or-tools and I am trying to implement something similar to the employee scheduling example from here.

I have a matrix that represents which employee is assigned to which shift:

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

An employee has a number of hours he is supposed to work per week and a shift has an individual duration. These numbers are stored in two separate arrays.

How would I create an objective function to minimize the deviation between the sum of the assigned shifts' durations and the employee's hours per week, so that each employee comes as close to his goal as possible?

Thanks in advance :)

Answer 1

You can compute the total number of hours per employee per week in another set of IntVar's and then compute the square of the difference of them to the target hours per week. The objective would be to minimize the sum of the deviations. (Least squares principle).

Here is an example code of how to do it:

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_;
        }
    }
}

If all the shifts have the same length, and you only need to ensure each employee has roughly the same number of shifts, then you could eliminate the deviation variable and simply minimize the sum of the squares of the number of shifts for each employee.

Here is a sample output of the above; the solver found 9 solutions with continually decreasing objective, the last one reported was:

...
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

You'll have to add any other constraints you need such as each shift being covered only once, etc.

Edit: After posting, I realized there are some issues with AddMultiplicationEquality when the operands span positive and negative values, which is the case here (deviations to target working week can be both positive and negative). During some testing the model here indicated infeasibility where there were obvious solutions.

By changing the objective to "Minimize the maximum absolute value of the deviations" instead of "Minimize the sum of the squares of the deviations" this problem can be avoided. This would then be the required code section to compute the 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);