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

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

这里写目录标题

人员排班问题
问题描述
数学建模
编程求解（Cplex+JavaAPI）
求解结果

人员排班问题

随着现在产业的发展，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}$

变量

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

约束

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

目标

雇佣的员工最少，即有排班的班次总数最少： $\min \sum_{d \in D, s\in S, e \in E}x_{d,s,e}$

\begin{aligned} min & \sum_{d \in D, s \in S, e \in E} x_{d, s, e} \\ subject to & \sum_{e \in E} x_{d, s, e} \geq N_{d, s}, \forall d \in D, s \in S \\ \sum_{s \in S} x_{d, s, e} \leq 1, \forall d \in D, e \in E \\ x_{d, 3, e} + x_{d + 1, 1, e} \leq 1, \forall d \in D, e \in E \\ \sum_{d \in D, s \in S} x_{d, s, e} \leq 5, \forall e \in E \\ x_{d, s, e} \in {0, 1} \end{aligned}

min subject to d \in D, s \in S, e \in E \sum x_{d, s, e} e \in E \sum x_{d, s, e} \geq N_{d, s}, \forall d \in D, s \in S s \in S \sum x_{d, s, e} \leq 1, \forall d \in D, e \in E x_{d, 3, e} + x_{d + 1, 1, e} \leq 1, \forall d \in D, e \in E d \in D, s \in S \sum x_{d, s, e} \leq 5, \forall e \in E x_{d, s, e} \in {0, 1}

编程求解（Cplex+JavaAPI）

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

<dependency>
            <groupId>org.apache.commons</groupId>
            <artifactId>commons-csv</artifactId>
            <version>1.7</version>
        </dependency>
1
2
3
4
5

在这里插入图片描述

package main.java;

import ilog.concert.*;
import ilog.cplex.IloCplex;
import org.apache.commons.csv.CSVFormat;
import org.apache.commons.csv.CSVRecord;

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

public class EmpSchedulingProblem {


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

    /**
     * @param day   某天
     * @param shift 某个班次
     * @return 某天某班次需求的人数
     */
    public int getDemandOfEmployees(int day, int shift) {
        return demandOfEmployees[day][shift];
    }

    public EmpSchedulingProblem() 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[][] day_shift_empNum = 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));   // 晚班需要员工的数量

                //保存至二维数组，某天某班次需要的员工数量
                day_shift_empNum[day][0] = morningShiftEmpNum;
                day_shift_empNum[day][1] = middleShiftEmpNum;
                day_shift_empNum[day][2] = nightShiftEmpNum;

                this.n_employees += morningShiftEmpNum + middleShiftEmpNum + nightShiftEmpNum;
            }
            this.n_employees = (int) Math.ceil((double) (this.n_employees) / 5) + 1;
