FlexibleJobShop with Machine Calendars

[davidesempri...@gmail.com]

Hi All,

I'm new in OR-TOOLS, my goal is to implement Flexible Job Shop Problem with Machine Calendars. I define for all my machine a list of Exceptions like this:

// Machine calendar

MachineException[] machine_exceptions = {

  // Machine 1 - Shift from 8-12 and 14-18

  // Mon

  new MachineException(){ Start = 0, Duration = 8, Machine = 1},

  new MachineException(){ Start = 12, Duration = 2, Machine = 1},

  new MachineException(){ Start = 18, Duration = 6, Machine = 1},

  ...

  // Sat

  new MachineException(){ Start = 0+120, Duration = 24, Machine = 1},

  // Sun

  new MachineException(){ Start = 0+144, Duration = 24, Machine = 1},

     

  // Machine 2 - Shift from 8-12 e 14-18

  // Mon

  new MachineException(){ Start = 0, Duration = 8, Machine = 2},

  new MachineException(){ Start = 12, Duration = 2, Machine = 2},

  new MachineException(){ Start = 18, Duration = 6, Machine = 2},

  ...

  // Sat

  new MachineException(){ Start = 0+120, Duration = 24, Machine = 2},

  // Sun

  new MachineException(){ Start = 0+144, Duration = 24, Machine = 2},

};

this draw when the machine is not available ...

I use disjunctive constraints to tell OR-TOOLS to not allocate TASK during exception machine slot

foreach (MachineException m in machine_exceptions)

{

  m.Interval = solver.MakeFixedInterval(m.Start, m.Duration, string.Format("Machine_{0} off", m.Machine - 1));

}

Dictionary<int, SequenceVar> all_machines_calendars = new Dictionary<int, SequenceVar>();

for (int machine_id = 0; machine_id < machines_to_tasks.Count(); ++machine_id)

{

  List<IntervalVar> calendar = machines_to_tasks[machine_id];

  calendar.AddRange(machine_exceptions.Where(rsv => rsv.Machine == machine_id + 1).Select(rsv => rsv.Interval));

  string dsjName = String.Format("Machine_{0} calendar", machine_id);

  DisjunctiveConstraint disj = solver.MakeDisjunctiveConstraint(calendar.ToArray(), dsjName);

  all_machines_calendars[machine_id] = disj.SequenceVar();

  solver.Add(disj);

}

// add the sequence

all_sequences.Concat<SequenceVar>(all_machines_calendars.Values);

Finally I obtain a model where the tasks of jobs are allocated (the gray bar is the machine off slot)

but this is not enought ..... because my goal is to allocate the task when there are also a partial slot available (see FIRST task OF Job_2) , break it and continue the task later when the shift restart ...

This is possibile using disjunction constraint ? How to do that?

The result attended is shown below

Can anyone really help me to make this stuff in a simple way (I'm not using SAT)?

Thank you REALLY so much

Davide

[Laurent Perron]

If you have a disjunctive constraint, you need a variable duration interval var.

Then you precompute the duration of task w.r.t. the start of the task (account for overlap).

Additionally, you restrict the possible start times of the interval.

--Laurent

PS: I would really use the SAT solver :-)

--
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.

[davidesempri...@gmail.com]

Hi Laurent,

first thank you for your quick reply. I found a old thread where you expose your idea to precompute the duration taking in account overlap

>>>>>>>>>>>>>>>>

let's take an example

task : start between 0 and 10, duration = 5

break between 2 and 4, and 6 and 7.

so duration is [8, 8, -1, -1, 6, 6, -1, 5, 5, 5]

I use -1 to forbid this as a starting point.

>>>>>>>>>>>>>>>>

Ok, I understand your idea BUT I'm not able to text C# code to implement this stuff ....

I create the IntervalVar with this method:

        int duration; 

IntervalVar interval = solver.MakeFixedDurationIntervalVar(start, horizon, duration, optional, name);

