scheduling jobshop with alternative resource

[wonsuk.choi]

Hello
Thank you for the google or-tools discussion group.

I am testing examples, to solve classical job shop scheduling problem,
which allows an operation to be processed by any machine from a given
set (so called, alternative resource)

The operation processing time depends on the allocated machine.
The problem is to assign each operation to machine, and to order the
operations
such that the maximal completion time of all operations is minimized.

Here is my coding concept. (not a correct syntax)
If there is any other way of implementing alternative resource,
please give me an advise.
Thank you for your help.

--------------------------------------------------------------------------------------------------------
IntervalVar operation1; // operation 1
IntervalVar operation2; // operation 2

IntervarVarList machineset; // machine group
machineset.add(machine1); // member 1
machineset.add(machine2); // member 2
machineset.add(machine3); // member 3

operation1 <= any of machineset; // assign any machine (constraint)
operation2 <= any of machineset; // assign any machine (constraint)

solver.Add(opertion2,StartsAfterEnd(operation1)) // precedence
relation
--------------------------------------------------------------------------------------------------------

[Laurent Perron]

Please have a look at python/simple_meeting.py

Basically, duplicates all intervals on all alternative resources, with optional = true.

Maintain them in sync, and force one to be active, usually with a map domain constraint.

Thanks

--Laurent

Laurent Perron |

Operations Research Team Lead |

lpe...@google.com |

(33) 1 42 68 53 00

[Laurent Perron]

Hello,

I have pushed a simplification to simple_meeting.py.

There is a new relation type between 2 intervals using the BinaryIntervalRelation: STAYS_IN_SYNC, which comes in handy here.

--Laurent

Laurent Perron |

Operations Research Team Lead |

lpe...@google.com |

(33) 1 42 68 53 00

[wonsuk.choi]

Hello
I got the solution about this problem by virtue of your help
Here is my java code.
-------------------------------------------------------------------------------------
IntVar[] presence = new IntVar[machineset.size()];
IntVar selection = solver.makeIntVar(0, machineset.size()-1];

for(int i = 0; i < machineset.size(); i++)
{
presence[i] = solver.makeBoolVar("presence of member " + i);
IntervalVar member = machineset.get(i);

solver.addConstraint(
solver.makeIntervalVarReleation(master,
solver.START_AT_START, member));

solver.addConstraint(
solver.makeEquality(
presence[i].Var(),
member.PerformedExpr().Var));
}
solver.addConstraint(
solver.makeSumEquality(presence, 1));
sover.addConstraint(
solver.makeMapDomain(selection, presence));
---------------------------------------------------------------------------------------
because each member's duration time is different,
I could not use the new relation StaysInSync.

I have got the same objective value (makespan) as legacy system.
In case of 5 jobs, 10 machines, 14 operations,
It takes only 47ms to complete, :-)
but when I doubled the job number to 10, it took long time.

I think I have to make my own DecisionBuilder for the faster search.
I will keep trying to study or-tools to understand the idea.
Thanks.

Best regards
wonsuk choi

[Laurent Perron]

I think you can simplify a bit the model

for(int i = 0; i < machineset.size(); i++)
{

   IntervalVar member = machineset.get(i);
   presence[i] = member.PerformedExpr().Var();

   presence[i].setName("presence of member " + i);

   solver.addConstraint(
       solver.makeIntervalVarReleation(master,
                 solver.START_AT_START, member));

}

Thanks

--Laurent

Laurent Perron |

Operations Research Team Lead |

lpe...@google.com |

(33) 1 42 68 53 00