• 基于or-tools的人员排班问题建模求解（JavaAPI）

    基于OR-Tools的人员排班问题建模求解（JavaAPI）


    使用Java调用or-tools实现了阿里mindopt求解器的案例（https://opt.aliyun.com/platform/case）人员排班问题。

    随着现在产业的发展，7*24小时服务的需要，人员排班的问题，逐渐成为了企业管理中的重要环节。人员排班在许多行业都具有广泛的应用价值，制造业， 医疗行业，餐饮业，零售业，旅游业，客服中心等。总之，人员排班在各行各业都具有重要的实际应用价值，可以帮助企业和机构提高管理效率、降低成本，同时提升员工的工作满意度和整体效能。

    人员排班问题在建模时需要考虑多种约束条件：

    • 用工需求约束：根据各岗位的工作任务和生产要求，保证每个岗位在每个时间段内有足够的员工进行工作。
    • 员工能力约束：不同岗位可能需要不同的技能和经验，需要确保安排到相应岗位的员工具备相关的能力和资质。
    • 工作时间约束：员工的工作时间需要遵守相关法律法规，比如每天工作时间上限、休息时间要求等。此外，还需要考虑员工的工作时间偏好，如部分员工可能只能接受特定时间段的工作安排。
    • 连续工作天数约束：为保证员工的工作质量和身体健康，通常要求连续工作天数不超过一定限制。以及员工在一定时间周期内有休假要求，需要确保他们的休假安排得到满足。
    • 公平性约束：为保障员工的权益，要求在满足以上约束的前提下，尽量平衡各员工的工作时间和任务分配，避免出现工作负担不均衡的情况。
    • 员工偏好：如每个员工有自己更喜欢的上班的时间、岗位、或者协作同事配合等。

    我们需要考虑企业内各岗位的需求、员工的工作能力以及工作时间的限制等因素。此外，还需关注企业成本与员工满意度的权衡，以确保在合理控制成本的前提下，最大程度地提高员工的工作满意度。属于一个约束复杂，且多目标的问题。在用数学规划方法进行排班时，建议做一些业务逻辑简化问题，否则容易出现问题太大或者不可解的情况。

    下面我们将通过一个简单的例子，讲解如何使用数学规划的方法来做人员排班。

    一、人员排班问题

    个公司有客服岗工作需要安排，不同时间段有不同的用户需求。该公司安排员工上班的班次有三种：早班8-16点、晚班16-24点和夜班0-8点。一周员工最多安排5天上班，最少休息2天。需要保障值班员工能满足需求，且要保障员工休息时间，如前一天安排晚班后，第二天不能安排早班。

    请问怎么安排总上班的班次最少，此时的班表是什么样的？

    二、数学建模

    首先根据工作量预估每天早、中、晚三个班次需要的最少的上班人数。然后我们根据值班最大值，预估我们需要的人数c。

    集合

    • 一周日期 D = 1，2，…7
    • 班次的编号 S = 1， 2，3
    • 员工编号先根据预估设 E=1,2,…c

    参数

    • 每天d每个班次s的需求在岗人数 N d , s N_{d,s} Nd,s​

    变量

    • x d , s , e x_{d,s,e} xd,s,e​代表在d天，班次s上，员工e的上班状态，0代表没有值班，1代表值班。

    约束

    • 每天各个班次在岗的人数符合需求： ∑ e ∈ E x d , s , e ≥ N d , s , ∀ d ∈ D , s ∈ S \sum_{e\in E}x_{d,s,e} \geq N_{d,s}, \forall d \in D, s \in S ∑e∈E​xd,s,e​≥Nd,s​,∀d∈D,s∈S
    • 每人每天最多只有一个班次，即 ∑ s ∈ S x d , s , e ≤ 1 , ∀ d ∈ D , e ∈ E \sum_{s\in S}x_{d,s,e} \leq 1, \forall d \in D, e \in E ∑s∈S​xd,s,e​≤1,∀d∈D,e∈E
    • 前一天是晚班的，第二天不能是早班： x d , 3 , e + x d + 1 , 1 , e ≤ 1 , ∀ d ∈ D , e ∈ E x_{d,3,e}+x_{d+1,1,e} \leq 1 ,\forall d \in D, e \in E xd,3,e​+xd+1,1,e​≤1,∀d∈D,e∈E
    • 一周工作工作时间不能超过5天： ∑ d ∈ D , s ∈ S x d , s , e ≤ 5 , ∀ e ∈ E \sum_{d\in D,s \in S}x_{d,s,e} \leq 5, \forall e \in E ∑d∈D,s∈S​xd,s,e​≤5,∀e∈E

    目标

    • 雇佣的员工最少，即有排班的班次总数最少： min ⁡ ∑ d ∈ D , s ∈ S , e ∈ E x d , s , e \min \sum_{d \in D, s\in S, e \in E}x_{d,s,e} min∑d∈D,s∈S,e∈E​xd,s,e​

    min ⁡ ∑ d ∈ D , s ∈ S , e ∈ E x d , s , e subject to ∑ e ∈ E x d , s , e ≥ N d , s , ∀ d ∈ D , s ∈ S ∑ s ∈ S x d , s , e ≤ 1 , ∀ d ∈ D , e ∈ E x d , 3 , e + x d + 1 , 1 , e ≤ 1 , ∀ d ∈ D , e ∈ E ∑ d ∈ D , s ∈ S x d , s , e ≤ 5 , ∀ e ∈ E x d , s , e ∈ { 0 , 1 } min∑d∈D,s∈S,e∈Exd,s,esubject to∑e∈Exd,s,e≥Nd,s,∀d∈D,s∈S∑s∈Sxd,s,e≤1,∀d∈D,e∈Exd,3,e+xd+1,1,e≤1,∀d∈D,e∈E∑d∈D,s∈Sxd,s,e≤5,∀e∈Exd,s,e∈{0,1} minsubject to​d∈D,s∈S,e∈E∑​xd,s,e​e∈E∑​xd,s,e​≥Nd,s​,∀d∈D,s∈Ss∈S∑​xd,s,e​≤1,∀d∈D,e∈Exd,3,e​+xd+1,1,e​≤1,∀d∈D,e∈Ed∈D,s∈S∑​xd,s,e​≤5,∀e∈Exd,s,e​∈{0,1}​​

    三、编程求解（ortools+JavaAPI）

    复制代码不能直接运行，需要在IDEA pom.xml中导入阿帕奇读取csv文件的依赖，并且需要导入ortools的maven依赖。
    数据可在文章开头阿里mindopt案例地址中获取。

    <dependency>
            <groupId>org.apache.commons</groupId>
            <artifactId>commons-csv</artifactId>
            <version>1.7</version>
        </dependency>

    • 1
    • 2
    • 3
    • 4
    • 5
    package main.java.mindoptdemo;

