问题描述¶
在柔性资源约束项目调度问题中，一个项目由一组需要调度的任务组成。每个任务有一组兼容的资源，并且必须由其中一个资源处理。每个任务的处理时间和资源使用量（也称为权重）取决于其选择的资源。每个资源都有一个给定的最大容量：它可以同时处理多个任务，但所处理任务的权重之和不能超过该最大容量。任务之间还存在紧前约束：每个任务必须在其任意紧后任务开始之前结束。目标是找到一个使 makespan（即所有任务处理完成的时间）最小化的调度方案。
学习要点¶
- 添加 集合决策变量 来建模任务到资源的分配
- 添加 区间决策变量 来建模任务
- 定义嵌套的 符号 Lambda 函数 来建模柔性累计资源约束
建模思路¶
柔性资源约束项目调度问题的 OptAgent 模型使用表示任务的 区间决策变量，以及表示每个资源上调度任务集合的 集合决策变量。
使用 partition 算子，我们确保每个任务被分配到恰好一个资源。对于每个任务，我们借助 contains 算子过滤掉不兼容的资源。然后使用 find 算子检索为处理每个任务所选择的资源的索引。这使我们能够推导每个任务的处理时间和权重（它们取决于所选的资源），并相应地约束每个 interval 的长度。
然后我们编写紧前约束：每个任务必须在其任意紧后任务开始之前结束。
累计资源约束可以表述如下：对于每个资源以及每个时间槽 t，正在被处理的任务所消耗的资源量不得超过该资源的容量。为了对这些约束建模，我们对每个资源和每个时间槽，将所有活动任务的权重求和。通过嵌套 lambda，对资源任务集合求和；外层 lambda 枚举时间槽，内层 lambda 枚举分配给资源的任务。我们将变参 and 与另一个 符号 Lambda 函数 结合使用，以确保在任何时刻都满足资源容量约束。这种写法集中表达了各时间段的资源约束；实际求解开销取决于实例规模与求解配置。
需要最小化的 makespan 是所有任务结束的时间。
[1] Patterson, J. H.,( 1984), A comparison of exact approaches for solving the multiple constrained resource, Project Scheduling Problem, Management Science, Vol. 30, p854-86
Python 实现¶
from pathlib import Path
from optagent import OptModel, solve
def read_instance(filename):
lines = Path(filename).read_text().splitlines()
first_line = lines[0].split()
# Number of tasks
nb_tasks = int(first_line[0])
# Number of resources
nb_resources = int(first_line[1])
# Maximum capacity of each resource
capacity = [int(lines[1].split()[r]) for r in range(nb_resources)]
# Duration of task i if task i is done by resource r
task_processing_time_data = [[] for _ in range(nb_tasks)]
# Resource weight of resource r required for task i
weight = [[] for _ in range(nb_resources)]
# Number of successors
nb_successors = [0 for _ in range(nb_tasks)]
# Successors of each task i
successors = [[] for _ in range(nb_tasks)]
for i in range(nb_tasks):
line_d_w = lines[i + 2].split()
for r in range(nb_resources):
task_processing_time_data[i].append(int(line_d_w[2 * r]))
weight[r].append(int(line_d_w[2 * r + 1]))
line_succ = lines[i + 2 + nb_tasks].split()
nb_successors[i] = int(line_succ[0])
successors[i] = [int(elm) for elm in line_succ[1::]]
# Trivial upper bound for the end times of the tasks
horizon = sum(max(task_processing_time_data[i][r] for r in range(nb_resources)) for i in range(nb_tasks))
return (
nb_tasks,
nb_resources,
capacity,
task_processing_time_data,
weight,
nb_successors,
successors,
horizon,
)
def main(instance_file, output_file=None, time_limit=20):
(
nb_tasks,
nb_resources,
capacity,
task_processing_time_data,
weight,
nb_successors,
successors,
horizon,
) = read_instance(instance_file)
model = OptModel()
# Set of tasks assigned to each resource.
resources_tasks = [model.set(nb_tasks) for resource in range(nb_resources)]
resources = model.array(resources_tasks)
# Exclude resources that cannot process a task.
for task in range(nb_tasks):
for resource in range(nb_resources):
if task_processing_time_data[task][resource] == 0 and weight[resource][task] == 0:
model.constraint(model.not_(resources_tasks[resource].contains(task)))
task_resource = [model.find(resources, task) for task in range(nb_tasks)]
model.constraint(model.partition(resources))
tasks = [model.interval(0, horizon) for _ in range(nb_tasks)]
tasks_array = model.array(tasks)
task_processing_time = model.array(task_processing_time_data)
weight_array = model.array(weight)
# A task duration is selected from the row for its assigned resource.
for task in range(nb_tasks):
model.constraint(tasks[task].length() == task_processing_time.at(task, task_resource[task]))
# Respect task precedence relations.
for task in range(nb_tasks):
for successor_index in range(nb_successors[task]):
model.constraint(tasks[task] < tasks[successors[task][successor_index]])
makespan = model.max([task.end() for task in tasks])
# Enforce each resource capacity at every time slot before the makespan.
for resource in range(nb_resources):
capacity_respected = model.lambda_function(
lambda time: model.sum(
resources_tasks[resource],
model.lambda_function(
lambda task: model.at(weight_array, resource, task)
* model.at(tasks_array, task).contains(time)
),
)
<= capacity[resource]
)
model.constraint(model.and_(model.range(0, makespan), capacity_respected))
model.minimize(makespan)
solution = solve(model, time_limit_s=float(time_limit))
if not solution.feasible:
print(f"No feasible schedule found; Status = {solution.feasible}")
return solution
expressions = {"makespan": makespan}
for task in range(nb_tasks):
expressions[f"task_{task}_resource"] = task_resource[task]
expressions[f"task_{task}_start"] = tasks[task].start()
expressions[f"task_{task}_end"] = tasks[task].end()
values = {name: expression.value for name, expression in expressions.items()}
schedule_rows = [
(
task,
values[f"task_{task}_resource"],
values[f"task_{task}_start"],
values[f"task_{task}_end"],
)
for task in range(nb_tasks)
]
print(f"Makespan = {values['makespan']}; Status = {solution.feasible}")
print("Task\tResource\tStart\tEnd")
for row in schedule_rows:
print("\t".join(map(str, row)))
if output_file is not None:
Path(output_file).write_text(
f"{values['makespan']}\n" + "\n".join(" ".join(map(str, row)) for row in schedule_rows) + "\n",
encoding="utf-8",
)
return solution
本地运行¶
INSTANCE_DIR = Path.cwd() / "instances"
solution = main(INSTANCE_DIR / "pat1.fc", time_limit=10)