14. Scheduling

14.1. Setup

We start by downloading the unified planning library.

%pip install unified-planning[aries]

14.2. A scheduling primer

unified-planning provides support for modeling scheduling problems. It heavily relies on all the building blocks of planning problems and in particular:

• reuse state definition (Type, Fluent, initial state, (timed) goals, …)

• replace Action with Activity

• add syntactic sugar for common patterns in scheduling problems (resources, …)

from unified_planning.shortcuts import *
from unified_planning.model.scheduling import SchedulingProblem

# Create an empty problem called factory
problem = SchedulingProblem("factory")
problem

problem name = factory

fluents = [
]

initial fluents default = [
]

initial values = [
]


BASE: {
  }

Activities:

14.3. Resources as numeric fluents

A SchedulingProblem allows boolean, symbolic and numeric fluents to state representation, just like a regular planning problem.

In addition, it exposes an `add_resource <https://unified-planning.readthedocs.io/en/latest/api/model/scheduling/SchedulingProblem.html#unified_planning.model.scheduling.SchedulingProblem.add_resource>`__ method that eases the definition of reusable resources:

# Create two unary resources, one for each machine
machine1 = problem.add_resource("machine1", capacity=1)
machine2 = problem.add_resource("machine2", capacity=1)
# Create a resource with capacity 4 representing the available operators
operators = problem.add_resource("operators", capacity=4)

print(problem)

problem name = factory

fluents = [
  integer[0, 1] machine1
  integer[0, 1] machine2
  integer[0, 4] operators
]

initial fluents default = [
  integer[0, 1] machine1 := 1
  integer[0, 1] machine2 := 1
  integer[0, 4] operators := 4
]

initial values = [
]


BASE: {
  }

Activities:

14.4. Activities

An `Activity <https://unified-planning.readthedocs.io/en/latest/api/model/scheduling/Activity.html>`__ is essentially a durative action that appears exactly once in the solution.

# Create an activity a1 that has a duration of 3 time units that uses the machine 1
a1 = problem.add_activity("a1", duration=3)
a1.uses(machine1, amount=1)

print(a1)

a1 {
    duration = [3, 3]
    effects = [
      start(a1):
        machine1 -= 1:
      end(a1):
        machine1 += 1:
    ]
  }

# Specify that activity a1 requires 2 operators to be executed
a1.uses(operators, amount=2)
print(a1)

a1 {
    duration = [3, 3]
    effects = [
      start(a1):
        machine1 -= 1:
        operators -= 2:
      end(a1):
        machine1 += 1:
        operators += 2:
    ]
  }

# Create a new activity a2 that lasts 6 time units and require machine2 and 1 operator
a2 = problem.add_activity("a2", duration=6)
a2.uses(operators)  # default usage is 1
a2.uses(machine2)

# Require that activity be finished by time unit 14
a2.add_deadline(14)
a2

a2 {
    duration = [6, 6]
    constraints = [
      (end(a2) <= 14)
    ]
    effects = [
      start(a2):
        operators -= 1:
        machine2 -= 1:
      end(a2):
        operators += 1:
        machine2 += 1:
    ]
  }

# finish a2 strictly before starting a1
problem.add_constraint(LT(a2.end, a1.start))

# One worker is unavailable over [17, 25)
problem.add_decrease_effect(17, operators, 1)
problem.add_increase_effect(25, operators, 1)
problem

problem name = factory

fluents = [
  integer[0, 1] machine1
  integer[0, 1] machine2
  integer[0, 4] operators
]

initial fluents default = [
  integer[0, 1] machine1 := 1
  integer[0, 1] machine2 := 1
  integer[0, 4] operators := 4
]

initial values = [
  machine1 := 1
  machine2 := 1
  operators := 4
]

quality metrics = [
  minimize makespan
]

BASE: {
    constraints = [
      (end(a2) < start(a1))
    ]
    effects = [
      start + 17:
        operators -= 1:
        operators -= 1:
      start + 25:
        operators += 1:
        operators += 1:
    ]
  }

Activities:
  a1 {
    duration = [3, 3]
    effects = [
      start(a1):
        machine1 -= 1:
        operators -= 2:
      end(a1):
        machine1 += 1:
        operators += 2:
    ]
  }
  a2 {
    duration = [6, 6]
    constraints = [
      (end(a2) <= 14)
    ]
    effects = [
      start(a2):
        operators -= 1:
        machine2 -= 1:
      end(a2):
        operators += 1:
        machine2 += 1:
    ]
  }

As a last step, lets just specify that we want the makespan to be minimized.

problem.add_quality_metric(MinimizeMakespan())

14.5. Solving scheduling problems

Like all problems in the UP, we can access the kind field that is automatically computed to reflect the features in the problem.

print(problem.kind)

PROBLEM_CLASS: ['SCHEDULING']
PROBLEM_TYPE: ['SIMPLE_NUMERIC_PLANNING']
TIME: ['TIMED_EFFECTS', 'DISCRETE_TIME']
EXPRESSION_DURATION: ['INT_TYPE_DURATIONS']
NUMBERS: ['BOUNDED_TYPES']
EFFECTS_KIND: ['DECREASE_EFFECTS', 'INCREASE_EFFECTS']
FLUENTS_TYPE: ['INT_FLUENTS']
QUALITY_METRICS: ['MAKESPAN']

Currently, the only solver supporting scheduling problems is aries. When asking for a oneshot solver, it would automatically be selected to solve the problem.

with OneshotPlanner(problem_kind=problem.kind) as planner:
    res = planner.solve(problem)
    print(res)

status: SOLVED_OPTIMALLY
engine: aries
plan: Schedule:
    [0, 6] a2
    [7, 10] a1

As you can see, all activities are present in the solution, with a2 finishing strictly before starting a1 as imposed in the problem’s constraints.

14.6. Going Further

Reference: Complete parser for jobshop (with operators) problems