How I can create the IntervalVar with variable duration like you suggest me? What method should I use? (some snippet C# available?)

 

second stuff, you wrote:

>>>>>>>>

Additionally, you restrict the possible start times of the interval.

>>>>>>>>

Can you explain me better this?

Regards

Davide

 

 

[Laurent Perron]

Instead of creating a full interval for the start time, fill in the possible start values (outside the breaks).

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

--

[davidesempri...@gmail.com]

Hi Laurent,

I have some doubt about like you suggest; If I have a TASK duration in seconds, should I precompute for each TASK (I can have a thousand of it) the Whole day from 0 to 86400 seconds possible intervals? ... multiply for 2 weeks ... huge numbers of intervals to compute, you don't think so?

Question: using SAT what I have to do, IT CAN BE more easy and smart to do? With SAT I can get the same result attended (flexible job shop with machine alternative and calendars)? Do you have and C# sample?

Thnak you so much

Davide

[Laurent Perron]

I do not believe that planning tasks in seconds over two weeks will lead to (a) reasonable sized problems, and (b) are robust solutions.

How do you know that the duration of the tasks will not change over 2 weeks? That to 1 second glitch will invalid your plan?

Considering the code, I am adding code samples here:

  https://github.com/google/or-tools/blob/master/ortools/sat/doc/index.md

I will write an example of flexible scheduling soon.

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

--

[Davide Semprini]

Hi Laurent,

I don't have task duration of few seconds, but consider this example: shift 1: from 08:00 AM to 12:00 AM; shift 2: from 02:00 PM to 06 PM

I have a Task duration of 65 minutes; I have to precompute a task duration and so I have to put at work a model that consider the start time cross all possible minutes ... the array will be:

Start Time  Duration

08:00 AM    65

08:01 AM    65

08:02 AM    65 

...

10:55 AM    65

10:56 AM    185

10:57 AM    185

10:58 AM    185  

10:59 AM    185 

11:00 AM    185 

02:00 PM    65

02:01 PM    65

too much intervals to compute? Consider also a case where the task duration is more that 4 hour and IS NEVER allocable ... suggestions (should be breakable ... )?

I'm waiting for your example

Very thank you

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 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.

[Laurent Perron]

Now, if you can predict the maximum number of times a task will be split (at most 1 time), you can always create 2 intervals, constraint the second one to be after the first one.

See https://www.slideshare.net/PhilippeLaborie/conditional-interval-variables-a-powerful-concept-for-modeling-and-solving-complex-scheduling-problems  slide 20.

Then you add all these intervals + fixed interval for breaks in a no_overlap constraint.

The part that is still unclear is the continuity across breaks.

I need to think more about it.

Considering the 4 hour case, you need to preprocess your data.

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

Le lun. 23 juil. 2018 à 07:48, Davide Semprini <davidesempri...@gmail.com> a écrit :

Hi Laurent,

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 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 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.

[davidesempri...@gmail.com]

Hi Laurent,

do you have had the time to text the flexible job shop sample in c#?

thanks a lot in advance for your patience ... 

Davide

[Laurent Perron]

Not this week as I am on vacation :-)

[davidesempri...@gmail.com]

Hi Laurent,

ok, good vacation to u! :-)

before you suggest me to take a look at the predicate PresenceOf(t) => PresenceOf(t+1) to solve the problem when a task should be break due to calendars constraint

you text:

See https://www.slideshare.net/PhilippeLaborie/conditional-interval-variables-a-powerful-concept-for-modeling-and-solving-complex-scheduling-problems  slide 20.

Question1: with ORTOOLS I'm able to implement the predicate PresenceOf()  suggest to me? I see that this is fully available on IBM CPLEX

Question2: my goal is also to constrait the presence of the next fraction to be allocated on same machine. It can be done? and so PresenceOf(t) => PresenceOf(t+1) constrained to the machine choosen for t (t+1 should be present on the same machine)

Thank you

Davide Semprini

[Laurent Perron]

When you create an optional interval, you directly create a predicate for the presence.

Now PresenceOf(t) => PresenceOf(t+1) is just an implication between these two pre-existing predicates.

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

[davidesempri...@gmail.com]

Hi Laurent,

why you are talking about "optional interval"?

In my case they are not Optional, my goal is to obtain a break of a task during calendar machine off (and as I understood the tecnique is to fractioning the interval in two (N) subinterval in "strick" sequence )

In the slide ... they refer conditional interval 

They should be performed both ....

Regards

Davide

[Laurent Perron]

After some thinking 

here is what I would do:

1) use the CP-SAT solver (we need half reified constraint)

2) for each activity, compute the maximum number of sub-splits

I assume we are planning over days with breaks on a week-end

an activity of duration 3 has at most 2 sub-activities

an activity of duration 6 has exactly 2 subactivities

an activity of duration 8 has between 2 and 3 subactivities

3) create the sub-activities, the initial ones are non optional, the final ones may be optional

4) force breaks to happen on the week-ends

