Scheduling on unidentical parallel machines

[Jeremy Karouta]

Hello,

I'm doing an internship project in which I should test the possibility of using Constraint Programming to solve a scheduling problem. I have read the first few chapters of the manual and browsed through the rest (mainly the job-shop chapter and the TSP chapter).

What I want to accomplish is to make a tool that schedules an orderlist such that the total makespan is minimized. All orders can be manufactured on all machines, however not all machines have same speed, this means an order does not have a fixed duration. Moreover I will need to implement change-over times between different orders (machines need to be set up between each order), which i'm disregarding for now, just to get something working. Also, I am working in C# because this is a language the company can continue to maintain. Lastly I do not have a lot of background in programming, and I am learning C# for this project, so excuse me if I do not use right terminology.

I checked the discussion group, but I only found unfinished threads or inclomplete/unsatisfactory answers

for example: https://groups.google.com/d/topic/or-tools-discuss/ZLhIVQAkIao/discussion

First idea was to use IntervalVar's like in the job-shop example. However because the orders don't have a fixed duration, I could not come up with a way of working with this. Then I could try to make a routing problem out of it, which I haven't looked at yet, because I want to make the program as generic as possible and understandable for the Software Engineers without knowledge about CP, who will need to take over my project after i finish my internship goal. 

So I wanted to stick to IntVars and link them all together using constraints. However I am stuck now, because I actually need dynamic constraints, which i dont seem to get working.

First let me introduce the variables I have declared:

I have defined a struct "Order" containing:

public string OrderNumber;

public string ProductNumber;

public int Quantity;

public IntVar Start_Time;

public IntVar On_Line;

public IntVar CurrentCapacity;

public IntVar Duration;

public IntVar End_Time;

Then I save in a List<Order> all the orders for which i define the IntVars each named with the OrderNumber.

Two of the problems I am now having:

1. Link duration of an order to Machine

So I need a constraint to link the duration of an order to the machine its on. I've got a list of capacities [prod/hour] of all machines.

What I thought would be a good idea is the following:

solver.Add( OrderList[i].CurrentCapacity == lines.MLineList[OrderList[i].On_Line - 1].Capacity );

- First I probably need to use solver.MakeEquality because that the right side of the equation is an integer and not an IntVar;

- Secondly this doesn't work because I cannot use an Intvar (OrderList[i].On_Line) as an index.

Does anyone have an idea on how to make this working?

2. No two orders simultaneous on same machine

So then I also need to constrain to orders from happening at the same time on a single machine. I thought of several ways of doing this however anyway I would need a conditional constraint looking about the following:

This would loop for all orders i and for orders j = i+1 and up

solver.Add( !( (OrderList[i].Start_Time <= OrderList[j].End_Time) && (OrderList[j].Start_Time <= OrderList[i].End_Time) ) )

meaning no two orders can overlap. However this should only apply if the solver chose to put the two orders on the same machine, so:

solver.Add( (OrderList[i].On_Line == OrderList[j].On_Line) == !( (OrderList[i].Start_Time <= OrderList[j].End_Time) && (OrderList[j].Start_Time <= OrderList[i].End_Time) ) )

 

meaning when two jobs are on the same line, this should imply that those two orders do not overlap.

- Firstly, solver.Add() apparently cannot coop with the &&, || and ! logical operators.

- Secondly, what I want to do is say if the first expression is true, it should imply the second expression. in the current syntax also the opposite holds => so if the first expression is false, the second should also be, which I don't want. I only want this constraint to hold if the first expression is true. However adding == true to the first expression, gives an error saying it cannot compare IntVarExpr (if i remember correctly) to a bool. 

Help on this is appreciated, also the PC I am programming on is not connected to the internet, because I don't have rights at the company for my own laptop. So if I need to copy anything for you from my current code this will probably be a bit of a hazard, but surely not impossible.

Also I'm starting to think translating the problem to a routing problem is the best bet, however I would like to see if this is also possible.

Thanks!

Jeremy

[Alessandro Zanarini]

Hi Jeremy,

my suggestion would be to have a closer look at the flexible_jobshop.cc example. There you should find most of the answers. Shortly a possible solution is:

- for dealing with multiple machines, you create one optional task (IntervalVar) for each machine. All this tasks are constrained so that one and only one is actually executed. Since you have one task per machine you can have the duration depending on that.

