建模实战：员工排班优化调度与Ortools求解器应用

创作时间:

作者:

@小白创作中心

建模实战：员工排班优化调度与Ortools求解器应用

引用

CSDN

https://blog.csdn.net/abc8023/article/details/11881345

员工排班优化调度是运筹优化中的一个典型问题。本文通过一个具体的案例，详细介绍了如何使用Ortools求解器进行员工排班优化调度。文章包括问题描述、建模过程、代码实现和求解结果等多个部分，内容完整且实用性强，适合对运筹优化和编程感兴趣的读者参考学习。

1. 问题描述

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

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

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

员工姓名最小工作小时最大工作小时每小时工资可用性
王小明 6 8 30 6-20
李婷婷 6 8 50
张伟华 6 8 30
刘晓红 6 8 30
陈建国 6 8 40
杨丽丽 6 8 50
黄强强 6 8 45 6-18
赵静静 6 8 30
周文华 6 8 35
吴小刚 2 8 40
孙雅雅 2 3 60 0-6, 18-24
胡明明 2 4 40
朱强强 2 4 60 8-16
曾丽丽 2 6 55
许鹏飞 2 6 45
马晓霞 2 3 40
郑伟伟 2 5 50 12-24
谢娟娟 2 4 50
彭军军 2 4 40
方美丽 2 5 50

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

2. 建模

参数：

决策变量：创建202424个变量

目标函数和约束：

目标函数与约束说明：
目标函数：使得每日支付员工的薪水最少
约束1：如果员工d进行工作，则需满足个人工作时长不低于最小值、不高于最大值每位员工每天至多工作一个班次，每个班次都是一段连续的时间，员工 d 只工作一个班次，即至多只有一组 (i,j) 使得 x_dij≠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