Scheduling with sequence dependent setup times and machine unavailability

[ciam...@gmail.com]

Hello everyone,

I am modeling a flexible job shop scheduling problem with CP-SAT. I have sequence-dependent setup times between operations assigned to the same machine.

Usually, I would model these setup times using circuit constraints, for example:

start_next >= end_previous + setup_time[previous][next]

However, in my case the setup is an actual activity performed by an operator. Operators are available only during specific working shifts, so the setup cannot simply be a passive delay between two operations. It must be scheduled explicitly in a time interval where the operator is available.

For example, if operation B follows operation A on a machine and the setup time from A to B is 30 minutes, those 30 minutes must take place during an operator availability window. If the machine finishes A just before the end of a shift, the setup should not be allowed to continue during the unavailable period.

What is the best modeling approach in CP-SAT for this case?

Any advice or small example would be greatly appreciated.

Thank you!

[Priidik Vilumaa]

Hi

Cool problem. Perhaps something like this would work

Assuming that operation B always requires a setup performed by an operator and just the time value is different depending on the preceding task. 

1) model the setup as a task

2) noOverlap the person (i.e. that person can only do 1 setup at a time)

3) noOverlap the setup task with the machine tasks as well, since probably setup can't be complete unless the machine is stopped and empty

4) setup_end <= task_start

5) setup_duration == setup_time[prev][next]

6) block out operator unavailability windows with dummy tasks or just play with the start end variable domains

Best,

Priidik

[Laurent Perron]

I would attach 1 optional setup_interval per task, starting at the end of the task (or ending at the start of the task), and use the literals of the circuit to set the end of that setup tasks, and its performed literal.

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

--
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 visit https://groups.google.com/d/msgid/or-tools-discuss/67dc710d-ea51-491f-b946-477a5116d720n%40googlegroups.com.

[ciam...@gmail.com]

Thank you both for your helpful answers!

I will try to follow this modeling approach.

Thanks again!

[grego...@gmail.com]

You didn’t specified size of a problem and whether an operator for an operation is known before or calculated. Circuit constraint is very heavy approach that should be used only when really needed.

Is it possible to exclude time outside shifts and use compressed shift time? 

Jan