EVA_duty_arrange_tool/README.md

# EVA 值班排班工具

## 环境配置

本项目使用 `uv` 进行包管理。

安装项目中所需要的所有包的最新版本。其中 `pyside6` 是一个前端库，`pyinstaller` 用于打包项目，`ortools` 是一个高效的组合优化求解器，`pandas` 用于处理表格数据：
```bash
uv sync
```

## 项目结构
```
EVA_duty_arrange_tool/
    ├─ main.py                // 主函数，定义了前端界面和组件的回调函数
    ├─ solve.py               // 定义了值班排班问题的求解函数
    ├─ utils.py               // 定义了读取、写入 excel 的函数
    ├─ pics                   // 储存了说明文档中用到的图片
    │  ├─ *.jpg/*.png
    ├─ *.md                   // 说明文档
    ├─ *.xlsx                 // 测试用例
```

## 项目运行 & 打包
项目运行方式：
```bash
uv run main.py
```

本项目使用 `pyinstaller` 工具进行打包。如果要打包，请确保能够正常运行项目。打包命令如下：
```bash

uv run pyinstaller --onefile --windowed --name=EVA_duty_arrange_tool --hidden-import=ortools --collect-all ortools --additional-hooks-dir=. main.py
```

> **注意**：由于 `ortools` 库包含大量 DLL 依赖,需要使用 `--collect-all ortools` 参数来收集所有必要的动态链接库。`--additional-hooks-dir=.` 参数指定使用项目根目录下的 `hook-ortools.py` 文件来确保正确打包。

