0

I want to include downtime in a specific way to, e.g. the Job shop example in the official tutorial using OR-Tools CP-Sat solver with Python. I want to allow a machine to start processing a task, then have downtime, and afterwards continue finishing the same task.

The answer to a similar question here: https://stackoverflow.com/a/75901853/22301210 only shows how we can ensure that a task does not end when the machine is down. The answer given was to include the following

if machine == 1:
    model.AddLinearExpressionInDomain(
        all_tasks[job_id, task_id].end,
        cp_model.Domain.FromIntervals([[0, 2], [4, horizon]]))

However, this implies that the task can still be processed during the downtime, it will simply end afterwards.

The same question as I have was asked here: https://groups.google.com/g/or-tools-discuss/c/ZMHvaoK2Z_Q?pli=1 . The answer given was to include a NewIntervalVar during the downtime:

machine_to_intervals[0].append(model.NewIntervalVar(0, 10, 10, 'weekend_0'))

However, in this situation the machine can't start processing a task before downtime and end it after. It will have to be finished processing it before downtime, or start processing it afterwards.

In case we want to process a task of 4 time units on machine 1, and this machine is down in time interval [2,4]. How can we allow the machine to process it from time 0 to 2, and then continue from 4 to 6?

Edit: I actually want to use it for a more complicated scheduling problem: a flexible job shop with a big amount of tasks and many possible start times and durations of machine downtime. For example, given a dictionary with machine downtime intervals per machine

machine_downtime_intervals = {0: [(2,5)], 1 : [(2,3),(6,7),(9,14)], 2: [(3,5)}

minimize the makespan in a flexible job shop problem, where the duration of a task on an a machine is extended by the machine's downtime.

rellorolo
  • 1
  • 1

1 Answers1

0

You can extend the duration if it spans across an break, without introducing the break interval.

See the code here: https://github.com/google/or-tools/blob/stable/ortools/sat/docs/scheduling.md#intervals-spanning-over-breaks-in-the-calendar

Laurent Perron
  • 8,594
  • 1
  • 8
  • 22
  • Thank you for your (fast) reply! This works well for these more simple job shop scheduling situations, such as the example I gave. However, I want to apply it to a flexible job shop problem (such as here: https://github.com/google/or-tools/blob/stable/examples/python/flexible_job_shop_sat.py) where machines can process many jobs and can have many possible moments and durations of downtime. The duration extention as you mention will then become quite complicated, right? Is there an alternative? Btw, this is my first stackexchange question, would it be best to edit my question? – rellorolo Jul 28 '23 at 14:43
  • with CP-SAT, I do not see another way. You can also ignore downtime, and fix the solution in a second phase. – Laurent Perron Jul 28 '23 at 16:55
  • Ah, that is too bad. To me it sounded like this type of problem would be really suited for OR-tools CP-SAT solver. So for example, given a dictionary with machine downtime intervals per machine ```python machine_downtime_intervals = {0: [(2,5)], 1 : [(2,3),(6,7),(9,14)], 2: [(3,5)} ``` I then want to extend the duration of the interval of each task if the task is processed on a machine during its downtime. I imagined it to be solvable with some channeling constraints. But I got really stuck with the problem an hoped someone had solved it, as I saw some people with the same problem online – rellorolo Jul 29 '23 at 12:05
  • This is not that complex. And it only affect the copy on that resource. – Laurent Perron Jul 29 '23 at 16:01
  • Thank you for your reply again and for your patience. So if this would be part of the job shop example from the google tutorial. What would I need to add? In the end my situation is more complicated but I think this would translate to any more complicated scheduling problem. Once again, I am new to posting on stackoverflow. So sorry for not formulating it clearly enough… – rellorolo Jul 29 '23 at 19:06