//            System.out.println("预估排班人数：" + n_employees);
            logger.info("预估排班人数：" + n_employees);
        } catch (IOException e) {
            logger.info(e.getMessage());
        }
        System.out.println(Arrays.deepToString(day_shift_empNum));

        return day_shift_empNum;
    }

    public void cplexSolve() {
        try {
            // 声明cplex优化模型
            IloCplex model = new IloCplex();
            // 声明决策变量，x_ijk表示员工i在第j天上班次k
            IloIntVar[][][] x = new IloIntVar[n_employees][n_days][n_shifts];
            for (int i = 0; i < n_employees; i++) {
                for (int j = 0; j < n_days; j++) {
                    for (int k = 0; k < n_shifts; k++) {
                        // boolVar()声明x_ijk为0-1变量
                        x[i][j][k] = model.boolVar();
                    }
                }
            }

            // 约束：每天各个班次在岗的人数符合需求
            for (int d = 0; d < days.length; d++) {
                for (int s = 0; s < shifts.length; s++) {
                    IloLinearIntExpr expr = model.linearIntExpr();
                    for (int e = 0; e < n_employees; e++) {
                        // addTerm()表示 1*x_eds
                        expr.addTerm(1, x[e][d][s]);
                    }
                    model.addGe(expr, this.getDemandOfEmployees(d, s));
                }
            }
            // 约束：每人每天最多只有一个班次
            for (int n : employees) {
                for (int d : days) {
                    IloLinearIntExpr expr = model.linearIntExpr();
                    for (int s : shifts) {
                        expr.addTerm(1, x[n][d][s]);
                    }
                    model.addLe(expr, 1);
                }
            }

            // 约束：前一天是晚班的，第二天不能是早班
            for (int e : employees) {
                for (int d : days) {
                    IloLinearIntExpr expr = model.linearIntExpr();
                    // 0 早班
                    // 1 中班
                    // 2 晚班
                    // 当天上晚班的员工，第二天不能上早班
                    expr.addTerm(1, x[e][d][2]);
                    if (d == 6) {
                        expr.addTerm(1, x[e][0][0]);
                    } else {
                        expr.addTerm(1, x[e][d + 1][0]);
                    }

                    model.addLe(expr, 1);
                }
            }

            // 约束：一周工作工作时间不能超过5天
            for (int e = 0; e < n_employees; e++) {
                IloLinearIntExpr expr = model.linearIntExpr();
                for (int d = 0; d < days.length; d++) {
                    for (int s = 0; s < shifts.length; s++) {
                        expr.addTerm(1, x[e][d][s]);
                    }
                }
                model.addLe(expr, 5);
            }

            // 目标：雇佣的员工最少，即有排班的班次总数最少
            IloLinearIntExpr expr = model.linearIntExpr();
            for (int e : employees) {
                for (int d : days) {
                    for (int s : shifts) {
                        expr.addTerm(1, x[e][d][s]);
                    }
                }
            }
            model.addMinimize(expr);

            // 打印求解结果
            if (model.solve()) {
                System.out.println("num of employees: " + n_employees);
                System.out.println("solution status: " + model.getStatus());
                System.out.println("solution value: " + model.getObjValue());

                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 (((int) model.getValue(x[e][d][s])) != 0) {
                                shift = s + 1;
                                shiftCount += 1;
                            }
                        }
                        System.out.printf("%d\t", shift);
                    }
                    System.out.printf("员工%d这周上%d个班次", e + 1, shiftCount);
                    System.out.println();
                }
            }

            model.end();
        } catch (IloException e) {
            logger.warning(e.getMessage());
        }

    }

    public static void main(String[] args) {
        try {
            EmpSchedulingProblem esp = new EmpSchedulingProblem();
            esp.cplexSolve();
        } catch (IOException e) {
            throw new RuntimeException(e);
        }
    }
}

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
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217

求解结果

信息: 预估排班人数：21
信息: 排班周期：7
信息: 每天班次：3（1，2，3）若为0则代表不排班，即休息

每个员工在那一天上第几个班，如图所示，如员工1-周1-不上班，员工2-周2-夜班；0不上班、1早班、2晚班、3夜班。