If act has 2 subs (sub0 and sub1, sub1 optional, this corresponds to the first case above)

sub1 implies end0 is on a friday  // easy to do with half reified unary literal constraint.

sub1 implies start1 is end0 + 3 // next monday

not(sub1) implies duration1 is 0

sub1 implies sub0  // to break symmetries on the splitting.

5) manage total duration

duration0 + duration1 == act_duration

This works well if the breaks are regular.

If the breaks are irregular, you need to explore the sub1 implies start1 is end0 + 3 constraint into

sub1 and end0 is just before break0 implies start0 is just after break0

sub1 and end0 is just before break1 implies start0 is just after break1

I hope this helps.

...

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

[Laurent Perron]

I meant explode in the last paragraph.

One nice feature of this model is that it is easy to constraint each sub-task to have a minimum duration (such that you do not work for 1 minute on a task before a break :-) ).

[davidesempri...@gmail.com]

Hi Laurent,

very thank you for your reply. The real model could be more complicated cause each day we can have different also shifts and so I think tha precompute the numbers of intervals can be very hard to do.

think about a global calendar where for instance Christmas day come on Wednesday only this year ... 

My goal is to produce a real scheduling for 2 weeks horizon considering different shift for each resource, whole days off 

I need time to think about your solution if really can help me

Thank you to much

Davide

[Laurent Perron]

So, 

back to the initial method

Let's get a granularity 1 time unit = 1 day, scheduling over 3 weeks, with week-end, and 1 day off (Thu of the second week)

My task has a duration of 4

total duration =  ( I use X to indicate impossible)

M T W T F S S M T W T F S S M T W T F S S

4 4 6 6 6 X X 5 7 7 X 6 X X 4 4 X X X X X

I have duration = 4 when start in [0..1] U [14..15]

I have duration = 5 when start in [7..7]

I have duration = 6 when start in [2..4] U [11..11]

I have duration = 7 when start in [8..9]

I have duration = X when start in [5..6] U [10..10] U [12..13] U [16..20]

And the domain of start is [0..4] U [7..9] U [11..11] U [14..15] (complement of X)

Now I can create my interval variables  (in python for the example)

# Create variables

start = model.NewEnumeratedIntVar([0, 4, 7, 9, 11, 11, 14, 15], 'start')

duration = model.NewIntVar(4, 7, 'duration')

end = model.NewIntVar(0, 20, 'end')  # We can compute it exactly.

# Create indicators

d4 = model.NewBoolVar('d4')

d5 = model.NewBoolVar('d5')

d6 = model.NewBoolVar('d6')

d7 = model.NewBoolVar('d7')

# Link start to indicators

model.AddLinearConstraintWithBounds([(start, 1)], [0, 1, 14, 15]).OnlyEnforceIf(d4)

model.Add(start == 7).OnlyEnforceIf(d5)

model.AddLinearConstraintWithBounds([(start, 1)], [2, 4, 11, 11]).OnlyEnforceIf(d6)

model.AddLinearConstraintWithBounds([(start, 1)], [8, 9]).OnlyEnforceIf(d7)

# Exactly one indicator is true

model.Add(d4 + d5 + d6 + d7  == 1)

# Indicators constraint the duration

model.Add(duration == 4).OnlyEnforceIf(d4)

model.Add(duration == 5).OnlyEnforceIf(d5)
model.Add(duration == 6).OnlyEnforceIf(d6)
model.Add(duration == 7).OnlyEnforceIf(d7)

This way, you are completely flexible.

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

[Ankit Jain]

Hello,

Currently, I am working on the Job Shop Scheduling Problem with the resource calendar. I found your solution shared (link) to be relevant to my scenario.

The problem I am having is :

1) Not able to get a generalized solution to automatically compute the all possible scenarios with time duration

2) There are Many Jobs like 500 nos & each job have approx 5 task

3) There are approx 50 machines/resources on which it will be routed.

4) Some resources have more than 1 Capacity.

I am very new to Python & google-or-tool. Please suggest some way out to incorporate the above problems in my model. Sharing of any idea/ reference/ solution is highly appreciated.

Thanks in advance.

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

[Andrey Sinitsyn]

Hi Laurent,

I checked your solution, but unfortunately in ortools 7.3/7.4 we don't have AddLinearConstraintWithBounds method in the CpModel class. Was it changed to AddLinearExpressionInDomain?

Thanks

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

[Laurent Perron]

yes

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

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/59f88dbd-471a-491e-826f-1e00d30d5d38%40googlegroups.com.

