英文:
Scheduling : How to enforce consecutiveness of shifts for an employee
问题
我有一个排班问题，其中员工一天最多可以工作4小时，总共允许的工作时间是8小时。这4小时要求连续工作。
例如，决策变量（二进制）是员工是否会在特定小时工作。因此，一个示例解决方案可能如下所示：
小时：0 1 2 3 4 5 7 [一天8小时]dv ：0 1 1 1 1 0 0 [员工从第2小时工作到第5小时]
一个开源求解器中的解决方案/方法真的会对我有所帮助。
英文:
I have a scheduling problem where an employee can work maximum of say, 4 hours out of total allowable 8 hours in a day. For these 4 hours, I want them to be consecutive.
For example, decision variables (binary) are whether an employee will work in a particular hour or not. So a sample solution could look like below:
hrs : 0 1 2 3 4 5 7 [8 hours in a day]dv : 0 1 1 1 1 0 0 [employee works from 2nd hour through 5th hour]
A solution / approach in an open-source solver would really help me.
答案1
得分: 1
允许最多一次变动以限制启动次数。启动发生在我们从 dv[t-1]=0 转变为 dv[t]=1 时。
start[t] >= dv[t] - dv[t-1] 对于所有 tsum(t,start[t]) <= 1start[t] ∈ {0,1} (或者 ∈ [0,1])
这将给您一个启动，因此一个变动。这是一种非常常见的表述，在调度中经常使用。值得知道。
英文:
To allow a maximum of one shift restrict the number of starts. A start happens when we go from dv[t-1]=0 to dv[t]=1.
start[t] >= dv[t] - dv[t-1] for all tsum(t,start[t]) <= 1start[t] ∈ {0,1} (or even ∈ [0,1])
This will give you just one start, so one shift. This is a fairly standard formulation that is used very often in scheduling. Worthwhile to know.
答案2
得分: 0
这可以被表达为一个混合整数线性规划问题。我的方法如下：
-
创建员工 (e) 按一天中的小时 (t) 的二进制变量，set。
-
计算班次变动，并将其存储在一个变量中，例如 wet，如下所示：
wet = set - se(t-1)，对于 t > 0, e -
we0 = se0，对所有 e
-
创建一个二进制变量，用于捕获班次的开始时间，称之为 vet，设置以下约束条件：
vet = max(0, wet)，对所有 e, t -
我们希望班次只能开始一次，因此强制执行以下约束条件：
对所有 e，求和(vet) ≤ 1
以下是在Google-OR-tool的线性求解器中实现上述内容的代码。请注意，我们将不得不线性化max函数。
from ortools.linear_solver import pywraplps = pywraplp.Solver("", pywraplp.Solver.SCIP_MIXED_INTEGER_PROGRAMMING)班次长度 = 8# 决策变量：班次是否被工作# 根据上述解释，s_t 我只取了一个员工来简化shift_bool =展开收缩# 约束条件：员工最多能工作 4 小时s.Add(sum(shift_bool) == 4)# 决策变量：捕获从一小时到另一小时的班次变动# 根据上述解释，w_tshift_diff =展开收缩for i in range(班次长度 - 1):s.Add(shift_diff[i+1] == shift_bool[i+1] - shift_bool[i])# 对于第一个小时：s.Add(shift_diff[0] == shift_bool[0])# 决策变量：捕获班次开始# 根据上述解释，v_tshift_max =展开收缩s.Add(sum(shift_max) == 1)# 我们需要线性化 `max` 操作，所以设 u = max(a0, a1, a2)# u >= a_i, 对所有 i# u <= a_i + (1 - b_i) * M, 对所有 i# 求和(b_i) = 1# b_i 是二进制变量# M 是 u 的上限# 我在下面实现了上述逻辑：# 实质上，对于每个小时，我们需要在 0 和 shift_diff 之间取最大值for i in range(班次长度):bool_var =展开收缩s.Add(shift_max[i] >= shift_diff[i])s.Add(shift_max[i] >= 0)s.Add(shift_max[i] <= shift_diff[i] + (1 - bool_var[0]) * 5)s.Add(shift_max[i] <= 0 + (1 - bool_var[0]) * 5)s.Add(sum(bool_var) == 1)# 假目标obj = sum(shift_bool)s.Minimize(obj)s.Solve()# shift_assigned 的值：[shift_bool[i].SolutionValue() for i in range(班次长度)]# [0.0, 0.0, 0.0, 0.0, 1.0, 1.0, 1.0, 1.0]
只是随意玩一下，如果你添加一个额外的约束：s.Add(shift_bool[0] + shift_bool[1] == 0)，那么解决方案将如下所示：[0, 0, 0, 1, 1, 1, 1, 0]
英文:
This can be formulated as a mixed integer linear program. My approach is as follows:
-
Create binary variables by employee (e) by hour of the day (t), s<sub>et</sub>
-
Calculate shift changes, and store them in a variable, say, w<sub>et</sub>, so:
w<sub>et</sub> = s<sub>et</sub> - s<sub>et-1</sub>, for t > 0, e -
w<sub>e0</sub> = s<sub>e0</sub>, for all e
-
Create binary variable, that will capture when the shift will start, say, v<sub>et</sub>, put the following constraint:
v<sub>et</sub> = max(0, w<sub>et</sub>), for all e, t -
we want shift to only start once, so enforce the following constraint:
sum_over_t(v<sub>et</sub>) <= 1, for all e
Below is the implementation of the above in Google-OR-tool's linear solver. Please note that we will have to linearise the max function.
from ortools.linear_solver import pywraplps = pywraplp.Solver("", pywraplp.Solver.SCIP_MIXED_INTEGER_PROGRAMMING)shift_length = 8# decision variable : whether the shift was worked or not# s_t following above explanation. I have taken 1 employee for simplicityshift_bool =展开收缩# constraint : employee can work for max 4 hourss.Add(sum(shift_bool) == 4)# decision variable : capture shift changes from one hour to another.# w_t following above explanation.shift_diff =展开收缩for i in range(shift_length - 1):s.Add(shift_diff[i+1] == shift_bool[i+1] - shift_bool[i])# for first hour:s.Add(shift_diff[0] == shift_bool[0])# decision variable : to capture shift start# v_t following above explanationshift_max =展开收缩s.Add(sum(shift_max) == 1)# we need to linearise the `max` operation, so say, u = max(a0, a1, a2)# u >= a_i, for all i# u <= a_i + (1 - b_i) * M, for all I# sum_over_i(b_i) = 1# b_i is binary variable# M is the upper bound on u# I have implemented the above logic below:# essentially, for each hour we need to take max between# 0 and shift_difffor i in range(shift_length):bool_var =展开收缩s.Add(shift_max[i] >= shift_diff[i])s.Add(shift_max[i] >= 0)s.Add(shift_max[i] <= shift_diff[i] + (1 - bool_var[0]) * 5)s.Add(shift_max[i] <= 0 + (1 - bool_var[0]) * 5)s.Add(sum(bool_var) == 1)# dummy objectiveobj = sum(shift_bool)s.Minimize(obj)s.Solve()# shift_assigned values:[shift_bool[i].SolutionValue() for i in range(shift_length)]# [0.0, 0.0, 0.0, 0.0, 1.0, 1.0, 1.0, 1.0]
just to play around, if you add an additional constraint : s.Add(shift_bool[0] + shift_bool[1] == 0), then the solution looks as follows: [0, 0, 0, 1, 1, 1, 1, 0]
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论