"C:\Program Files (x86)\openjdk-17.0.2_windows-x64_bin\jdk-17.0.2\bin\java.exe" "-javaagent:C:\Program Files\JetBrains\IntelliJ IDEA Community Edition 2023.2\lib\idea_rt.jar=52285:C:\Program Files\JetBrains\IntelliJ IDEA Community Edition 2023.2\bin" -Dfile.encoding=UTF-8 -classpath "C:\Users\user\IdeaProjects\cplex-project\out\production\employee-scheduling-problem;C:\Program Files\IBM\ILOG\CPLEX_Studio1263\cplex\lib\cplex.jar;C:\Users\user\.m2\repository\org\apache\commons\commons-csv\1.7\commons-csv-1.7.jar" EmpSchedulingProblem
C:\Users\user\IdeaProjects\cplex-project
12月 06, 2023 2:34:07 下午 EmpSchedulingProblem readFile
信息: 预估排班人数：21
[[5, 5, 1], [6, 4, 1], [4, 6, 1], [4, 5, 12], [5, 7, 2], [7, 7, 2], [7, 7, 1]]
Tried aggregator 1 time.
Reduced MIP has 336 rows, 441 columns, and 1617 nonzeros.
Reduced MIP has 441 binaries, 0 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.00 sec. (0.95 ticks)
Found incumbent of value 99.000000 after 0.00 sec. (4.77 ticks)
Probing time = 0.00 sec. (0.26 ticks)
Tried aggregator 1 time.
Reduced MIP has 336 rows, 441 columns, and 1617 nonzeros.
Reduced MIP has 441 binaries, 0 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.01 sec. (0.95 ticks)
Probing time = 0.00 sec. (0.26 ticks)
Clique table members: 294.
MIP emphasis: balance optimality and feasibility.
MIP search method: dynamic search.
Parallel mode: deterministic, using up to 8 threads.
Root relaxation solution time = 0.00 sec. (0.70 ticks)

        Nodes                                         Cuts/
   Node  Left     Objective  IInf  Best Integer    Best Bound    ItCnt     Gap

*     0+    0                           99.0000        0.0000           100.00%
      0     0        cutoff             99.0000                     69    0.00%

Root node processing (before b&c):
  Real time             =    0.01 sec. (7.53 ticks)
Parallel b&c, 8 threads:
  Real time             =    0.00 sec. (0.00 ticks)
  Sync time (average)   =    0.00 sec.
  Wait time (average)   =    0.00 sec.
                          ------------
Total (root+branch&cut) =    0.01 sec. (7.53 ticks)
num of employees: 21
solution status: Optimal
solution value: 99.0
        	1	2	3	4	5	6	7
employee1	0	1	0	3	2	2	2	员工1排5个班次
employee2	1	3	2	3	0	1	0	员工2排5个班次
employee3	3	2	0	3	0	1	0	员工3排4个班次
employee4	1	1	2	1	0	1	0	员工4排5个班次
employee5	1	2	0	1	1	0	2	员工5排5个班次
employee6	1	1	0	3	0	1	2	员工6排5个班次
employee7	1	1	1	1	1	0	0	员工7排5个班次
employee8	2	1	0	2	2	0	2	员工8排5个班次
employee9	2	1	0	1	1	0	1	员工9排5个班次
employee10	2	0	0	2	1	1	1	员工10排5个班次
employee11	2	0	1	2	2	1	0	员工11排5个班次
employee12	0	0	3	2	2	3	3	员工12排5个班次
employee13	0	0	1	2	1	2	2	员工13排5个班次
employee14	0	0	1	3	2	2	2	员工14排5个班次
employee15	0	0	0	3	3	2	0	员工15排3个班次
employee16	0	2	0	3	3	0	1	员工16排4个班次
employee17	0	0	2	3	2	2	1	员工17排5个班次
employee18	0	0	2	3	0	2	1	员工18排4个班次
employee19	2	0	2	3	0	1	1	员工19排5个班次
employee20	0	0	2	3	0	3	2	员工20排4个班次
employee21	0	2	0	3	2	2	1	员工21排5个班次

Process finished with exit code 0

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

相关阅读:
CentOS 安装 rabbitMQ
Springboot整合Fastdfs上传图片、缩略图、下载文件、需求：文件转存方案(springboot整合线程池多线程实现)
多线程（二）多线程的锁机制（java）
自动微分原理
2防火墙：基础知识
母线电容及其计算方法
关于简单线性代数——矩阵乘法与行列式
基于桶的排序之计数排序
这种动态规划你见过吗——状态机动态规划之股票问题(中)
centos7容器安装宝塔

原文地址：https://blog.csdn.net/qq_43276566/article/details/133402306