[Mayank Mahajan]

Hello @laurent, @david,

```

List<IntervalVar> calendar = machines_to_tasks[machine_id];

  calendar.AddRange(machine_exceptions.Where(rsv => rsv.Machine == machine_id + 1).Select(rsv => rsv.Interval));

  string dsjName = String.Format("Machine_{0} calendar", machine_id);

  DisjunctiveConstraint disj = solver.MakeDisjunctiveConstraint(calendar.ToArray(), dsjName);

  all_machines_calendars[machine_id] = disj.SequenceVar();

  solver.Add(disj);

}

// add the sequence

all_sequences.Concat<SequenceVar>(all_machines_calendars.Values);

```

I am not able to understand how to create a list of intervalvars as below you have called addrange method on it.. (it means it is not a simple list).

Please help, i am stuck here.

[Mayank Mahajan]

my sample goes like this:

m_exceptions = [
{"start": 0, "duration": 8, "machine": 1},
{"start": 12, "duration": 2, "machine": 1},
{"start": 18, "duration": 6, "machine": 1},

{"start": 0 + 24, "duration": 8, "machine": 1},
{"start": 12 + 24, "duration": 2, "machine": 1},
{"start": 18 + 24, "duration": 6, "machine": 1},

{"start": 0 + 24 + 24, "duration": 8, "machine": 1},
{"start": 12 + 24 + 24, "duration": 2, "machine": 1},
{"start": 18 + 24 + 24, "duration": 6, "machine": 1},

{"start": 0 + 24 + 24 + 24, "duration": 8, "machine": 1},
{"start": 12 + 24 + 24 + 24, "duration": 2, "machine": 1},
{"start": 18 + 24 + 24 + 24, "duration": 6, "machine": 1},

{"start": 0 + 24 + 24 + 24 + 24, "duration": 8, "machine": 1},
{"start": 12 + 24 + 24 + 24 + 24, "duration": 2, "machine": 1},
{"start": 18 + 24 + 24 + 24 + 24, "duration": 6, "machine": 1},

{"start": 0 + 120, "duration": 24, "machine": 1},

{"start": 0 + 144, "duration": 24, "machine": 1},

{"start": 0, "duration": 8, "machine": 2},
{"start": 12, "duration": 2, "machine": 2},
{"start": 18, "duration": 6, "machine": 2},

{"start": 0 + 24, "duration": 8, "machine": 2},
{"start": 12 + 24, "duration": 2, "machine": 2},
{"start": 18 + 24, "duration": 6, "machine": 2},

{"start": 0 + 24 + 24, "duration": 8, "machine": 2},
{"start": 12 + 24 + 24, "duration": 2, "machine": 2},
{"start": 18 + 24 + 24, "duration": 6, "machine": 2},

{"start": 0 + 24 + 24 + 24, "duration": 8, "machine": 2},
{"start": 12 + 24 + 24 + 24, "duration": 2, "machine": 2},
{"start": 18 + 24 + 24 + 24, "duration": 6, "machine": 2},

{"start": 0 + 24 + 24 + 24 + 24, "duration": 8, "machine": 2},
{"start": 12 + 24 + 24 + 24 + 24, "duration": 2, "machine": 2},
{"start": 18 + 24 + 24 + 24 + 24, "duration": 6, "machine": 2},

{"start": 0 + 120, "duration": 24, "machine": 2},

{"start": 0 + 144, "duration": 24, "machine": 2}
]

for exceptions in m_exceptions:
    exceptions['interval_var'] = model.NewFixedSizeIntervalVar(exceptions['start'], exceptions['duration'], "machine_off_" + str(exceptions['machine']))

# disjunctive contraints

for machine in all_machines:
    model.AddNoOverlap(machine_to_intervals[machine])

#another disjunctive constraint for calendar need to be added. I can definitly merge two loops if required. for simplicity tried seperate loops

calendars = []
for machine in all_machines:
    calendars.append(machine_to_intervals[machine])

#Now calendars is just a list so `AddRange` method is unaavailable.

Please help

[Wirattawut Boonbandansook]

Can you demonstrate how one can create interval variables with variable/flexible 'durations' in Python please?

[Nicolas Cheron]

the NewIntervalVar function is able to get as duration a intValue and also an IntVar.

So you can have "duration = 5" and also "duration = model.NewIntVar(5,horizon,"duration")" 

[KR Prasath]

Did you find any solution for this?