Flexible Job Shop with additional restrictions

[Lukas Hollenstein]

Hi

I'm looking into solving a flexible job shop scheduling problem with or-tool. Since I'm kind of new to mathematical optimization I have a few questions before I get going:

1. I have 2 tasks per job and up to possible 3 machines per operation. The processing times don't vary much. How many jobs can I expect to schedule in, say, 1h on a normal desktop PC?
2. I glanecd at the C++ examples "flexible_jobshop" and "jobshop_sat" and understand that the first one uses the constraint solver and the second one the SAT. What is the difference? Could anyone point me to some reference please?
3. I'd like to use C# rather than C++. Does anyone have a C# version of those examples or similar ones? And would there be a reason not to use C# and stick to C++?

Thank you very much in advance!

Regards,

Lukas

[Driss Lahlou]

Hi Lukas,

I glanecd at the C++ examples "flexible_jobshop" and "jobshop_sat" and understand that the first one uses the constraint solver and the second one the SAT. What is the difference? Could anyone point me to some reference please?

 

You can check this link and this one for a basic introduction about constraint_programming, and the wiki page for SAT.

I'd like to use C# rather than C++. Does anyone have a C# version of those examples or similar ones? And would there be a reason not to use C# and stick to C++?

 

Or-tools  is mainly written in C++, and provides wrappers for other languages using SWIG, so for example, when you declare a DecisionBuilder in C#, SWIG will create a DecisionBuilder in C++, and several communications will happen between C++ and C# during the resolution. It's true that we're trying to minimize the amount of the back-and-forth SWIG calls by implementing some cache mechanisms, but the best choice is to use C++ directly, because it doesn't use SWIG at all, which guarantees a better performance. 

You can check TaskScheduling.cc example to see how you can solve the job shop problem using constraint solver in C#.

I hope this helps.

Regards, 

 

Thank you very much in advance!

Regards,

Lukas

--
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-discuss+unsubscribe@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

--

driss

[Lukas Hollenstein]

Hi Driss,

Thanks for the links and hints. I looked at the TaskScheduling.cs example and I think I can build up from there. Only, I don't understand where the rpecedence constraints come in that make sure that the successor of a task really is processed after that task. In the jobshop.cc example on line 99 there is

solver.MakeIntervalVarRelation(t2, Solver::STARTS_AFTER_END, t1);

which is exactly that, isn't it?

Another question: In my problem, there are changeover times between some tasks, depending on some properties of the tasks and machines. Can you hint on how to implement such constraints?

Thanks so much, best, Lukas

Hi Lukas,

To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.

For more options, visit https://groups.google.com/d/optout.

--

driss

[Driss Lahlou]

Hello Lukas,

Sorry for my late reply.

I created a job shop example in C# with the precedence constraint. Let us know if you need anything else.

Regards.

To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discuss+unsubscribe@googlegroups.com.

For more options, visit https://groups.google.com/d/optout.

--

driss

[Lukas Hollenstein]

Hi Driss,

Thank you very much! Don't worry, I got stuck in another project anyway. Soon I'll be looking into this again and then I'm sure this will help a lot =)

Regards, Lukas

--
You received this message because you are subscribed to a topic in the Google Groups "or-tools-discuss" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/or-tools-discuss/mlxVrMQtcHM/unsubscribe.
To unsubscribe from this group and all its topics, send an email to or-tools-discuss+unsubscribe@googlegroups.com.

For more options, visit https://groups.google.com/d/optout.

--

Lukas Hollenstein
mobile: +41 78 870 66 22
home: +41 43 537 72 82
Malojaweg 1, 8048 Zürich, Switzerland

[Lukas Hollenstein]

Hi

Ok, finally back to this... Your example works fine, thanks. A quick question:

In the solution, some task have StartMin==StartMax and some have StartMin < StartMax. Does it mean that there's no sinlge optimal schedule? Would I have to add more constraints or a secondary objective to narrow the bounds down?

Thanks, Lukas
 

On Thursday, October 20, 2016 at 8:47:02 AM UTC+2, Lukas Hollenstein wrote:

Hi Driss,

Thank you very much! Don't worry, I got stuck in another project anyway. Soon I'll be looking into this again and then I'm sure this will help a lot =)

Regards, Lukas

[Driss Lahlou]

It means that the tasks with StartMin < StartMax may start at any time between StartMin and StartMax with no impact on the objective value.

Regards,

[Phil Barber]

I am facing the same problem that Lukas also asked about earlier:

Another question: In my problem, there are changeover times between some tasks, depending on some properties of the tasks and machines. Can you hint on how to implement such constraints?

In my case, tasks use tools. If the previous task on a machine uses a different tool to the current task then there must be a changeover time added.

I am thinking that a solution would be something along the lines of below but am unsure how to implement it:

for machine in machines:

    if previous_job.tool != current_job.tool:   # unsure how to access these

         changeover = IntVar(changeover_time, ... )

         # add changeover to sequence on machine, placed between prev_job and cur_job

I am aware that this requires knowing what the previous and current jobs are before knowing what the changeover is. It is this that is making me question how feasible this is. 

Is something like this possible, and if so is this the approach?

Written in python based of this example if that makes a difference.

Cheers

[Laurent Perron]

This is implemented in C++ in the examples/cpp/jobshop_sat.cc

Here is the idea:

for one disjunctive constraint, 

Set of node: 1 node per task + 1 extra node.

Create a dense graph + self looping arc for each optional task (and not the extra node).

Add a circuit constraint on this graph with one literal per arc.

For each literal 'lit' on the arc task_i -> task_j

lit implies start(task_j) >= end(task_i) + transition_time

lit implies task_i performed

lit implies task_j performed

(to be verified in the jobshop_sat.cc for completeness).

The idea is that you create a matrix of literal such that

literal[i][j] is true iff task_j is the immediate successor of task_i

From this, you can encode transition times, transition costs easily.

--Laurent

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

--

[Phil Barber]

So here  is the part you're talking about and I'm trying to translate this into python: Apologies in advance for how little I understand here... Going to spell this out in case it helps anyone else in the future.

On the CpModel I would call AddCircuit with a list of acs where an arc = (source_node, destination_node, literal)

I'm struggling to find documentation on CircuitConstraintProto to be able to map what's happening here. 

I think what is going on is addTail addHead addLiteral is the equivalent of one of the tuples in the python above.

So the steps are: 

1. connect beginning = IntVar(0,0) to end = IntVar(i+1, i+1) with IntVar(0, 1) as the literal - Is this essentially a BoolVar?

2. connect end to beginning 

3. connect all jobs on the machine with literal =  IntVar(0,1)

4. add_conditional_precedence_with_offset I don't know how to recreate this in python

Thank you for your help on this! 

[Laurent Perron]

add_conditional_precedence_with_offset(before, after, lit, offset)

in python:

model.Add(after >= before + offset).OnlyEnforceIf(lit)

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

[Phil Barber]

You make it look so easy!

Thanks Laurent :)