建模实战|最优化员工排班（附python代码）-使用Ortools求解器 - 知乎

安宇雨 - 随手采集
2025-12-21 21:52:00
随手采集
0000-未整理-等待研究

转载请注明出处。无形忍者：运筹优化实战案例-最优化员工排班

1 问题描述

下图分别为员工信息（包含每日最短工作时长、最长工作时长、单位小时工作薪资、可工作时间）、每小时最短工作人数，要求满足以下条件：

a)如果员工进行工作，则需满足个人工作时长不低于最小值、不高于最大值
b)每位员工每天至多工作一个班次，每个班次都是一段连续的时间
c)满足每小时最短工作人数

请给出一种分配方案，使得每日支付员工的薪水最少。

员工姓名

最小工作小时

最大工作小时

每小时工资

可用性

王小明

6-20

李婷婷

张伟华

刘晓红

陈建国

杨丽丽

黄强强

6-18

赵静静

周文华

吴小刚

孙雅雅

0-6, 18-24

胡明明

朱强强

8-16

曾丽丽

许鹏飞

马晓霞

郑伟伟

12-24

谢娟娟

彭军军

方美丽

每个时段需要的最少员工数：

2 建模

参数：

决策变量：创建20*24*24个变量
，表示员工在时间到时间是否工作注意：表示员工在工作，如果，则会造成在无人工作xd,i,jbinary，表示员工d在时间i到时间j是否工作0≤i≤231≤j≤24注意：i=6,j=9表示员工在6:00−9:00工作，如果maxj=23，则会造成在23:00−24:00无人工作\begin{matrix}{{x}_{d,i,j}}\quad binary，表示员工d在时间i到时间j是否工作\0\le i\le 23\1\le j\le 24\注意：i=6,j=9表示员工在6:00-9:00工作，如果maxj=23\，则会造成在23:00-24:00无人工作\end{matrix}

目标函数和约束：

目标函数：约束目标函数： min∑d∈D∑i=023∑j>i24(j−i)∗xd,i,j∗cd 约束: ∑i=023∑j>i24xd,i,j≤∑i=startdi= end d∑j>ij= end d&mind≤j−i≤ max dxd,i,j≤1,∀d∈D∑d∈D∑i=023∑j>i&i≤c<j24xd,i,j≥Rc,∀c∈C\begin{array}{l} \text { 目标函数： } \ \min \sum_{d \in D} \sum_{i=0}^{23} \sum_{j>i}^{24}(j-i) x_{d, i, j} c_{d} \ \text { 约束: } \ \sum_{i=0}^{23} \sum_{j>i}^{24} x_{d, i, j} \leq \sum_{i={ start }_{d}}^{i=\text { end }_{d}} \sum_{j>i}^ {j=\text { end }_{d} \& \min _{d} \leq j-i \leq \text { max }_{d}} x_{d, i, j} \leq 1, \forall d \in D \ \sum_{d \in D} \sum_{i=0}^{23} \sum_{j>i \& i \leq c<j}^{24} x_{d, i, j} \geq R_{c}, \forall c \in C \ \end{array}

目标函数与约束说明：

目标函数：使得每日支付员工的薪水最少

约束1：如果员工d进行工作，则需满足个人工作时长不低于最小值、不高于最大值每位员工每天至多工作一个班次，每个班次都是一段连续的时间，员工 d 只工作一个班次，即至多只有一组 (i,j) 使得 xd,i,j x_{d, i, j} ≠0 ，从员工可开始工作时间开始扫描，在大于员工最少上班时间、小于最长上班时间内搜索，到员工必须结束工作时间为止，至多有一个状态变量为1

约束2：满足每小时最少工作人数

3.代码实现-ortools：

from ortools.sat.python import cp_model

# Define the problem 员工排班是一个整数规划问题
model = cp_model.CpModel()
EMPLOYEE = ["王小明", "李婷婷", "张伟华", "刘晓红", "陈建国", "杨丽丽", "黄强强", "赵静静",
            "周文华", "吴小刚", "孙雅雅", "胡明明", "朱强强", "曾丽丽", "许鹏飞", "马晓霞",
            "郑伟伟", "谢娟娟", "彭军军", "方美丽"]
MIN, MAX, COST, START, END = (
    [6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2],  # 最小工作小时数
    [8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 3, 4, 4, 6, 6, 3, 5, 4, 4, 5],  # 最大工作小时数
    [30, 50, 30, 30, 40, 50, 45, 30, 35, 40, 60, 40, 60, 55, 45, 40, 50, 50, 40, 50],  # 每小时薪资
    [6, 0, 0, 0, 0, 0, 6, 0, 0, 0, 0, 0, 8, 0, 0, 0, 12, 0, 0, 0],  # 可工作时段开始时间
    [20, 24, 24, 24, 24, 24, 18, 24, 24, 24, 6, 24, 16, 24, 24, 24, 24, 24, 24, 24])  # 可工作时段结束时间

REQUIRED = [1, 1, 2, 3, 6, 6, 7, 8, 9, 8, 8, 8, 7, 6, 6, 5, 5, 4, 4, 3, 2, 2, 2, 2]  # 每个时段需要的最少员工数

# 创建变量
x = {}
for d in EMPLOYEE:
    for i in range(24):
        for j in range(1, 25):
            x[d, i, j] = model.NewBoolVar('')

# 创建目标函数
cost = sum((j - i) * x[d, i, j] * COST[EMPLOYEE.index(d)]
           for d in EMPLOYEE
           for i in range(24)
           for j in range(i + 1, 25))
model.Minimize(cost)

# ....以上为部分代码

4.求解结果

最优解：4670.0
状态：OPTIMAL
求解时间：0.2649239秒
x[d,i,j]变量的取值：
(王小明, 8, 16) = 1
(李婷婷, 3, 11) = 1
(张伟华, 4, 12) = 1
(刘晓红, 8, 16) = 1
(陈建国, 16, 24) = 1
(杨丽丽, 12, 20) = 1
(黄强强, 9, 17) = 1
(赵静静, 4, 12) = 1
(周文华, 0, 8) = 1
(吴小刚, 16, 24) = 1
(胡明明, 10, 14) = 1
(曾丽丽, 11, 15) = 1
(许鹏飞, 7, 13) = 1
(马晓霞, 2, 5) = 1
(郑伟伟, 14, 19) = 1
(谢娟娟, 5, 9) = 1
(彭军军, 6, 10) = 1
(方美丽, 4, 9) = 1