Shift crossing (fake time unit)

Source: scheduling/example_16_shift_crossing_fake_time_unit.py

What it does

Prevents tasks from straddling shift boundaries by inserting a tiny fake break at each boundary. Every task is required to not overlap those fake breaks.

var_shift_break_intervals[s, e] = model.new_fixed_size_interval_var(
    start=s, size=e - s, name="shift_edge",
)
for s, e in synthetic_shift_breaks:
    for t in tasks:
        model.add_no_overlap([var_task_intervals[t], var_shift_break_intervals[s, e]])

Real breaks are still modeled with add_cumulative as usual.

Concepts

• Shifts (synthetic break approach)
• Breaks

Source

from ortools.sat.python import cp_model

# Initiate
model = cp_model.CpModel()

# 1. Data

synthetic_shift_breaks = {(4, 5), (9, 10)}
breaks = {(0, 2)}
tasks = {1}
processing_time = {1: 3}
max_time = 10

var_task_starts = {
    task: model.new_int_var(0, max_time, f"task_{task}_start") for task in tasks
}
var_task_ends = {
    task: model.new_int_var(0, max_time, f"task_{task}_end") for task in tasks
}

var_task_intervals = {
    task: model.new_interval_var(
        var_task_starts[task], processing_time[task], var_task_ends[task], name=f"interval_t{task}"
    ) for task in tasks
}

# Add break time
var_break_intervals = {
    (start, end): model.new_fixed_size_interval_var(start=start, size=end-start, name='a_break')
    for (start, end) in breaks
}

intervals = list(var_task_intervals.values()) + list(var_break_intervals.values())

demands = [1]*len(tasks) + [1]*len(breaks)

model.add_cumulative(intervals=intervals, demands=demands, capacity=1)


# THE CONSTRAINT for synthetic shift break time unit


var_shift_break_intervals = {
    (start, end): model.new_fixed_size_interval_var(start=start, size=end-start, name='a_break')
    for (start, end) in synthetic_shift_breaks
}

for start, end in synthetic_shift_breaks:
    print(start, end)
    for task in tasks:
        model.add_no_overlap([var_task_intervals[task], var_shift_break_intervals[start, end]])



# 3. Objectives

make_span = model.new_int_var(0, max_time, "make_span")

model.add_max_equality(
    make_span,
    [var_task_ends[task] for task in tasks]
)

model.minimize(make_span)


# 4. Solve

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


# 5. Results

if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:

    print('===========================  TASKS SUMMARY  ===========================')
    for task in tasks:
        print(f'Task {task} ',
              solver.value(var_task_starts[task]), solver.value(var_task_ends[task]),
              )

    print('Make-span:', solver.value(make_span))

elif status == cp_model.INFEASIBLE:
    print("Infeasible")
elif status == cp_model.MODEL_INVALID:
    print("Model invalid")
else:
    print(status)