## 数学原理
本项目将值班排班问题建模为了一个[组合优化](https://zh.wikipedia.org/wiki/%E7%BB%84%E5%90%88%E4%BC%98%E5%8C%96)问题，使用 Google 的 OR-Tools 求解器中的 SCIP 求解器进行求解。

### 问题描述

在本问题中，优化目标是一个涉及多个方面的量化指标：
- **目标1**：每一班同学数量的平均程度
- **目标2**：每一班技术部老人数量接近期望值
- **目标3**：每一班技术部小朋友数量接近期望值
- **目标4**：每一班人资部小朋友数量接近期望值
- **目标5**：每一班各部门人数的平均程度

在本问题中，主要约束是：
1. 让每位同学每周的班次数符合意愿（特别地，选择3次的同学可以安排2-3次；若某同学的可用班次数少于其期望值班次数，则自动降至可用数量）
2. 让每位同学只在自己有空的时间段值班
3. 每班次的总人数在指定范围内（无人选择的班次豁免下限约束，视为无人值班）
4. 每班次技术部老人数量在指定范围内
5. 每班次老人总数在指定范围内
6. 每班次小朋友总数在指定范围内

### 数学建模

设一共有 $n$ 位同学，$m$ 个值班的班次，协会共有 $t=5$ 个部门（电脑部、电器部、人资部、财外部、文宣部），定义以下符号：

**决策变量：**
- $x_{ij} \in \{0,1\}, \quad i=1,2,\dots,n,\quad j=1,2,\dots,m$ 表示第 $i$ 位同学是否值第 $j$ 班

**已知参数：**
- $N_i \in \mathbb{N}, \quad i=1,2,\dots,n$ 表示第 $i$ 个同学每周愿意值班次数
- $v_{ij} \in \{0,1\}, \quad i=1,2,\dots,n,\quad j=1,2,\dots,m$ 表示第 $i$ 位同学是否有空值第 $j$ 班
- $\text{old}_i \in \{0,1\}, \quad i=1,2,\dots,n$ 表示第 $i$ 位同学是否是老人（非小朋友）
- $d_{ik}\in\{0,1\}, \quad i=1,2,\dots,n,\quad k=1,2,\dots,t$ 表示第 $i$ 位同学是否属于第 $k$ 个部门
- $\text{tech}_i = d_{i1} + d_{i2} \in \{0,1\}$ 表示第 $i$ 位同学是否属于技术部（电脑部或电器部）
- $\text{hr}_i = d_{i3} \in \{0,1\}$ 表示第 $i$ 位同学是否属于人资部

**派生量：**
- $M_j = \sum_{i=1}^{n} x_{ij}, \quad j=1,2,\dots,m$ 表示第 $j$ 班次实际安排的值班人数
- $\bar{M} = \frac{\sum_{i=1}^{n}N_i}{m}$ 表示平均每班的人数

### 优化目标

为了处理多目标优化问题，我们采用**线性加权法**将多个目标组合成单一目标函数。引入归一化系数 $m_1=2.5, m_2=3, m_3=4, m_4=1, m_5=8$ 和权重 $w_1, w_2, w_3, w_4, w_5$，总目标函数为：

$$\min \quad Z = w_1 \cdot \frac{X_1}{m_1 \cdot M} + w_2 \cdot \frac{X_2}{m_2 \cdot M} + w_3 \cdot \frac{X_3}{m_3 \cdot M} + w_4 \cdot \frac{X_4}{m_4 \cdot M} + w_5 \cdot \frac{X_5}{m_5 \cdot M}$$

各目标定义如下：

**目标1：均衡班次人数**

$$X_1 = \sum_{j=1}^{m} a_j^{(1)}$$

其中辅助变量 $a_j^{(1)} \in [0,+\infty)$ 满足：
$$a_j^{(1)} \ge M_j - \bar{M}, \quad a_j^{(1)} \ge \bar{M} - M_j, \quad \forall j$$

> 注：在组合优化问题中只能定义线性约束，不能直接使用绝对值。因此引入辅助变量 $a_j^{(1)}$ 并添加两个不等式约束，使得在优化过程中 $a_j^{(1)}$ 自动收敛到 $|M_j - \bar{M}|$。

**目标2：每班技术部老人数量接近期望值**

期望每班有 $m_2 = 3$ 位技术部老人，定义缺口：

$$X_2 = \sum_{j=1}^{m} a_j^{(2)}$$

其中辅助变量 $a_j^{(2)} \in [0,+\infty)$ 满足：
$$a_j^{(2)} \ge \sum_{i=1}^{n} x_{ij} \cdot \text{old}_i \cdot \text{tech}_i - m_2$$
$$a_j^{(2)} \ge m_2 - \sum_{i=1}^{n} x_{ij} \cdot \text{old}_i \cdot \text{tech}_i, \quad \forall j$$

**目标3：每班技术部小朋友数量接近期望值**

期望每班有 $m_3 = 4$ 位技术部小朋友，定义缺口：

$$X_3 = \sum_{j=1}^{m} a_j^{(3)}$$

其中辅助变量 $a_j^{(3)} \in [0,+\infty)$ 满足：
$$a_j^{(3)} \ge \sum_{i=1}^{n} x_{ij} \cdot (1-\text{old}_i) \cdot \text{tech}_i - m_3$$
$$a_j^{(3)} \ge m_3 - \sum_{i=1}^{n} x_{ij} \cdot (1-\text{old}_i) \cdot \text{tech}_i, \quad \forall j$$

**目标4：每班人资部小朋友数量接近期望值**

期望每班有 $m_4 = 1$ 位人资部小朋友，定义缺口：

$$X_4 = \sum_{j=1}^{m} a_j^{(4)}$$

其中辅助变量 $a_j^{(4)} \in [0,+\infty)$ 满足：
$$a_j^{(4)} \ge \sum_{i=1}^{n} x_{ij} \cdot (1-\text{old}_i) \cdot \text{hr}_i - m_4$$
$$a_j^{(4)} \ge m_4 - \sum_{i=1}^{n} x_{ij} \cdot (1-\text{old}_i) \cdot \text{hr}_i, \quad \forall j$$

**目标5：均衡各部门人数分布**

对每个班次 $j$ 和每个部门 $k$，定义该班次该部门的人数偏差：

$$X_5 = \sum_{j=1}^{m} \sum_{k=1}^{t} a_{jk}^{(5)}$$

其中 $\bar{M}_j = \frac{M_j}{t}$ 表示第 $j$ 班次各部门的平均人数，$C_{jk} = \sum_{i=1}^{n} x_{ij} \cdot d_{ik}$ 表示第 $j$ 班次第 $k$ 部门的实际人数，辅助变量 $a_{jk}^{(5)} \in [0,+\infty)$ 满足：

$$a_{jk}^{(5)} \ge C_{jk} - \bar{M}_j, \quad a_{jk}^{(5)} \ge \bar{M}_j - C_{jk}, \quad \forall j,k$$

### 约束条件

**基本约束：**

1. **意愿班次约束**：每位同学的值班次数必须符合其意愿
   $$\sum_{j=1}^{m}x_{ij} = N_i, \quad \forall i \text{ where } N_i \neq 3$$
   $$2 \le \sum_{j=1}^{m}x_{ij} \le 3, \quad \forall i \text{ where } N_i = 3$$

2. **时间可行性约束**：只在有空的时间段排班
   $$x_{ij} \le v_{ij}, \quad \forall i,j$$

**班次人数约束：**

3. **总人数约束**：每班次人数在 $[n_{\min}, n_{\max}]$ 范围内
   $$n_{\min} \le \sum_{i=1}^{n} x_{ij} \le n_{\max}, \quad \forall j$$

4. **技术部老人约束**：每班次技术部老人数在范围内
   $$n_{\text{tech\_old\_min}} \le \sum_{i=1}^{n} x_{ij} \cdot \text{old}_i \cdot \text{tech}_i \le n_{\text{tech\_old\_max}}, \quad \forall j$$

5. **老人总数约束**：每班次老人总数在范围内
   $$n_{\text{old\_min}} \le \sum_{i=1}^{n} x_{ij} \cdot \text{old}_i \le n_{\text{old\_max}}, \quad \forall j$$

6. **小朋友总数约束**：每班次小朋友总数在范围内
   $$n_{\text{new\_min}} \le \sum_{i=1}^{n} x_{ij} \cdot (1-\text{old}_i) \le n_{\text{new\_max}}, \quad \forall j$$

### 求解器

以上完成了整个排班问题的建模。本项目使用 Google OR-Tools 中的 **SCIP 求解器**（Solving Constraint Integer Programs）进行求解。SCIP 是一个强大的混合整数规划（MIP）求解器，特别适合处理这类组合优化问题。

OR-Tools 支持 `C++`、`Python`、`C#`、`Java` 等多种语言，并提供跨平台支持。在本项目中，我们使用其 Python 接口 `ortools.linear_solver.pywraplp` 进行建模和求解。当找到最优解时，求解器会输出详细的目标值和各个优化指标的统计信息。

## 维护指南
- 如果你想更改 Excel 的读取、写入相关的功能，应该修改 `utils.py` 中的相关函数。
- 如果你想更改软件的前端界面，应该修改 `main.py` 中 `MyWidget` 这个类相关的代码。
- 如果你想更换排班问题的建模方式、更换求解器、增减限制条件，应该修改 `solve.py` 中的相关代码。
- 如果你想更改异常数据（缺班、可用班次不足）的检测和处理逻辑，应该修改 `main.py` 中 `magic` 方法内对应的检查块，以及 `solve.py` 中 `solve_program` 的 `exempt_shifts` 参数相关逻辑。