- for dealing with non-overlapping tasks, have a look at the disjunctive constraint.

- for change-over time, have a look at transition times in the disjunctive constraint itself.

I hope this helps,

Alessandro

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

[Jeremy Karouta]

Hello Alessandro,

First of all, thanks for a reaction.

Secondly I cannot find flexible_jobshop.cc anywhere (looked on the manual, and in the latest revision of the tutorial folder: http://or-tools.googlecode.com/svn/trunk/documentation/tutorials/cplusplus/chap6/ )

I have taken a good look at the normal "jobshop.cc" and actually I started with that and tried to convert my data to fit this, however this didn't succed because of what I mentioned earlier.

Also maybe this wasn't clear earlier: Each order only needs to be processed by one machine, so it's not a real job-shop problem. Yes I can link the two together, however this unidentical machine thing makes it hard for me to see through I guess.

Then I cannot quite understand what you mean in your first point. Yes I can convert the capacity of a machine [products/time] to speed [time/prod] and yes, I can get a small enough order of magnitude of time such that making an integer will not make me loose this that much information (going down to ms/product will cause me about 0.1% loss). But your second sentence confuses me, and I'm not sure what you mean. Could you elaborate?

About the two other points, I could use the disjunctive constraints only if I have IntervalVars, which I don't (yet) because of this NON-fixed duration problem I'm facing.

regards,

Jeremy

Op woensdag 19 maart 2014 22:43:04 UTC+8 schreef Alessandro Zanarini:

[Laurent Perron]

You should look at ortools/examples/cpp/README and the examples in this directory.

Thanks

[Jeremy Karouta]

Hi guys,

Thanks a lot so far! I have something working now! I'm currently checking if my solution makes any sense given my input, after which I will start to add other constraints.

So, what I did was actually copying the flexible_jobshop.cc, translating it to c# and modifying it to fit my model. And it works! I just had a few questions that arose while translating:

• On line 114 of flexible_jobshop.cc the method solver.MakeMapDomain() is used. What does this do? I could only understand that this constraint makes sure that at least 1 task-alternative is still carried out, however how?
  
• On line 144 of flexible_jobshop.cc the method IntExpr.Bound() is used. Also I understand this would return true whenever the variable is bound, but what does bound mean in this case? Because all variables have a lower and an upper bound, yet they are all added to the list is it not?
  
• Last point: on line 228 of flexible_jobshop.cc the method collector->ForwardSequence() is used. I guess this is to retreive the "solved" sequences from the solution collector? Anyways, I cannot find any method alike in the C# library. So currently I'm retreiving all the information I can from the IntervalVars, however I think I will need some information from the SequenceVars as well.
  

Kind regards,

Jeremy

Op donderdag 20 maart 2014 19:39:37 UTC+8 schreef Laurent Perron:

[Alessandro Zanarini]

Hi,

- MakeMapDomain maps one discrete variable domain to an array of boolean variables. Ex:

V = [0..3] A = [0..1, 0..1, 0..1, 0..1]

V = i <=> A[i] = 1

In the flexible jobshop the boolean variables in A are the performed variables related to each task alternative. When V is assigned to a value you basically say which alternative is actually performed and the corresponding performed variables are assigned as a consequence.

- Bound() is true if the lower bound of the variable is equal to the upper bound. In other words, it is true iff the variable or expression is actually assigned to a single value. In the specific example, all_alternative_variables contains all the variables that require to be bound in order to find an assignment of tasks to machines. In line 144, it is basically asking whether for a specific task I have alternative machines; if yes, then I should add to the variable list that needs to be searched upon.

- In C# you can use the SequenceVar.Next(int) method to find similar information. Assume that the SequenceVar is defined for a machine defined over N tasks (of which some may be performed, some may not be performed).

Just be careful that: 

* SequenceVar.Next(0) = k tells which is the first IntervalVar (task) to be performed (in this case IntervalVar k - 1)

* SequenceVar.Next(i)  = k tells that IntervalVar k - 1 is performed after IntervalVar i - 1 

* SequenceVar.Next(i) = i tells that IntervalVar i-1 is NOT performed

* SequenceVar.Next(i) = N + 1 tells that IntervalVar i - 1 is the last to be performed in this machine.

I hope this helps.

Best,

Alessandro

[Jeremy Karouta]

Hi and thanks for the information, this clears up a lot!

Again however, I get stuck. Namely while trying to retrieve the variables from the solver.

Firstly I used the if(solver.Solve(...)){...} way of calling the solver.

I could find the values of the "Alternative Variables" using solution.Value(OrderList[order_id].AlternativeVariable), and such know which order was scheduled on which machine. (solution = collector.Solution(0), and I use a LastSolutionCollector)

However, the solution does not have any method which accepts a SequenceVar, so I cannot read any information in the current solution about the sequences. Then I thought I might look into the IntervalVar's, this should be possible using solution.DurationValue(OrderList[order_id].intervals[LINE]) (or Start- and EndValue), wehere LINE is the value of the alternative variable.

However each time I try to get this information, my program crashes (I think it's something to do with an invalid memory call, caused by LINE).

Also I could not find a way to access the SequenceVar.Next() method.

Anyway, I read in the manual in section 2.4.2, that using solver.Solve(), you cannot access the variables of the current solution, but with NewSearch, NextSolution and EndSearch you can. So I decided to try that, such that I won't need the solution.Value() method. So I tested this:

[...]

solver.NewSearch(main_phase, search_log,objective_monitor,limit);

while(solver.NextSolution()){[..1..]}

// Check values in IntervalVars and SequenceVars

[..2..]

solver.EndSearch();

Now only in place [..1..] I can obtain the current values of the variables not in [..2..], however I only want the LAST solution (with the best objective value), so I would like to obtain them only in [..2..]. I also tried to add a single solver.NextSolution() outside the while, but this doesn't help as the time_limit has already finished (at least that's what I guess is happening after testing a bit).

The actual question: (above is a bit of context and stuff):

So I guess my actual question is how to use the SequenceVar.Next() method only for the last solution, in a not so devious way.

Thanks for your time!

Jeremy

Op woensdag 26 maart 2014 17:18:11 UTC+8 schreef Alessandro Zanarini:

[Jeremy Karouta]

Hi,

One more question:

I was trying to come up with an alternative "smart" solution: I wanted to check the time after each search, and somehow using the timelimit know when the it is the last solution, then I could keep everything in the while(solver.NextSolution()) loop, where I can reach the variables.

However after a bit of testing, it came to my attention that sometimes the last solution is over the time limit, and sometimes under. So any help on how this time limit works would also be appreciated.

Thanks,

Jeremy

Op vrijdag 28 maart 2014 15:20:08 UTC+8 schreef Jeremy Karouta:

[Alessandro Zanarini]

Hi Jeremy,

SequenceVar.Next(int) returns an IntVar.

I have not tried, but you should be able to access the value of such solution by doing something like this:

solution.Value(seq.Next(0));

I hope this helps

Best,

Alessandro

[Laurent Perron]

Beware, there is a difference of 1 between the next and the interval.
next(0) points to the first interval.

so if next[0] = 3, this means that the first interval is the 3rd (and not the 4th).

Thanks

[Jeremy Karouta]

Hey guys, thanks a lot for all the time you take for me.

When I saw your post I thought that I was dumd not to have tried this, however I actually did (just remembered when trying it again), but in the end didn't mention it.

So when I try it, I get the following error:

System.AccessViolationException : Attempted to read or write protected memory. This is often an indication that other memory is corrupt.

This error is induced by the WriteLine command in the bellow code (I hope I added all the important bits of code):

SolutionCollector collector = solver.MakeLastSolutionCollector();

[...]

if (solver.Solve(...,collector)){

Assignment solution = collector.Solution(0);

for (int line_id = 0; line_id < Line_Count; ++line_id){

SequenceVar seq = all_sequences[line_id];

Console.WriteLine("{0}: {1}", seq.Name(), solution.Value(seq.Next(0)).ToString() );

}

}

Moreover when i try to write seq.Next(0).Value() NUnit crashes completely with a BEX64 "Problem Event Name", which I have found to be mostly caused by a bad memory access (I got the same crashes when I was trying to read instance N (instead of N-1) of a N-size list).

By the way, when I try ToString() instead of Value() I get Line_0_nexts0(1..30) and it doesn't crash, but then again, this is not the variable from the collector.

Hopefully you can help me again!

Thanks, Jeremy

Op vrijdag 28 maart 2014 23:07:04 UTC+8 schreef Laurent Perron:

[Alessandro Zanarini]

Hi Jeremy,

I get the same error. When using solution collectors you have to add the variables that you are going to retrieve after the solve.

I *think* collector.Add(SequenceVar) works together with Assignment.ForwardSequence that however is not exposed to C# through SWIG.

Now, the Assignment.Value(IntVar) works iff the corresponding IntVar has been added to the solution collector... so the easiest work around is the following (in pseudo-code):

SolutionCollector collector = ...

SequenceVar seq = ...

for (int i = 0; i < seq.Size() + 1; i++)

  collector.Add(seq.Next(i));

I hope this helps

Best,

Alessandro

[Jeremy Karouta]

Understandable, thanks for looking into it!

I'll try it tomorrow.

Jeremy

--

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

--
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/3KCbccqVWjs/unsubscribe.
To unsubscribe from this group and all its topics, send an email to or-tools-discu...@googlegroups.com.

[Jeremy Karouta]

Hi Guys,

It has been some time now, because I've been working on different aspects of the project. Just wanted to mention in the first place that the Scheduler works (at least what I have implemented so far), and I even made a nice visualizer to show a Gantt chart of the come-up schedule using SVG. Thanks for all the help so far!

So now I just started working on adding constraints to my program, the first one being adding the change-over times, and I ran into new problems:

Alessandro mentioned:

- for change-over time, have a look at transition times in the disjunctive constraint itself.

So When I try to use the SetTransitionTime() method on a disjunctive constraint, I need to input a LongResultCallback2 transit_evaluator. Unfortunately I could not find any information about this in the manual, and trying to dig deeper in the definitions did not make it any clearer either. So I cannot figure out just how I should be using this.

A second option I swiftly considered was the Dependency Graph explained in 6.3.5 of the manual. Anyways I cannot use the methods as explained in the manual because they probably are not to pushed to the C# library yet (?). However if I understand correctly, this constraint is used to imply a certain scheduled order. Using the same example as in the manual, if I add 

graph->AddStartsAfterEndWithDelay(jobs_to_tasks[2][0],jobs_to_tasks[1][0], 1);

this would mean I will never get a schedule where job 2 precedes job 1. Am I correct?

If I am correct, this dependency graph isn't what I need anyway:

Maybe it wasn't so clear before, but for my problem different pairs of orders have different switching times. Changing from 1 -> 2 will always cost the same time as 2 -> 1, but a 1-2 transition will (most probably) cost a different amount of time than a 1-3 transition. So every pair of IntervalVar in a SequenceVar should have their own transition time.
Unless this is possible using the transition times of the disjunctive constraint, I guess I will need to come up with another solution, probably meaning using extra, optional, IntervalVars for each transition.

Does anyone have any ideas as how to tackle this?

Jeremy

Op maandag 31 maart 2014 21:49:37 UTC+8 schreef Jeremy Karouta:

Understandable, thanks for looking into it!

I'll try it tomorrow.

Jeremy

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.

--
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/3KCbccqVWjs/unsubscribe.

To unsubscribe from this group and all its topics, send an email to or-tools-discuss+unsubscribe@googlegroups.com.

[Lukas Hollenstein]

Hi Jeremy,

I have a very similar problem as what you describe: jobs that need to be scheduled on production lines, not in a specific order but with transition times on the line that depend on the job and the previous job on that line.

Did you find a way how to implement this in the meantime?

Thanks,

Lukas

[Jeremy Karouta]

Hi Lukas,

After my internship period was over, I still didn't have a working CP algorithm, and I finished by using a heuristic. The time it took to solve the entire problem I had in CP was way too long. Probably, my constraints were not very well implemented either.

If you want to give CP a try, my suggestion would be to try to implement it as a TSP (as explained in the user manual and examples). I didn't, but I think that it would be more readable and maybe more efficiently programmed.

I'm sorry I can't really help you anymore. Good luck with it, and if you have any specific questions, the OR-tools team/community responds quite fast (at least one year ago they did :) )

Kind regards,

Jeremy

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.

--
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/3KCbccqVWjs/unsubscribe.

To unsubscribe from this group and all its topics, send an email to or-tools-discu...@googlegroups.com.

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

--
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/3KCbccqVWjs/unsubscribe.

To unsubscribe from this group and all its topics, send an email to or-tools-discu...@googlegroups.com.

[Lukas Hollenstein]

Thanks for your suggestions, Jeremy.

Best,

Lukas

Lukas

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.

--
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/3KCbccqVWjs/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.