Wait time constraint in job scheduling

[selekt]

Hi,

I have the following problem:

1. There is an input queue of jobs called q1 (the jobs don't necessarily need to be processed FIFO)
2. A scheduler needs to pick a job out of q1 queue and schedule it on machines of type t1 and there are n such machines
3. Once the job is completed on a "t1" machine it is placed in a separate queue called q2
4. Now this job needs to be taken from this queue and scheduled on a machine of type t2. There are k machines of type t2.

Constraints:

1. Each job has a deadline that it must be finished by (q1 wait time + t1 processing time + q2 wait time + t2 processing time < deadline time)
2. A job must not spend > c minutes waiting in queue q2 to be processed by a machine of type t2

I have gone through the job shop example and understand the precedence and non-overlapping constraints, but how dow I model the above ^ constraints using the CP solver? Is job shop even the right way to model this problem or it could be modeled differently?

Any help is appreciated.

[lperron]

Do you want to run the scheduler once for a list of jobs, or process the jobs one by one, or one batch at a time? Do you know exactly the processing time of each job?

On the modeling side, each task (t1 and t2 have start and end variables). You can write arbitrary linear constraints on those, thus setup, deadlines, max delay, all are easy to write.

You have max delay constraints in the examples/python/rcpsp_sat.py model, but it is just a precedence with a negative delay.

Laurent Perron | Operations Research | lperron@google.com | (33) 1 42 68 53 00

Le lun. 3 déc. 2018 à 22:07, selekt notifications@github.com a écrit :

Hi,

I have the following problem:

1. There is an input queue of jobs called q1 (the jobs don't necessarily need to be processed FIFO)
2. A scheduler needs to pick a job out of q1 queue and schedule it on machines of type t1 and there are n such machines
3. Once the job is completed on a "t1" machine it is placed in a separate queue called q2
4. Now this job needs to be taken from this queue and scheduled on a machine of type t2. There are k machines of type t2.

Constraints:

1. Each job has a deadline that it must be finished by
2. A job must not spend > c minutes waiting in queue q2 to be processed by a machine of type t2

I have gone through the job shop example and understand the precedence and non-overlapping constraints, but how dow I model the above ^ constraints using the CP solver? Is job shop even the right way to model this problem or it could be modeled differently?

Any help is appreciated.

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/google/or-tools/issues/960, or mute the thread https://github.com/notifications/unsubscribe-auth/AKj17SXXKANX2ZH27y7PkJksm1vJdn3_ks5u1ZKEgaJpZM4Y_aps .

[selekt]

The tasks are coming in continuously in a queue and it is up to the scheduler to process them one by one or one batch a time. The implementation is flexible.

For ever combination of task/machine we know the execution time. A machine can process "y" tasks in parallel and "y" can be any value.

In the job shop scheduling problem I see the "non-overlapping" constraint and the "precedence" constraints defined. But I see no example of how the limit on a "wait time" before a task must be processed on the second machine of type t2 should be modeled.

Also - we have an SLA with our clients. 100% of all tasks don't need to be completed before the deadline, only 80% of them do and that should be "satisfactory". How can I express this objective?

In fact, I am not familiar with constraint programming at all, so any help figuring out how these constraints should be modeled would be helpful. Thanks a lot!

[lperron]

start(next_task) <= end(previous_task) + max_delay Laurent Perron | Operations Research | lperron@google.com | (33) 1 42 68 53 00

Le mar. 4 déc. 2018 à 01:37, selekt notifications@github.com a écrit :

The tasks are coming in continuously in a queue and it is up to the scheduler to process them one by one or one batch a time. The implementation is flexible.

In the job shop scheduling problem I see the "non-overlapping" constraint and the "precedence" constraints defined. But I see no example of how the limit on a "wait time" before a task must be processed on the second machine of type t2 should be modeled.

In fact, I am not familiar with constraint programming at all, so any help figuring out how these constraints should be modeled would be helpful. Thanks a lot!

— You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/google/or-tools/issues/960#issuecomment-443924951, or mute the thread https://github.com/notifications/unsubscribe-auth/AKj17Rt_5c6_9Rm473TC6tQ7dg0Jk-fvks5u1cPmgaJpZM4Y_aps .

[selekt]

Thank you! How might I tell the objective function that only X% of the jobs needs to be completed before the deadline since that is our SLA agreemnt?

[lperron]

for i in all_jobs: job_one_time[i] = model.NewBoolVar('') model.Add(end_of_job[i] <= deadline[i]).OnlyEnforceIf(job_on_time[i])

model.Add(sum(job_on_time) >= X * len(job_on_time) // 100) Laurent Perron | Operations Research | lperron@google.com | (33) 1 42 68 53 00

Le mar. 4 déc. 2018 à 21:20, selekt notifications@github.com a écrit :

Thank you! How might I tell the objective function that only X% of the jobs needs to be completed before the deadline since that is our SLA agreemnt?

— You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/google/or-tools/issues/960#issuecomment-444243528, or mute the thread https://github.com/notifications/unsubscribe-auth/AKj17Xs28ZwL-0T-hwutD3Ydyo6o3vg6ks5u1tj_gaJpZM4Y_aps .

[selekt]

Apologies for yet another question. I am very new to this.

what does the following line mean:

model.Add(end_of_job[i] <= deadline[i]).OnlyEnforceIf(job_on_time[i])

I gather job_one_time is a boolean variable. What does it mean to "sum" booleans here?

model.Add(sum(job_on_time) >= X * len(job_on_time) // 100)

[lperron]

https://github.com/google/or-tools/blob/master/ortools/sat/doc/index.md

Laurent Perron | Operations Research | lperron@google.com | (33) 1 42 68 53 00

Le mer. 5 déc. 2018 à 03:58, selekt notifications@github.com a écrit :

Apologies for yet another question. I am very new to this.

what does the following line mean:

model.Add(end_of_job[i] <= deadline[i]).OnlyEnforceIf(job_on_time[i])

I gather job_one_time is a boolean variable. What does it mean to "sum" booleans here?

model.Add(sum(job_on_time) >= X * len(job_on_time) // 100)

— You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/google/or-tools/issues/960#issuecomment-444340896, or mute the thread https://github.com/notifications/unsubscribe-auth/AKj17auF3JzsxMmM3DLmPvhmfera6cQdks5u1zZpgaJpZM4Y_aps .

[selekt]

Okay. Thanks a lot for your quick responses and patience for a newbie.

So - this is what I have so far. The problem I modeled as a task/machine problem is actually a real world problem that I am trying to solve.

The real world version of the problem is:

There is a restaurant producing orders. Each order has a bunch of meals in it. The order enters an "order queue" that needs to be cooked by a kitchen. The kitchen is not at the same location as the restaurant. There are 2 kitchens -> k1, k2 A kitchen can cook 1 meal at a time. There is a pool of drivers. Let's say there are "d" drivers that pick up food from these kitchens and then deliver them to the restaurant. Each driver can fit 10 meals in their car. An order will never have more than 8 meals. A meal should not be waiting for more than 20 mins to be picked up by a driver or it will get cold. Orders delivered in < 20 mins to the restaurant are good ; anything > 45 min wait is bad.

I have gone through the documentation and examples and tried putting pieces together to solve this. It feels like the documentation is intended for people who already have some experience in ops research and is hard for a newbie to understand.

I took a very simple example. There is one order in the queue with 3 meals in it. 2 kitchens and 2 drivers. 5 mins/meal to cook in the kitchen and 10 mins to deliver it.

The code below is producing a MODEL_INVALID error from the solver. I am not sure what I am doing wrong.

Your help is greatly appreciated. This is a new area for me so I apologize for any obvious rookie mistakes.

def main():
    # create the model
    model = cp_model.CpModel()
    Order = collections.namedtuple("Order", ["meals"])

    order_one = Order(meals=[1, 1, 2])

    kitchen_capacity = model.NewIntVar(0, 1, "kitchen_cap") # can only cook one meal at a time
    driver_capacity = model.NewIntVar(0, 2, "driver_cap") # a driver can carry only 2 meals at a time

    horizon = 45

    kitchen_intervals = []
    driver_intervals = []
    presences = []

    for meal in order_one.meals:
        presence = model.NewBoolVar("meal_order_one_%i" % meal)
        presences.append(presence)

        start_cook = model.NewIntVar(0, horizon, "start_cook_meal_%i" % meal)
        end_cook = model.NewIntVar(0, horizon, "end_cook_meal_%i" % meal)

        start_drive = model.NewIntVar(0, horizon, "start_drive_meal_%i" % meal)
        end_drive = model.NewIntVar(0, horizon, "end_drive_meal_%i" % meal)

        # don't know what to do with this right now
        #master_interval = model.NewIntervalVar(0, horizon, "meal_task_%i" % meal)

        kitchen_one_interval = model.NewOptionalIntervalVar(start_cook, 5, end_cook, presence, "kitchen_one_interval_meal_%i" % meal)
        kitchen_two_interval = model.NewOptionalIntervalVar(start_cook, 5, end_cook, presence,  "kitchen_two_interval_meal_%i" % meal)

        driver_one_interval = model.NewOptionalIntervalVar(start_drive, 10, end_drive, presence, "kitchen_one_interval_meal_%i" % meal)
        driver_two_interval = model.NewOptionalIntervalVar(start_drive, 10, end_drive, presence, "kitchen_two_interval_meal_%i" % meal)

        kitchen_intervals.append(kitchen_one_interval)
        kitchen_intervals.append(kitchen_two_interval)

        driver_intervals.append(driver_one_interval)
        driver_intervals.append(driver_two_interval)

        model.Add(end_cook < start_drive)
        model.Add(start_drive < end_cook + 20) # cannot wait for more than 20 mins ...
        model.Add(end_drive < 45) # .. SLA for the meal

    # add capacities and demands
    model.AddCumulative(kitchen_intervals, [1,1,1], kitchen_capacity)
    model.AddCumulative(driver_intervals, [1,1,1], driver_capacity)

    solver = cp_model.CpSolver()

    solution_printer = SolutionPrinter()
    solver.SolveWithSolutionCallback(model, solution_printer)
    print(solver.ResponseStats())

Thank you for your patience.

[lperron]

A working solution with some comments:

from future import print_function from future import absolute_import from future import division

import collections from ortools.sat.python import cp_model

----------------------------------------------------------------------------

----------------------------------------------------------------------------

def main():

create the model

model = cp_model.CpModel()
Order = collections.namedtuple("Order", ["meals"])

order_one = Order(meals=[1, 1, 2])

driver_capacity = 2

horizon = 45

# One set of intervals per kitchen.
kitchen1_intervals = []
kitchen2_intervals = []
driver_intervals = []
driver_demands = []
presences = []

for meal in order_one.meals:
    presence = model.NewBoolVar("meal_order_one_%i" % meal)
    presences.append(presence)

    start_cook = model.NewIntVar(0, horizon, "start_cook_meal_%i" %

meal) end_cook = model.NewIntVar(0, horizon, "end_cookmeal%i" % meal)

    start_drive = model.NewIntVar(0, horizon, "start_drive_meal_%i" %

meal) end_drive = model.NewIntVar(0, horizon, "end_drivemeal%i" % meal)

    # Normally, create 1 boolean variable per kitchen, and ensure that
    # their sum == 1. Here, we simplify, presence = True -> k1, False

-> k2. kitchen_one_interval = model.NewOptionalIntervalVar( start_cook, 5, end_cook, presence, "kitchen_one_intervalmeal%i" % meal) kitchen_two_interval = model.NewOptionalIntervalVar( start_cook, 5, end_cook, presence.Not(), "kitchen_two_intervalmeal%i" % meal)

    # We will use a cumulative. We do not need optional intervals.
    driver_interval = model.NewIntervalVar(
        start_drive, 10, end_drive,
        "kitchen_one_interval_meal_%i" % meal)

    kitchen1_intervals.append(kitchen_one_interval)
    kitchen2_intervals.append(kitchen_two_interval)

    driver_intervals.append(driver_interval)
    driver_demands.append(1)  # Make sure the 2 arrays have the same

length.

    model.Add(end_cook < start_drive)
    model.Add(start_drive < end_cook + 20) # cannot wait for more than

20 mins ... model.Add(end_drive < 45) # .. SLA for the meal.

# add capacities and demands
model.AddNoOverlap(kitchen1_intervals)
model.AddNoOverlap(kitchen2_intervals)

model.AddCumulative(driver_intervals, driver_demands, driver_capacity)

# minimize end drive.
model.Minimize(end_drive)

print(model.Validate())

solver = cp_model.CpSolver()

solution_printer = cp_model.ObjectiveSolutionPrinter()
solver.SolveWithSolutionCallback(model, solution_printer)
print(solver.ResponseStats())

main()

Laurent Perron | Operations Research | lperron@google.com | (33) 1 42 68 53 00

Le jeu. 6 déc. 2018 à 05:41, selekt notifications@github.com a écrit :

Okay. Thanks a lot for your quick responses and patience for a newbie.

So - this is what I have so far. The problem I modeled as a task/machine problem is actually a real world problem that I am trying to solve.

The real world version of the problem is:

There is a restaurant producing orders. Each order has a bunch of meals in it. The order enters an "order queue" that needs to be cooked by a kitchen. The kitchen is not at the same location as the restaurant. There are 2 kitchens -> k1, k2 A kitchen can cook 1 meal at a time. There is a pool of drivers. Let's say there are "d" drivers that pick up food from these kitchens and then deliver them to the restaurant. Each driver can fit 10 meals in their car. An order will never have more than 8 meals. A meal should not be waiting for more than 20 mins to be picked up by a driver or it will get cold. Orders delivered in < 20 mins to the restaurant are good ; anything > 45 min wait is bad.

I have gone through the documentation and examples and tried putting pieces together to solve this. It feels like the documentation is intended for people who already have some experience in ops research and is hard for a newbie to understand.

I took a very simple example. There is one order in the queue with 3 meals in it. 2 kitchens and 2 drivers. 5 mins/meal to cook in the kitchen and 10 mins to deliver it.

The code below is producing a MODEL_INVALID error from the solver. I am not sure what I am doing wrong.

Your help is greatly appreciated. This is a new area for me so I apologize for any obvious rookie mistakes.

def main():

create the model

model = cp_model.CpModel()
Order = collections.namedtuple("Order", ["meals"])

order_one = Order(meals=[1, 1, 2])

kitchen_capacity = model.NewIntVar(0, 1, "kitchen_cap") # can only cook one meal at a time
driver_capacity = model.NewIntVar(0, 2, "driver_cap") # a driver can carry only 2 meals at a time

horizon = 45

kitchen_intervals = []
driver_intervals = []
presences = []

for meal in order_one.meals:
    presence = model.NewBoolVar("meal_order_one_%i" % meal)
    presences.append(presence)

    start_cook = model.NewIntVar(0, horizon, "start_cook_meal_%i" % meal)
    end_cook = model.NewIntVar(0, horizon, "end_cook_meal_%i" % meal)

    start_drive = model.NewIntVar(0, horizon, "start_drive_meal_%i" % meal)
    end_drive = model.NewIntVar(0, horizon, "end_drive_meal_%i" % meal)

    # don't know what to do with this right now
    #master_interval = model.NewIntervalVar(0, horizon, "meal_task_%i" % meal)

    kitchen_one_interval = model.NewOptionalIntervalVar(start_cook, 5, end_cook, presence, "kitchen_one_interval_meal_%i" % meal)
    kitchen_two_interval = model.NewOptionalIntervalVar(start_cook, 5, end_cook, presence,  "kitchen_two_interval_meal_%i" % meal)

    driver_one_interval = model.NewOptionalIntervalVar(start_drive, 10, end_drive, presence, "kitchen_one_interval_meal_%i" % meal)
    driver_two_interval = model.NewOptionalIntervalVar(start_drive, 10, end_drive, presence, "kitchen_two_interval_meal_%i" % meal)

    kitchen_intervals.append(kitchen_one_interval)
    kitchen_intervals.append(kitchen_two_interval)

    driver_intervals.append(driver_one_interval)
    driver_intervals.append(driver_two_interval)

    model.Add(end_cook < start_drive)
    model.Add(start_drive < end_cook + 20) # cannot wait for more than 20 mins ...
    model.Add(end_drive < 45) # .. SLA for the meal

# add capacities and demands
model.AddCumulative(kitchen_intervals, [1,1,1], kitchen_capacity)
model.AddCumulative(driver_intervals, [1,1,1], driver_capacity)

solver = cp_model.CpSolver()

solution_printer = SolutionPrinter()
solver.SolveWithSolutionCallback(model, solution_printer)
print(solver.ResponseStats())

Thank you for your patience.

— You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/google/or-tools/issues/960#issuecomment-444746280, or mute the thread https://github.com/notifications/unsubscribe-auth/AKj17WoAgEVvtXaEyYwq8v9WrkX2YSE0ks5u2J_wgaJpZM4Y_aps .

[selekt]

Thanks Laurent! This gives me enough to understand and work on the problem.

Just a couple follow up questions on your comments:

• why did you decide to use an optional interval for the kitchens and not for the drivers. Is this because the kitchen capacity is 1?
• could we have also used the "addCumulative" for kitchens with a capacity of 1. Is this equivalent to the above ^?

[lperron]

1) If you use a cumulative, all tasks are done using this cumulative. I use optional intervals when there are alternative way to execute them (kitchen1 OR kitchen2). When this happens, you create one optional copy of the master interval (not needed here), and you add the exactly one must be performed. Here, you have only one driver resource, thus no not for optionality.

2) cumulative (tasks, [1...1], 1) will be presolved into a no_overlap. Laurent Perron | Operations Research | lperron@google.com | (33) 1 42 68 53 00

Le dim. 9 déc. 2018 à 02:55, selekt notifications@github.com a écrit :

Thanks Laurent! This gives me enough to understand and work on the problem.

Just a couple follow up questions on your comments:

• why did you decide to use an optional interval for the kitchens and not for the drivers. Is this because the kitchen capacity is 1?
• could we have also used the "addCumulative" for kitchens with a capacity of 1. Is this equivalent to the above ^?

— You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/google/or-tools/issues/960#issuecomment-445504153, or mute the thread https://github.com/notifications/unsubscribe-auth/AKj17VS4RzoT1zLUaumUtUjeddynBSyfks5u3G2lgaJpZM4Y_aps .

[selekt]

Based on your example code and what I have learnt so far, I came up with the following generic solution to this problem. However, when I run the solver it runs for an infinite amount of time and keeps printing solutions. I looked at rcpsp for an example of how to associate a "master" interval with a set of optional intervals like you had mentioned. What am I doing wrong?

   meal_one = Meal(1)
    meal_two = Meal(2)
    meals = [meal_one, meal_two]
    orde = Order(meals)
    orders = [orde]

    # create the model
    model = cp_model.CpModel()

    kitchen_capacity = 5  # a kitchen can only cook 5 meals at a time
    driver_capacity = 20 # a driver can carry only 20 meals at a time

    horizon = 40  # the max time a meal can be cooked at .. we say at the 40th minute mark

    kitchen_one_intervals = []
    kitchen_two_intervals = []

    kitchen_one_demands = []
    kitchen_two_demands = []

    end_drives = []
    driver_intervals = collections.defaultdict(list)

    number_of_drivers = 2
    driver_presences = collections.defaultdict(list)

    driver_demands = collections.defaultdict(list)

    job_master_drive_start = {}
    job_master_drive_end = {}

    job_driver_starts = collections.defaultdict(list)
    job_driver_ends = collections.defaultdict(list)
    job_driver_presences = collections.defaultdict(list)

    for o in range(len(orders)):
         order = orders[o]

         # create meal cooking constraints
         for m in range(len(order.get_meals())):
             job_id = "job_%i_%i" % (o,m)
             kitchen_one_presence = model.NewBoolVar(job_id + "_cook_presence_k1")
             kitchen_two_presence = model.NewBoolVar(job_id + "_cook_presence_k2")

             start_master_cook = model.NewIntVar(0, horizon, "master_start_meal_" + job_id)
             end_master_cook = model.NewIntVar(0, horizon, "master_end_meal_" + job_id)

             start_cook_time_k1 = model.NewIntVar(0, horizon, "k1_start_meal_" + job_id)
             end_cook_time_k1 = model.NewIntVar(0, horizon, "k1_end_meal_" + job_id)

             start_cook_time_k2 = model.NewIntVar(0, horizon, "k2_start_meal_" + job_id)
             end_cook_time_k2 = model.NewIntVar(0, horizon, "k2_end_meal_" + job_id)

             # the meal gets cooked in either kitchen
             # let's say it takes 5 minutes to cook every meal in every kitchen
             kitchen_one_optional = model.NewOptionalIntervalVar(start_cook_time_k1, 5, end_cook_time_k1, kitchen_one_presence
                                                                 , "kitchen_one_" + job_id)

             kitchen_two_optional = model.NewOptionalIntervalVar(start_cook_time_k2, 5, end_cook_time_k2, kitchen_two_presence
                                                             , "kitchen_two_" + job_id)

             # TODO: add m9 and m10 constraints ...

             kitchen_one_intervals.append(kitchen_one_optional)
             kitchen_two_intervals.append(kitchen_two_optional)

             # takes up demand "1" when a meal is cooked in a kitchen
             kitchen_one_demands.append(1)
             kitchen_two_demands.append(1)

             # master kitchen interval
             model.Add(sum([kitchen_one_presence, kitchen_two_presence]) == 1)
             cook_duration = model.NewIntVar(5, 5, "master_cook_duration_" + job_id)
             master_kitchen_interval = model.NewIntervalVar(start_master_cook, cook_duration, end_master_cook, "kitchen_master_interval_" + job_id)

             model.Add(start_cook_time_k1 == start_master_cook).OnlyEnforceIf(kitchen_one_presence)
             model.Add(end_cook_time_k1 == end_master_cook).OnlyEnforceIf(kitchen_one_presence)
             model.Add(start_cook_time_k2 == start_master_cook).OnlyEnforceIf(kitchen_two_presence)
             model.Add(end_cook_time_k2 == end_master_cook).OnlyEnforceIf(kitchen_two_presence)
             model.Add(cook_duration == 5).OnlyEnforceIf(kitchen_one_presence)
             model.Add(cook_duration == 5).OnlyEnforceIf(kitchen_two_presence)

             # master drive interval
             start_master_drive = model.NewIntVar(0, horizon, "start_drive_" + job_id)
             end_master_drive = model.NewIntVar(0, horizon, "end_drive_" + job_id)
             drive_duration = model.NewIntVar(10,10, "master_duration_" + job_id)
             master_drive_interval = model.NewIntervalVar(start_master_drive, drive_duration , end_master_drive,
                                                          "drive_master_interval_" + job_id)

             job_master_drive_start[job_id] = start_master_drive
             job_master_drive_end[job_id] = end_master_drive

             # create delivery constraints
             for d in range(number_of_drivers):

                 # vars to represent start/end drives
                 start_drive = model.NewIntVar(0, horizon, "start_meal_drive_" + job_id + " _" + str(d))
                 end_drive = model.NewIntVar(0, horizon, "end_meal_drive_" + job_id + " _" + str(d))
                 job_driver_presence = model.NewBoolVar(job_id + "_driver_presence" + "_" + str(d))

                 job_driver_starts[job_id].append(start_drive)
                 job_driver_ends[job_id].append(end_drive)

                 end_drives.append(end_drive)

                 # a meal must not wait > 20 mins waiting to be picked up
                 model.Add(end_cook_time_k1 < start_drive)
                 model.Add(start_drive < end_cook_time_k1 + 20)
                 model.Add(end_drive < 40)

                 # option to drive this meal by driver d
                 # let's assume for simplicity that every driver d takes 10 mins to drive the meal to
                 # any restaurant .. in the real world application this would be different
                 # depending on the time taken to drive to the restaurant where the order came from
                 driver_interval = model.NewOptionalIntervalVar(start_drive, 10, end_drive, job_driver_presence,
                                                                "driver_" + str(d) + "_" + job_id)

                 driver_intervals[d].append(driver_interval)
                 driver_presences[job_id].append(job_driver_presence)

                 # 1 meal delivery -> 1 demand from the driver
                 driver_demands[d].append(1)

             # one meal gets assigned to one driver
             # so the sum of all "driver presences" for this delivery must be 1
             for job_id, job_driver_presences in driver_presences.items():
                 model.Add(sum(job_driver_presences) == 1)

             for d in range(number_of_drivers):
                 start_master = job_master_drive_start[job_id]
                 end_master = job_master_drive_end[job_id]
                 p = driver_presences[job_id][d]
                 model.Add(start_master == job_driver_starts[job_id][d]).OnlyEnforceIf(p)
                 model.Add(end_master == job_driver_ends[job_id][d]).OnlyEnforceIf(p)
                 model.Add(drive_duration == 10).OnlyEnforceIf(p)

             # all meals belonging to a single order must be delivered by the same driver
             # unsure on how to model this constraint ... but going to leave it for now

    # add capacities and demands
    for d, intervals in driver_intervals.items():
        model.AddCumulative(intervals, driver_demands[d], driver_capacity)

    model.AddCumulative(kitchen_one_intervals, kitchen_one_demands, kitchen_capacity)
    model.AddCumulative(kitchen_two_intervals, kitchen_two_demands, kitchen_capacity)

    for end_drive in end_drives:
        model.Minimize(end_drive)

    print(model.Validate())

    solver = cp_model.CpSolver()

    solution_printer = cp_model.ObjectiveSolutionPrinter()
    solver.SolveWithSolutionCallback(model, solution_printer)
    print(solver.ResponseStats())

[selekt]

For anyone who might be following this thread for educational purposes, I think have my code working! The mistake above ^ was that I was "minimizing" the drive_end_time for each optional interval instead of the associated master interval.

def main():

    orders = []
    # create 10 orders
    for i in range(1,10):
        # pick a random number of meals for this order between 1-8
        # max customers per order is 8
        number_of_meals = random.randint(1,8)
        meals = []
        for j in range(number_of_meals):
            # pick a random meal id between 1 and 10
            meal_id = random.randint(1,10)
            meal = Meal(meal_id)
            meals.append(meal)

        order = Order(meals)
        orders.append(order)

    # create the model
    model = cp_model.CpModel()

    kitchen_capacity = 5  # a kitchen can only cook 5 meals at a time
    driver_capacity = 20 # a driver can carry only 20 meals at a time

    horizon = 40  # the max time a meal can be cooked at .. we say at the 40th minute mark

    kitchen_one_intervals = []
    kitchen_two_intervals = []

    kitchen_one_demands = []
    kitchen_two_demands = []

    end_drives = []
    driver_intervals = collections.defaultdict(list)

    number_of_drivers = 2
    driver_presences = collections.defaultdict(list)

    driver_demands = collections.defaultdict(list)

    job_master_drive_start = {}
    job_master_drive_end = {}

    job_driver_starts = collections.defaultdict(list)
    job_driver_ends = collections.defaultdict(list)
    job_to_driver_intervals = collections.defaultdict(list)

    kitchen_master_intervals =  []

    for o in orders:
        print (o)

    for o in range(len(orders)):
         order = orders[o]

         # create meal cooking constraints
         for m in range(len(order.get_meals())):
             job_id = "job_%i_%i" % (o,m)
             kitchen_one_presence = model.NewBoolVar(job_id + "_cook_presence_k1")
             kitchen_two_presence = model.NewBoolVar(job_id + "_cook_presence_k2")

             start_master_cook = model.NewIntVar(0, horizon, "master_start_meal_" + job_id)
             end_master_cook = model.NewIntVar(0, horizon, "master_end_meal_" + job_id)

             start_cook_time_k1 = model.NewIntVar(0, horizon, "k1_start_meal_" + job_id)
             end_cook_time_k1 = model.NewIntVar(0, horizon, "k1_end_meal_" + job_id)

             start_cook_time_k2 = model.NewIntVar(0, horizon, "k2_start_meal_" + job_id)
             end_cook_time_k2 = model.NewIntVar(0, horizon, "k2_end_meal_" + job_id)

             # the meal gets cooked in either kitchen
             # let's say it takes 5 minutes to cook every meal in every kitchen
             kitchen_one_optional = model.NewOptionalIntervalVar(start_cook_time_k1, 5, end_cook_time_k1, kitchen_one_presence
                                                                 , "kitchen_one_" + job_id)

             kitchen_two_optional = model.NewOptionalIntervalVar(start_cook_time_k2, 5, end_cook_time_k2, kitchen_two_presence
                                                             , "kitchen_two_" + job_id)

             # TODO: add m9 and m10 constraints ...

             kitchen_one_intervals.append(kitchen_one_optional)
             kitchen_two_intervals.append(kitchen_two_optional)

             # takes up demand "1" when a meal is cooked in a kitchen
             kitchen_one_demands.append(1)
             kitchen_two_demands.append(1)

             # master kitchen interval
             model.Add(sum([kitchen_one_presence, kitchen_two_presence]) == 1)
             cook_duration = model.NewIntVar(5, 5, "master_cook_duration_" + job_id)
             master_kitchen_interval = model.NewIntervalVar(start_master_cook, cook_duration, end_master_cook, "kitchen_master_interval_" + job_id)

             model.Add(start_cook_time_k1 == start_master_cook).OnlyEnforceIf(kitchen_one_presence)
             model.Add(end_cook_time_k1 == end_master_cook).OnlyEnforceIf(kitchen_one_presence)
             model.Add(start_cook_time_k2 == start_master_cook).OnlyEnforceIf(kitchen_two_presence)
             model.Add(end_cook_time_k2 == end_master_cook).OnlyEnforceIf(kitchen_two_presence)

             # master drive interval
             start_master_drive = model.NewIntVar(0, horizon, "start_drive_" + job_id)
             end_master_drive = model.NewIntVar(0, horizon, "end_drive_" + job_id)
             master_drive_interval = model.NewIntervalVar(start_master_drive, 10 , end_master_drive,
                                                          "drive_master_interval_" + job_id)

             job_master_drive_start[job_id] = start_master_drive
             job_master_drive_end[job_id] = end_master_drive

             kitchen_master_intervals.append(end_master_drive)

             # create delivery constraints
             for d in range(number_of_drivers):

                 # vars to represent start/end drives
                 start_drive = model.NewIntVar(0, horizon, "start_meal_drive_" + job_id + "_" + str(d))
                 end_drive = model.NewIntVar(0, horizon, "end_meal_drive_" + job_id + " _" + str(d))
                 job_driver_presence = model.NewBoolVar(job_id + "_driver_presence" + "_" + str(d))

                 job_driver_starts[job_id].append(start_drive)
                 job_driver_ends[job_id].append(end_drive)

                 end_drives.append(end_master_drive)

                 # option to drive this meal by driver d
                 # let's assume for simplicity that every driver d takes 10 mins to drive the meal to
                 # any restaurant .. in the real world application this would be different
                 # depending on the time taken to drive to the restaurant where the order came from
                 driver_interval = model.NewOptionalIntervalVar(start_drive, 10, end_drive, job_driver_presence,
                                                                "driver_" + str(d) + "_" + job_id)

                 driver_intervals[d].append(driver_interval)
                 job_to_driver_intervals[job_id].append(driver_interval)
                 driver_presences[job_id].append(job_driver_presence)

                 # 1 meal delivery -> 1 demand from the driver
                 driver_demands[d].append(1)

             # one meal gets assigned to one driver
             # so the sum of all "driver presences" for this delivery must be 1
             for job_id, job_driver_presences in driver_presences.items():
                 model.Add(sum(job_driver_presences) == 1)

             for d in range(number_of_drivers):
                 start_master = job_master_drive_start[job_id]
                 end_master = job_master_drive_end[job_id]
                 p = driver_presences[job_id][d]
                 model.Add(start_master == job_driver_starts[job_id][d]).OnlyEnforceIf(p)
                 model.Add(end_master == job_driver_ends[job_id][d]).OnlyEnforceIf(p)

             # all meals belonging to a single order must be delivered by the same driver
             # unsure on how to model this constraint ... but going to leave it for now

             # precedences
             # a meal must not wait > 20 mins waiting to be picked up
             model.Add(end_master_cook < start_master_drive)
             model.Add(start_master_drive < end_master_cook + 20)
             model.Add(end_master_drive < 40)

    # add capacities and demands
    for d, intervals in driver_intervals.items():
        model.AddCumulative(intervals, driver_demands[d], driver_capacity)

    model.AddCumulative(kitchen_one_intervals, kitchen_one_demands, kitchen_capacity)
    model.AddCumulative(kitchen_two_intervals, kitchen_two_demands, kitchen_capacity)

    for end_drive in end_drives:
        model.Minimize(end_drive)

    print("validation: " +  model.ModelStats())

    solver = cp_model.CpSolver()

    solution_printer = cp_model.ObjectiveSolutionPrinter()
    solver.SolveWithSolutionCallback(model, solution_printer)
    print(solver.ResponseStats())

    for inter in kitchen_master_intervals:
        print ("value: " +  str(solver.Value(inter)))

[lperron]

Seems I can close this thread.

[huythachmario]

@selekt thank you for sharing this. I have a problem as same as yours with a little bit difference: setup time. If a kitchen cooks a new meal which is similar to the previous meal, we no need a setup time, but if the kitchen cooks a new meal which is different from the cooked previous meal, we need an extract time for setup, such as clean cookers, prepare materials.... Do you have any suggestion? Thank you in advance.

[lperron]

You can have a look at:

https://github.com/google/or-tools/blob/master/examples/contrib/scheduling_with_transitions_sat.py

especially the code around the circuit constraint.

With the circuit constraint and some reified constraints, you can map a disjunctive constraint to a sequence in a graph, that is a set of Boolean variables indicating the direct successor of a task. With those Boolean variables, you can model transitions times, setup times, setup costs...

Please note that the notion of successor is not defined for cumulative constraints, you need to go back to a disjunctive constraint. Laurent Perron | Operations Research | lperron@google.com | (33) 1 42 68 53 00

Le ven. 22 févr. 2019 à 08:13, huythachmario notifications@github.com a écrit :

@selekt https://github.com/selekt thank you for sharing this. I have a problem as same as yours with a little bit difference: setup time. If a kitchen cooks a new meal which is similar to the previous meal, we no need a setup time, but if the kitchen cooks a new meal which is different from the cooked previous meal, we need an extract time for setup, such as clean cookers, prepare materials.... Do you have any suggestion? Thank you in advance.

— You are receiving this because you modified the open/close state. Reply to this email directly, view it on GitHub https://github.com/google/or-tools/issues/960#issuecomment-466297631, or mute the thread https://github.com/notifications/unsubscribe-auth/AKj17St32ZhK6Z-0CsnoZbAIdP4uB25dks5vP5iwgaJpZM4Y_aps .

[nkierdem]

Do you want to run the scheduler once for a list of jobs, or process the jobs one by one, or one batch at a time? Do you know exactly the processing time of each job?

@lperron What would be different if jobs were processed one by one?

[vkb-bansal]

what does minimizing individual variable mean here:

for end_drive in end_drives:
        model.Minimize(end_drive)

If there is a relation between end_drive, how would it minimize. Minimizing something like sum(end_drives) makes sense. I tried the code below and it maximizes only one variable.

using Google.OrTools.Sat;

var model = new CpModel();

var st1 = model.NewIntVar(0, 6, "st1");
var en1 = model.NewIntVar(0, 6, "en1");
var int1 = model.NewIntervalVar(st1, 2, en1, "int1");

var st2 = model.NewIntVar(0, 6, "st2");
var en2 = model.NewIntVar(0, 6, "en2");
var int2 = model.NewIntervalVar(st2, 2, en2, "int2");

model.AddNoOverlap(new[] { int1, int2 });
model.Maximize(st1);
model.Maximize(st2);

var solver = new CpSolver();
var res = solver.Solve(model);
Console.WriteLine(solver.Value(st1)); // prints 0
Console.WriteLine(solver.Value(st2)); // print 4
Console.ReadKey();

[lperron]

1) do not reuse old close issues. 2) calling minimize() twice overwrite the first objective. Laurent Perron | Operations Research | @.*** | (33) 1 42 68 53 00

Le lun. 6 nov. 2023 à 11:36, vaibhav kumar bansal @.***> a écrit :

what does minimizing individual variable mean here: for end_drive in end_drives: model.Minimize(end_drive)

If there is a relation between end_drive, how would it minimize. Minimizing something like sum(end_drives) makes sense. I tried the code below and it maximizes only one variable.

`using Google.OrTools.Sat;

var model = new CpModel();

var st1 = model.NewIntVar(0, 6, "st1"); var en1 = model.NewIntVar(0, 6, "en1"); var int1 = model.NewIntervalVar(st1, 2, en1, "int1");

var st2 = model.NewIntVar(0, 6, "st2"); var en2 = model.NewIntVar(0, 6, "en2"); var int2 = model.NewIntervalVar(st2, 2, en2, "int2");

model.AddNoOverlap(new[] { int1, int2 }); model.Maximize(st1); model.Maximize(st2);

var solver = new CpSolver(); var res = solver.Solve(model); Console.WriteLine(solver.Value(st1)); // prints 0 Console.WriteLine(solver.Value(st2)); // print 4 Console.ReadKey();

`

— Reply to this email directly, view it on GitHub https://github.com/google/or-tools/issues/960#issuecomment-1794525415, or unsubscribe https://github.com/notifications/unsubscribe-auth/ACUPL3PQQHSM3Z6GW5RC4S3YDC4RZAVCNFSM4GH5VJWKU5DIOJSWCZC7NNSXTN2JONZXKZKDN5WW2ZLOOQ5TCNZZGQ2TENJUGE2Q . You are receiving this because you were mentioned.Message ID: @.***>