Job shop problem with breaks

[Jakub Bedlek]

Hi,
I was looking on examples from guides section and trying to add breaks/idles to job shop problem, but I don't know how to do it. I didn't find any example on it. Let's say we have example from: https://developers.google.com/optimization/scheduling/job_shop#entire-program 

What is the correct way to add breaks for machines (if possible in Java) ?  For example machine 0 and 2 should have break every 3 time units and machine 1 should have break every 4 time units (see picture in attachments). If there is some job before break which couldn't be finished, it can continue after break.

Thank you,

Jakub

[Rushabh Doshi]

Hi Jakub,

https://github.com/google/or-tools/blob/stable/examples/python/jobshop_ft06_distance_sat.py

This is an example in python on how to add distance between the jobs on the same machine. This is useful if you have constraints like requiring gaps of x minutes between manufacturing products of different groups. An example would be that if you are scheduling product A after product B then you need 50 minutes of downtime but if you are scheduling product C after product A then you need 130 minutes of downtime. 

Check out a previous discussion in the group about implementing such changeovers:

https://groups.google.com/g/or-tools-discuss/c/rC0rIiEO-8Q/m/Wi0YqrBtBgAJ

--
You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/92d18ddb-2dc9-4d9a-9bfa-17a87f8165d4n%40googlegroups.com.

[Jakub Bedlek]

Hi,
thank you for your response I will check it.

Dátum: piatok 29. júla 2022, čas: 9:18:05 UTC+2, odosielateľ: rushabh...@gmail.com

[Jakub Bedlek]

Hi,
I checked that code but it is little bit different.
I am trying to implement break/idle time for machine. For example if machine 0 can work only 8 hours per day and machine 1 can work only 16 hours per day and machine 2 works non stop. Then if we have some task which has to be processed on machine 0 and time to finish that task is more than 8 hours, it has to be finished the next day and then it can go to be procesed by machine 1 etc.. So I wondering if is possible to implement these types of conditions.

Dátum: piatok 29. júla 2022, čas: 9:41:54 UTC+2, odosielateľ: Jakub Bedlek

[Rushabh Doshi]

Are there fixed schedules for when the machines are not available? An example is that Machine 0 will not accept a new job between 2 to 4 pm. These can be easily handled by blocking these time intervals on the machines.

In your case, you need 2 things. One is a way to keep track of hours for which the machine was on and after 8 hours on that day you cannot accept new jobs. Switching jobs between 2 machines will be a bit difficult.

Let me think it over.

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/7e87c2b5-1d5e-46fd-b859-c5d7fe4aa759n%40googlegroups.com.

[Jakub Bedlek]

Thanks for reply,

yes there are fixed schedules for machines when they are not available. Can you provide some example on how to block these intervals please ? 

And thanks for thinking about switching jobs between multiple machines.

Dátum: utorok 2. augusta 2022, čas: 10:05:31 UTC+2, odosielateľ: rushabh...@gmail.com

[Rushabh Doshi]

For fixed schedules what you do is you create a NewIntervalVar variable where you specify the start and end time of the time period when the machine will not be available. There’s an example in python 

https://github.com/google/or-tools/blob/stable/examples/python/jobshop_with_maintenance_sat.py

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/8482a539-5a3c-44d7-9749-93ea50af1e02n%40googlegroups.com.

[Jakub Bedlek]

Thanks, this is what I was looking for. And if you figure out how to switch jobs between multiple machines or have some idea, let me know please.

Dátum: utorok 2. augusta 2022, čas: 11:28:18 UTC+2, odosielateľ: rushabh...@gmail.com

[Jakub Bedlek]

One more question about breaks. I try to add break like that, it won't split the task. If task take 3 hours and before break there is 2 hours free window it doesn't split the task but the task will start after the break ends. Is there some way to automatically split the task or it has to be manualy ? Like split the task to shorter tasks, for example 3 tasks where each take 1 hour ? 

Dátum: utorok 2. augusta 2022, čas: 12:26:53 UTC+2, odosielateľ: Jakub Bedlek

[PC See]

Try  https://github.com/or-tools/or-tools/blob/main/examples/cpp/variable_intervals_sat.cc

[Roelof Kuipers]

Hello, did you manage to solve this? I have the same problem.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. I am stuck with that unfortunately.

[Jakub Bedlek]

Hi, I found this answer https://groups.google.com/g/or-tools-discuss/c/DA_4Pniwhn8/m/BH2vO5K1BgAJ and it was working quite well.

Dátum: nedeľa 30. júla 2023, čas: 11:07:53 UTC+2, odosielateľ: roelof....@kineo.ai

[Roelof Kuipers]

Thank you for your reply. 'AddLinearConstraintWithBounds' is not working anymore for newer versions of OR-Tools. Do you know how to replace 'AddLinearConstraintWithBounds' in the example by 'AddLinearExpressionInDomain' ? What linear expression do you use?

[Jakub Bedlek]

Yes, I used 'addLinearExpressionInDomain' , for example 'model.addLinearExpressionInDomain(task.getStart(), Domain.fromIntervals(startIntervals))'  where start is of type 'IntVar'.

Dátum: pondelok 31. júla 2023, čas: 10:22:36 UTC+2, odosielateľ: roelof....@kineo.ai

[KR Prasath]

Hi I have a similar problem did you find any answers ? https://groups.google.com/g/or-tools-discuss/c/-aGuvghHSAQ/m/PJMW3GNZAwAJ