import com.google.ortools.Loader;
import com.google.ortools.sat.*;
import org.apache.commons.csv.CSVFormat;
import org.apache.commons.csv.CSVRecord;

import java.io.File;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.logging.Logger;
import java.io.IOException;
import java.io.Reader;
import java.nio.file.Files;
import java.nio.file.Paths;
import java.util.stream.IntStream;

public class EmployeeSchedulingProblem {
    public int n_shifts;
    public int n_days;
    public int n_employees;
    int[] days;
    int[] shifts;
    int[] employees;
    int[][] demandOfEmployees;
    public static Logger logger = Logger.getLogger("myLogger");

    public int getDemandOfEmployees(int day, int shift) {
        return demandOfEmployees[day][shift];
    }

    public EmployeeSchedulingProblem() throws IOException {
        demandOfEmployees = this.readFile();
        employees = IntStream.range(0, n_employees).toArray();
        days = IntStream.range(0, n_days).toArray();
        shifts = IntStream.range(0, n_shifts).toArray();
    }

    public int[][] readFile() throws IOException {
        this.n_shifts = 0;
        try (Reader reader = Files.newBufferedReader(Paths.get("src/main/java/mindoptdemo/班次.csv"))) {
            Iterable<CSVRecord> records = CSVFormat.DEFAULT.parse(reader);
            records.iterator().next(); // 跳过第一行
            for (CSVRecord record : records) {
                String shift = (record.get(0));   // 星期1到星期7，索引为0，故-1
                n_shifts += 1;
            }


        } catch (IOException e) {
            logger.warning(e.getMessage());
        }
        // 调度周期：7天，3班倒
        this.n_days = (int) Files.lines(Paths.get(new File("src/main/java/mindoptdemo/需求人数.csv").getPath())).count() - 1;
        int[][] demandOfEmps = new int[n_days][n_shifts];

        // commons-csv读取csv文件，需要导入依赖
        try (Reader reader = Files.newBufferedReader(Paths.get("src/main/java/mindoptdemo/需求人数.csv"))) {
            Iterable<CSVRecord> records = CSVFormat.DEFAULT.parse(reader);
            records.iterator().next(); // 跳过第一行
            for (CSVRecord record : records) {

                int day = Integer.parseInt(record.get(0)) - 1;   // 星期1到星期7，索引为0，故-1
                int morningShiftEmpNum = Integer.parseInt(record.get(1)); // 早班需要员工的数量
                int middleShiftEmpNum = Integer.parseInt(record.get(2));  // 中班需要员工的数量
                int nightShiftEmpNum = Integer.parseInt(record.get(3));   // 晚班需要员工的数量

                //保存至二维数组，某天某班次需要的员工数量
                demandOfEmps[day][0] = morningShiftEmpNum;
                demandOfEmps[day][1] = middleShiftEmpNum;
                demandOfEmps[day][2] = nightShiftEmpNum;
                this.n_employees += morningShiftEmpNum + middleShiftEmpNum + nightShiftEmpNum;
            }
            this.n_employees = (int) Math.ceil((double) (this.n_employees) / 5) + 1;
        } catch (IOException e) {
            logger.info(e.getMessage());
        }

        return demandOfEmps;
    }

