建模实战：员工排班优化调度问题的Ortools求解器实现

建模实战：员工排班优化调度问题的Ortools求解器实现

引用

CSDN

1.

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

1. 问题描述

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

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

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

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

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

5. 绘制结果

6. 配套视频链接

运筹优化实战-最优化员工排班-bilibili