or-toolsconstraint-programmingcp-sat

How can we achieve prioritization of tasks with OR-Tools?


I have two tasks to plan for the next two days in the shopfloor.

There is only one operator in the shopfloor and this operator can do only one task a day in these two days.

The tasks are of different priorities. One is more urgent and the other is less urgent.

How can we always make sure, whenever possible, the more urgent tasks is planned earlier?

Are we able to achieve it but keeping make span minimized?

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}')

Solution

  • create a bool_var

      priority_violated = model.new_bool_var('priority_violated')
    

    link it to the two tasks:

      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)
    

    penalize the violation

      model.minimize(make_span + violation_weight * priority_violated)