如何在GLPK.js中设置‘工作时长为0或≥3小时’的约束？
2026-6-14
员工排班优化的线性规划约束问题
问题背景
我用Node.js开发一款考虑多约束（周工作时长、人员可用性等）的周排班优化应用，采用glpk.js实现线性规划。目前已能生成排班，但在添加新约束时遇到问题：需实现员工若当班则工作时长至少3小时，否则为0小时。现有代码已添加「当班至少2小时」的约束，尝试使用glpk.GLP_DP未成功，求可行的约束设置方案。
相关类型定义
export interface LPEmployeeInput { id: number; name: string; availability: number[]; hoursPerWeek: number; formations: string[]; } export interface LPDailyNeed { hour: number; kitchen: number; service: number; manager: number; }
日需求示例
[ { hour: 11, kitchen: 1, service: 1, manager: 1 }, { hour: 12, kitchen: 1, service: 2, manager: 1 }, { hour: 13, kitchen: 1, service: 2, manager: 1 }, { hour: 14, kitchen: 1, service: 2, manager: 1 }, { hour: 18, kitchen: 2, service: 1, manager: 1 }, { hour: 19, kitchen: 2, service: 2, manager: 1 }, { hour: 20, kitchen: 2, service: 2, manager: 1 }, { hour: 21, kitchen: 2, service: 1, manager: 1 } ]
现有LP求解代码片段
const lp: LP = { name: 'Employee Scheduling', objective: { direction: glpk.GLP_MAX, name: 'total_hours', vars: [] }, subjectTo: [] }; // 添加每日时长约束 for (let i = 0; i < numEmployees; i++) { for (let j = 0; j < numDays; j++) { const noonVars: any[] = []; const eveningVars: any[] = []; for (let k = 0; k < dailyNeeds[j].length; k++) { if(dailyNeeds[j][k].hour < shiftBreakpoint && employees[i].availability[j * 2] == 1){ // 午班变量 noonVars.push({ name: `x_${i}_${j}_${k}`, coef: 1 }); } else if(dailyNeeds[j][k].hour >= shiftBreakpoint && employees[i].availability[j * 2 + 1] == 1){ // 晚班变量 eveningVars.push({ name: `x_${i}_${j}_${k}`, coef: 1 }); } } if(employees[i].availability[j * 2] == 1){ lp.subjectTo.push({ name: `daily_hours_${i}_${j}_noon`, vars: noonVars, bnds: { type: glpk.GLP_LO, ub: Infinity, lb: 2 } }); } if(employees[i].availability[j * 2 + 1] == 1){ lp.subjectTo.push({ name: `daily_hours_${i}_${j}_evening`, vars: eveningVars, bnds: { type: glpk.GLP_LO, ub: Infinity, lb: 2 } }); } } } // 其他约束... // 求解问题 const result = glpk.solve(lp, glpk.GLP_MSG_ALL);
解决方案
单纯的线性规划无法直接表达「要么0小时要么至少3小时」的离散逻辑，必须引入二进制决策变量将问题转化为整数规划。具体实现步骤如下：
1. 添加二进制变量
为每个员工的每个时段（午班/晚班）创建二进制变量，标记是否当班：
y_i_j_noon = 1：员工i在第j天午班当班；0：不当班y_i_j_evening = 1：员工i在第j天晚班当班；0：不当班
在LP模型中添加这些变量：
// 为员工的午班/晚班添加二进制变量 for (let i = 0; i < numEmployees; i++) { for (let j = 0; j < numDays; j++) { // 午班二进制变量 if (employees[i].availability[j * 2] == 1) { lp.objective.vars.push({ name: `y_${i}_${j}_noon`, coef: 0 // 目标函数不涉及该变量，系数设为0 }); } // 晚班二进制变量 if (employees[i].availability[j * 2 + 1] == 1) { lp.objective.vars.push({ name: `y_${i}_${j}_evening`, coef: 0 }); } } }
2. 替换原约束，添加逻辑约束
将原「至少2小时」约束替换为两组约束，实现「0或≥3小时」的逻辑：
- 约束1：若当班（y=1），工作时长≥3小时
- 约束2：若不当班（y=0），工作时长=0小时
代码实现：
for (let i = 0; i < numEmployees; i++) { for (let j = 0; j < numDays; j++) { const noonVars: any[] = []; const eveningVars: any[] = []; for (let k = 0; k < dailyNeeds[j].length; k++) { if(dailyNeeds[j][k].hour < shiftBreakpoint && employees[i].availability[j * 2] == 1){ noonVars.push({ name: `x_${i}_${j}_${k}`, coef: 1 }); } else if(dailyNeeds[j][k].hour >= shiftBreakpoint && employees[i].availability[j * 2 + 1] == 1){ eveningVars.push({ name: `x_${i}_${j}_${k}`, coef: 1 }); } } // 处理午班约束 if(employees[i].availability[j * 2] == 1){ const maxNoonHours = noonVars.length; // 午班最大可工作时长 // 约束1：工作时长 ≥ 3*y_i_j_noon lp.subjectTo.push({ name: `noon_min_hours_${i}_${j}`, vars: [ ...noonVars, { name: `y_${i}_${j}_noon`, coef: -3 } ], bnds: { type: glpk.GLP_LO, lb: 0, ub: Infinity } }); // 约束2：工作时长 ≤ maxNoonHours * y_i_j_noon lp.subjectTo.push({ name: `noon_max_hours_${i}_${j}`, vars: [ ...noonVars, { name: `y_${i}_${j}_noon`, coef: -maxNoonHours } ], bnds: { type: glpk.GLP_UP, lb: -Infinity, ub: 0 } }); } // 处理晚班约束 if(employees[i].availability[j * 2 + 1] == 1){ const maxEveningHours = eveningVars.length; // 约束1：工作时长 ≥ 3*y_i_j_evening lp.subjectTo.push({ name: `evening_min_hours_${i}_${j}`, vars: [ ...eveningVars, { name: `y_${i}_${j}_evening`, coef: -3 } ], bnds: { type: glpk.GLP_LO, lb: 0, ub: Infinity } }); // 约束2：工作时长 ≤ maxEveningHours * y_i_j_evening lp.subjectTo.push({ name: `evening_max_hours_${i}_${j}`, vars: [ ...eveningVars, { name: `y_${i}_${j}_evening`, coef: -maxEveningHours } ], bnds: { type: glpk.GLP_UP, lb: -Infinity, ub: 0 } }); } } }
3. 声明二进制变量类型
glpk.js需要明确变量为二进制类型，需在求解前通过API设置：
// 收集所有二进制变量名称 const binaryVars = []; for (let i = 0; i < numEmployees; i++) { for (let j = 0; j < numDays; j++) { if (employees[i].availability[j * 2] == 1) { binaryVars.push(`y_${i}_${j}_noon`); } if (employees[i].availability[j * 2 + 1] == 1) { binaryVars.push(`y_${i}_${j}_evening`); } } } // 读取LP模型并设置变量类型 const prob = glpk.readLP(lp); binaryVars.forEach(varName => { const idx = glpk.get_col_index(prob, varName); glpk.set_col_kind(prob, idx, glpk.GLP_BV); // GLP_BV表示二进制变量 }); // 求解整数规划问题 const result = glpk.solveLP(prob, glpk.GLP_MSG_ALL);
关键说明
- 原线性约束无法表达离散逻辑，必须引入二进制变量转化为整数规划
maxNoonHours/maxEveningHours是对应时段的总小时数，用来确保不当班时工作时长强制为0- glpk.js原生支持整数/二进制规划，只需正确声明变量类型并添加对应约束即可
内容的提问来源于stack exchange，提问作者Mirecos
相关产品推荐
相关产品推荐
