我们如何使用 OR-Tools 实现任务的优先级排序？

Question

接下来两天我要在车间计划两项任务。

车间里只有一名操作员，这两天该操作员每天只能做一项任务。

任务有不同的优先级。一个比较紧急，另一个不太紧急。

我们如何才能始终确保在可能的情况下更早地计划更紧急的任务？

我们能够在保持最小化跨度的情况下实现这一目标吗？

from ortools.sat.python import cp_model

model = cp_model.CpModel()


# 1. Data

tasks = {0, 1}

task_to_urgency_level = {10, 100}  # 100 is more urgent than 10

days = {0, 1}

day_to_operator_resource = {0: 1, 1: 1}


# 2. Decision Variables

max_date_index = max(days)

# the day index for tasks
variables_task_day_index = {
    task: model.NewIntVar(0, max_date_index, f"task_{task}") for task in tasks
}

# the allocation matrix
variables_task_to_day_matrix = {
    (task, day): model.NewBoolVar(f"task {task} --> day {day}")
    for task in tasks
    for day in days
}


# 3. Constraints

# The max number of tasks for a day must be less than the number of operators available in this day
for day in days:
    model.Add(
        sum(variables_task_to_day_matrix[task, day] for task in tasks) <= day_to_operator_resource[day]
    )

# One task can be allocated to only one day
for task in tasks:
    model.Add(
        sum(variables_task_to_day_matrix[task, day] for day in days) == 1
    )

# link the allocation matrix and task day index
for task in tasks:
    for day in days:
        model.Add(
            variables_task_day_index[task] == day
        ).OnlyEnforceIf(
            variables_task_to_day_matrix[task, day]
        )


# 4. Objective

make_span = model.NewIntVar(0, 99999, "total_days")

model.AddMaxEquality(
    make_span,
    [variables_task_day_index[task] for task in tasks]
)

model.Minimize(make_span)


# 5. Solve

solver = cp_model.CpSolver()
status = solver.Solve(model=model)


if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
    for day in days:
        for task in tasks:
            if solver.Value(variables_task_to_day_matrix[task, day]):
                print(f'Task {task} --> Day {day}')

Answer 1

创建一个 bool_var

  priority_violated = model.new_bool_var('priority_violated')

将其链接到两个任务：

  model.add(end_of_high_priority_task > end_of_low_priority_task).only_enforce_if(priority_violated)
  model.add(end_of_high_priority_task <= end_of_low_priority_task).only_enforce_if(~priority_violated)

违规处罚

  model.minimize(make_span + violation_weight * priority_violated)