    public void orToolssolve() {
        Loader.loadNativeLibraries();

        // 声明模型
        CpModel model = new CpModel();
        // 初始化决策变量
        Literal[][][] x = new Literal[n_employees][n_days][n_shifts];

        for (int n : employees) {
            for (int d : days) {
                for (int s : shifts) {
                    x[n][d][s] = model.newBoolVar("shifts_n" + n + "d" + d + "s" + s);
                }
            }
        }

        // 约束：每天各个班次在岗的人数符合需求
        for (int day = 0; day < days.length; day++) {
            for (int shift = 0; shift < shifts.length; shift++) {
                LinearExprBuilder numShiftsWorked = LinearExpr.newBuilder();

                for (int empNum = 0; empNum < n_employees; empNum++) {
                    numShiftsWorked.add(x[empNum][day][shift]);
                }
                model.addLinearConstraint(numShiftsWorked, this.getDemandOfEmployees(day, shift), n_employees);
            }
        }
        // 约束：每人每天最多只有一个班次
        for (int n : employees) {
            for (int d : days) {
                List<Literal> work = new ArrayList<>();
                for (int s : shifts) {
                    work.add(x[n][d][s]);
                }
                model.addAtMostOne(work);
            }
        }
        // 约束：前一天是晚班的，第二天不能是早班
        for (int e : employees) {
            for (int d : days) {
                List<Literal> work = new ArrayList<>();
                work.add(x[e][d][2]);
                if (d == 6) {
                    work.add(x[e][0][0]);
                } else {
                    work.add(x[e][d + 1][0]);
                }

                model.addAtMostOne(work);
            }
        }
        // 约束：一周工作工作时间不能超过5天
        for (int empNum = 0; empNum < n_employees; empNum++) {
            LinearExprBuilder expr = LinearExpr.newBuilder();
            for (int day = 0; day < days.length; day++) {
                for (int shift = 0; shift < shifts.length; shift++) {
                    expr.add(x[empNum][day][shift]);
                }
            }
            model.addLinearConstraint(expr, 0, 5);
        }

        // 目标：雇佣的员工最少，即有排班的班次总数最少
        LinearExprBuilder obj = LinearExpr.newBuilder();
        for (int n : employees) {
            for (int d : days) {
                for (int s : shifts) {
                    obj.add(x[n][d][s]);
                }
            }
        }
        model.minimize(obj);

        // 求解
        CpSolver solver = new CpSolver();
        CpSolverStatus status = solver.solve(model);

        if (status == CpSolverStatus.OPTIMAL || status == CpSolverStatus.FEASIBLE) {
            System.out.printf("%-8s", " ");
            for (int d = 0; d < n_days; d++) {
                System.out.printf("\t%d", d + 1);
            }
            System.out.println();

            for (int e : employees) {
                System.out.printf("employee%d\t", e + 1);
                int shiftCount = 0;
                for (int d : days) {
                    int shift = 0;

                    for (int s : shifts) {
                        if (solver.booleanValue(x[e][d][s])) {
                            shift = s + 1;
                            shiftCount += 1;
                        }
                    }
                    System.out.printf("%d\t", shift);
                }
                System.out.printf("员工%d这周上%d个班次", e + 1, shiftCount);
                System.out.println();
            }
        } else {
            System.out.printf("No optimal solution found !");
        }
    }

