0

我几乎没有关于显示每项任务以及任务持续时间的任务的数据，例如：

表格1：

任务 长度 时间
任务1 45 分钟 6:30
任务 2 45 分钟 7:00

在这里，我知道每项任务，任务多长时间，以及任务要在什么时间完成。现在我有 10 个工作人员，其中 7 个是合同制，他们的每小时工资单与普通员工不同。我需要将每项任务相应地分配给所有工作人员。不能有重叠。一项任务仅分配给单个船员。这样的任务有200个。是否有特定的 python 包甚至算法可以帮助我解决这个问题？我遇到了这个。但我不确定这是否可以相应地帮助我。有没有其他算法可以帮助我解决这个问题？

4

1 回答 1

0

您可以按如下方式在 CP Optimizer 中制定问题。它甚至将问题推广到开始日期不固定但必须在时间窗口内确定的任务的情况。

from docplex.cp.model import *

# Time hh:mm to minute
def mn(time):
    h,m = time.split(':')
    return 60*int(h)+int(m)

T = [
  # Length, Earliest start, Latest start
  (45, mn("6:30"),  mn("6:30")),
  (45, mn("7:00"),  mn("7:10")),
  #...
]

# Cost of crew (per minute)
C = [ 10, 12, 11, 12, 13 ]

N = range(len(T)) # Number of nbTasks
M = range(len(C)) # Number of resources (crews)

# CP Optimizer formulation

model = CpoModel()

# Decision variables:
# task[i]    : interval variable representing task i
# alloc[i][j]: optional interval variable representing task i allocated to crew j
task  = [ interval_var(size=T[i][0], start=[T[i][1],T[i][2]], name="T{}".format(i)) for i in N]
alloc = [ [interval_var(optional=True, name="T{}R{}".format(i,j)) for j in M] for i in N]

# Each task must be allocated one and only one crew:
model.add([alternative(task[i], [alloc[i][j] for j in M]) for i in N])
# Tasks performed by a crew do not overlap
model.add([no_overlap([alloc[i][j] for i in N]) for j in M])
# No more than M tasks executed in parallel (this is a redundant constraint)
model.add(sum(pulse(task[i],1) for i in N) <= len(C))

# Minimize total allocation cost
cost = sum(C[j]*length_of(alloc[i][j]) for i in N for j in M)
model.add(minimize(cost))

# CP Optimizer resolution

solution = model.solve(LogPeriod=1000000, TimeLimit=30)

# Display solution

for i in N:
    for j in M:
        s = solution.get_var_solution(alloc[i][j])
        if s.is_present():
            print("Task {} scheduled on {}-{} with crew {}".format(i,s.get_start(),s.get_end(),j))

将显示如下内容：

Task 0 scheduled on 390-435 with crew 0
Task 1 scheduled on 420-465 with crew 2
于 2021-06-23T14:06:32.520 回答