每小时轮班调度线性规划

Question

线性规划问题

数据：

1. 员工数据：包括员工姓名。
2. 技能数据：指定哪些员工可以执行每项任务。 （0 和 1）
3. 可用性数据：表示每个员工可以工作的时间（24 小时内）。 （0 和 1）
4. 需求数据：详细说明每小时每项任务所需的员工数量。

限制：

1. 每位员工每天最多可以工作8小时。
2. 员工必须从上班时间开始连续工作（例如，如果员工下午 1 点开始工作，则必须工作到晚上 9 点）。
3. 每位员工每天只能轮班一次。
4. 员工排班必须满足或超过每小时任务要求。
5. 一名员工每小时只能完成一项任务。
6. 员工可以根据时间安排工作。
7. 员工可以根据提供的技能数据执行特定任务。

目标：

• 最大限度地减少员工总工作时间。

我写了一段代码，但不明白我哪里出错了。该解决方案变得不可行，特别是与连续性约束有关。也就是说，如果我删除连续性约束，它就可以正常工作。

示例数据的链接：

https://drive.google.com/drive/folders/1QIr-zFhXzNtXQO6H0KkclpPPGZJ7735L?usp=sharing

import pulp

# Define the problem
prob = pulp.LpProblem("Minimize_Employee_Hours", pulp.LpMinimize)

# Define variables
shift_work = pulp.LpVariable.dicts("ShiftWork", [(emp, task, hour) for emp in employees for task in tasks for hour in range(24)], 
                                   lowBound=0, cat='Binary')

# Define auxiliary binary variable for start of the shift
start_work = pulp.LpVariable.dicts("ShiftStart", [(emp, start_hour) for emp in employees for start_hour in range(24)], 
                                    cat='Binary')

# Objective function: Minimize the total number of employee hours
prob += pulp.lpSum([shift_work[(emp, task, hour)] for emp in employees for task in tasks for hour in range(24)])

# Task requirement constraints for each hour
for task in tasks:
    for hour in range(24):
        prob += pulp.lpSum([shift_work[(emp, task, hour)] for emp in employees]) >= requirements[task][hour]
        
# Ensure employees do not work more than 8 hours in total across all tasks
for emp in employees:
    prob += pulp.lpSum([shift_work[(emp, task, hour)] for task in tasks for hour in range(24)]) <= 8
    
# Ensure employees only work on tasks they are skilled for
for emp in employees:
    for task in tasks:
        for hour in range(24):
            prob += shift_work[(emp, task, hour)] <= skills[emp][task]

# Ensure an employee can only work on one task at a time
for emp in employees:
    for hour in range(24):
        # Sum of shift_work for all tasks at a given hour should be <= 1
        prob += pulp.lpSum([shift_work[(emp, task, hour)] for task in tasks]) <= 1
    
# Ensure employees only work when available
for emp in employees:
    for task in tasks:
        for hour in range(24):
            prob += shift_work[(emp, task, hour)] <= availability[emp][hour]
            
            
# max one shift entire day per employee
for emp in employees:
    prob += pulp.lpSum([start_work[(emp, start_hour)] for start_hour in range(24)]) <= 1

# Continuous hours constraint 
for emp in employees:
    for start_hour in range(17):  # If the shift starts before 17 (i.e., from 0 to 16)
        prob += pulp.lpSum([shift_work[(emp, task, hour)] 
                            for task in tasks 
                            for hour in range(start_hour, start_hour + 8)]) <= 8 * start_work[(emp, start_hour)]
    
    for start_hour in range(17, 24):  # If the shift starts at or after 17 (i.e., from 17 to 23)
        prob += pulp.lpSum([shift_work[(emp, task, hour)] 
                            for task in tasks 
                            for hour in range(start_hour, 24)]) <= (24 - start_hour) * start_work[(emp, start_hour)]

        
# Solve the problem
solver = pulp.getSolver('GLPK_CMD')
prob.solve(solver)

Answer 1

尝试将如下所示的内容替换为连续性的约束。

我要假设，因为尚不完全清楚员工在轮班期间可以转向不同的任务，因为在这种情况下，您确实需要一个“工作”变量和一个“开始”变量，所以我想这就是你的意图。

最初设置连续性约束的方式的问题是，员工必须在前面的“所有”起点中从 1 开始才能工作。 您将其写为“与”约束。 这转变为“或”约束，基本上是说，为了在 x 小时内工作，您必须在

{x-7, x-6, ..., x}

小时内开始工作。代码

# Must have started shift constraint
# in order to work in hour x, employee must have a start within the last x-7 shifts, or at hour x
for emp in employees:
    for hour in range(24):
        start_hours = set(range(max(0, hour-7), hour + 1))  # the start "window" for this hour
        prob += pulp.lpSum(shift_work[emp, task, hour] for task in tasks) <= pulp.lpSum(
            start_work[emp, start_hour] for start_hour in start_hours)

未测试，因为您的数据未包含在问题中（链接到 Google 中响应者必须处理的内容不算在内。；）