    public static void main(String[] args) throws IOException {
        EmployeeSchedulingProblem esp = new EmployeeSchedulingProblem();
        esp.orToolssolve();
    }A
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140
    • 141
    • 142
    • 143
    • 144
    • 145
    • 146
    • 147
    • 148
    • 149
    • 150
    • 151
    • 152
    • 153
    • 154
    • 155
    • 156
    • 157
    • 158
    • 159
    • 160
    • 161
    • 162
    • 163
    • 164
    • 165
    • 166
    • 167
    • 168
    • 169
    • 170
    • 171
    • 172
    • 173
    • 174
    • 175
    • 176
    • 177
    • 178
    • 179
    • 180
    • 181
    • 182
    • 183
    • 184
    • 185
    • 186
    • 187
    • 188
    • 189
    • 190
    • 191
    • 192
    • 193
    • 194

    四、求解结果

    每个员工在那一天上第几个班，本文or-tools求解结果，如图所示，如员工1-周1-上夜班，员工2-周1-不上班；0不上班、1早班、2晚班、3夜班。

            	1	2	3	4	5	6	7
employee1	3	0	0	3	0	3	2	员工1这周上4个班次
employee2	0	1	3	2	1	0	1	员工2这周上5个班次
employee3	2	0	0	3	0	1	1	员工3这周上4个班次
employee4	2	0	2	1	3	0	1	员工4这周上5个班次
employee5	0	1	2	2	2	2	0	员工5这周上5个班次
employee6	0	0	1	3	0	1	2	员工6这周上4个班次
employee7	2	2	1	2	2	0	0	员工7这周上5个班次
employee8	1	0	0	3	2	3	2	员工8这周上5个班次
employee9	0	1	0	3	0	2	2	员工9这周上4个班次
employee10	0	1	0	3	0	2	1	员工10这周上4个班次
employee11	0	2	2	3	2	0	1	员工11这周上5个班次
employee12	1	2	0	3	2	0	1	员工12这周上5个班次
employee13	2	1	0	3	0	2	3	员工13这周上5个班次
employee14	1	0	0	3	2	1	1	员工14这周上5个班次
employee15	0	2	1	3	0	2	0	员工15这周上4个班次
employee16	1	0	0	2	1	1	2	员工16这周上5个班次
employee17	2	0	1	1	1	1	0	员工17这周上5个班次
employee18	0	0	2	3	2	1	2	员工18这周上5个班次
employee19	0	3	2	1	3	2	0	员工19这周上5个班次
employee20	0	0	2	1	1	2	2	员工20这周上5个班次
employee21	1	1	0	2	1	1	0	员工21这周上5个班次

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
  • 相关阅读:
    GO语言接入支付宝
    智汀教你如何用手机远程控制智能门锁
    SCI论文投稿经验分享，建议收藏！
    Python 图_系列之基于邻接矩阵实现广度、深度优先路径搜索算法
    简论UWB三种定位算法的区别
    Go类型嵌入介绍和使用类型嵌入模拟实现“继承”
    RabbitMQ项目实战（二）
    java计算机毕业设计ssm框架的天气预报系统
    servlet---前端代码发送
    提高APP安全性的必备加固手段——深度解析代码混淆技术
  • 原文地址：https://blog.csdn.net/qq_43276566/article/details/133487058