Re: [or-tools-discuss] One of several optional FixedDurationIntervalVar must be performed

[Laurent Perron]

Have a look at flexible_jobshop in the C++ example.

I recommend create a parallel boolean variable array from the performed expressions of all alternative interval variables.

And then use a MapDomain() constraint to link this array with a 'selected' integer variable.

As the 'selected' variable is an integer variable, it will force to have exactly 1 boolean variable set to true.

Bonus point, you can use these selected variables in you search strategies.

I hope this helps.

Le dim. 14 févr. 2016 à 19:16, Andres Collart <andres...@gmail.com> a écrit :

Hi,

I'm trying to model a multiple parallel machines problem with only certain availability periods (defined as "q in r"). I'm using FixedDurationIntervalVar objects created for each job, machine, and availability period and set them all to be optionally performed. However, I can't get it to say that at least one of them has to be performed. The second chunk of code below is what I thought would do that but it doesn't. How can I get that to work? Thanks in advance!

job_copies = {}

for j in jobs:

    for i in machines:

        for q in r:

            name = 'job %s copy %s %s'%(j,i,q)

            job_copy = solver.FixedDurationIntervalVar(sa[i,q],

                                                      99999,

                                                      p[j],

                                                      True,

                                                      name)

            job_copies[j,i,q] = job_copy

#Constrain for at least one copy to be used

for j in jobs:

    solver.Add(solver.SumEquality([job_copies[j,i,q].PerformedExpr() \

                for i in machines\

                for q in r],1))

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

[Andres Collart]

Hi Laurent,

Thanks for the info! I'd programmed it another way but the search is moving along slowly, I'll re-program it as you suggested and see if that helps.

Thanks again,

Andres

[clovis....@supplychainwizard.com]

Hi Laurent, 

I am very new to this tool and constraint programming.

I think I have the same problem as Andres. I am trying to implement P||Cmax: several machines and jobs, having the processing time of jobs can depending on the machines. That is why I created a matrix of processing time which is taking for each line x (of the matrix) the potential processing times of job x on the different machines. I want as Andres use only one of this "FixedDurationIntervalVar" in my final schedule, that is to say the one corresponding to the machine it has been scheduled on.

I am trying to implement your solution with Python but I found very few documentation about the method "MapDomain()" you mentioned, so I could not implement it so far. Also I did not see it in the job shop example.

Could you maybe share a piece of code where you used "MapDomain()" and a link to the "flexible jobshop" code example you mentioned?

Here is a part of my code (jobs are called 'WOs' and machines 'lines') for 2 machines and 4 jobs:

# processing time per job per line

   processingTime = [[2,1],

[1,1],

[4,2],

[1,1]]

# declaration of the number of WOs and lines

   totalDuration = 168

   numberOfWO = len(processingTime)

   numberOfLine = len(processingTime[0])

# definition of the line and WO set

   all_WOs = range(0, numberOfWO)

   all_lines = range(0, numberOfLine)

############################################ Variables

# A WO is defined as a duration interval

   WO = {}

   for j in all_WOs:

      for i in all_lines:

         WO[(j,i)] = solver.FixedDurationIntervalVar(0, totalDuration, processingTime[j][i], False, 'WO_{0}_{1}'.format(j, i))

   WOAssignment = {}

# if work order j is assigned to line i

   for j in all_WOs:

# X = [solver.BoolVar("x%i" % i) for i in range(N)]

         WOAssignment[j] = [solver.BoolVar('WO%d line%d' % (j, i)) for i in all_lines]

   all_sequences = []

   all_machines_jobs = []

############################################ constraints

# a job is scheduled on one and only one machine

   for j in all_WOs:

      solver.Add(solver.Sum(WOAssignment[j][i] for i in all_lines) == 1)

# link the boolean and the interval

   for j in all_WOs:

      solver.Add(WOAssignment[j].MapDomain(solver, WO[j, :]))

 

   for i in all_lines:

      machines_jobs = []

      for j in all_WOs:       

         machines_jobs.append(WO[(j, i)])

      disj = solver.DisjunctiveConstraint(machines_jobs, 'machine %i' % i)

      all_sequences.append(disj.SequenceVar())

      solver.Add(disj)

Thank you!

Clovis

[jeanfranco...@gmail.com]

Hi everybod,

I'm stuck with a pretty similar issue, here's the problem:

    - 2 machines (m1, m2): CNC gates (which translate themself along the horizontal axis, see the following sketch)
    - n jobs: n pieces which should be milled on the CNC
    - each job have to be executed either on m1 or m2, but not both. It also forbidden as well, that the two gates process the same piece simultaneously.
.
    - each piece have a specified length ()
 
    - The CNC gates share a limited space (L) together: it also induce the following constraint: 
      It meens for example, that in case of long pieces (l close to L), is it plausible that only one gate should work as the remaining length won't be sufficient to process another piece on the other side.

    - jobs completion times are the same either for m1 or m2

    - the obective would be to minimize the sum of inoccupation time of both gates.

    - I'm coding in Python

I tried the MapDomain method exposed above, but I'm still stuck.

@Clovis: did you finally find a solution to your problem? If yes, maybe could you share some tips?

@Laurent: I'm not used to CP programming at all. Could this problem even be solved with or-tools, as it appears to be symetrical (m1 could be switched with m2 and vice versa)?
Moreover, it would be nice if you could release a small sample using MapDomain.

Thank you in advance for your precious help!

Jeff  

[Laurent Perron]

Interesting, can you expand the constraint and show a solution?

Can you send me a small data set?

Do you want to stack pieces 2 by 2?

Can the separation between the two machines move as we proceed to the next pair of pieces?

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

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

[jeanfranco...@gmail.com]

Hi Laurent,

Thanks for your reply. I’m not sure what you meant about “expand the constraint”, but you will find some solutions + corresponding Gant charts in the pdf attached. The horizontal axis is the time and the vertical one represents the shared available length for M0 and M1 (in this example set to L = 10 units).

 

The little dataset (15 jobs) I used is the following:

 

[[, ], …

 

[[3, 3],

[2, 5],

[1, 3],

[3, 7],

[7, 3],

[2, 2],

[2, 2],

[5, 5],

[10, 2],

[4, 3],

[2, 6],

[1, 2],

[6, 8],

[4, 5],

[3, 7]]

 

Where represents the completion time of the job and its minimum required length on the CNC working area.

 

For the moment, I assumed that all jobs are available at t=0 and that there is no constraint on the end time (EndMax = horizon).

 

To establish these simple examples, I proceeded this way:

-          One random sequence is generated (ex.: Sol. 2)

-          I took the first piece (T5) and attributed it to M0

-          I take the second piece (T7) and place it at the most left free space. Here is M1 empty (8 units length are left), so I can attributeT7 to M1.

-          For the third piece (T10) however, it’s too long to be processed directly after T5 (T10 require 6 length free units, as only 5 are available once T5 is achieved). We also have to wait until T7 is completed. Then we can attribute T10 to M0 (or M1 as well).

-          And so on…

 

For Sol. 2, it appears that the gates are inactive during 15 time units. For Sol. 3, only 5 units, and for Sol. 3’, simply by pushing T5 to the end, we achieve something pretty optimal, as only 1 time unit is wasted.

 

Intuitively, I would propose that minimizing the inactive working time is equivalent to minimizing the total makespan. One optimal lower bound should also be something like .

 

So I want to stack the pieces 2 by 2, as you mentioned, but without waiting that both jobs are completed to start processing a new pair of pieces. Instead, as soon as one job is achieved on one gate, we carry on with another job which fits the remaining place, even if the other gate is still working (there is no physical separation between the two gates, they’re free to translate on rails. We just want to avoid them to collide :) )

I hope my explanations are clear so far.

 

For the moment in implemented the cumulative constraint over length with something like this:

solver.AddConstraint(solver.Cumulative(all_tasks_flat, all_lengths_flat, length_capacity, "cumul_length"))

 

I guess I can do the same for the gates and consider them as a cumulative constraint:

solver.AddConstraint(solver.Cumulative(all_tasks_flat, all_number_machine_flat, tot_number_machines, "number machine"))

where all_number_machine_flat  would be a list of int equal to 1 (each job require 1 gate)

and tot_number_machines will be the domain [0..2].

 

(By the way, I don’t get AddConstraint/Cumulative to work with dictionaries as arguments. Should the dictionaries necessarily be flattened in lists?)

 

I declared a list of FixedDurationInterval for each job on each machine. Where I’m stuck at, is how to set a job on “unperformed” as soon as it is already processed on one gate.

Thnak you!

[Laurent Perron]

Hi, 

I have pushed examples/python/gate_scheduling_sat.py which solves your problem with our new sat based CP solver.

I reproduce the code in this mail:

  # Creates the solver.

  model = cp_model.CpModel()

  jobs = [[3, 3],

          [2, 5],

          [1, 3],

          [3, 7],

          [7, 3],

          [2, 2],

          [2, 2],

          [5, 5],

          [10, 2],

          [4, 3],

          [2, 6],

          [1, 2],

          [6, 8],

          [4, 5],

          [3, 7]]

  max_length = 10

  horizon = sum(t[0] for t in jobs)

  all_jobs = range(len(jobs))

  intervals = []

  intervals0 = []

  intervals1 = []

  performed = []

  starts = []

  ends = []

  demands = []

  for i in all_jobs:

    start = model.NewIntVar(0, horizon, 'start_%i' % i)

    duration = jobs[i][0]

    end = model.NewIntVar(0, horizon, 'end_%i' % i)

    interval = model.NewIntervalVar(start, duration, end, 'interval_%i' % i)

    starts.append(start)

    intervals.append(interval)

    ends.append(end)

    demands.append(jobs[i][1])

    performed_on_m0 = model.NewBoolVar('perform_%i_on_m0' % i)

    performed.append(performed_on_m0)

    start0 = model.NewIntVar(0, horizon, 'start_%i_on_m0' % i)

    end0 = model.NewIntVar(0, horizon, 'end_%i_on_m0' % i)

    interval0 = model.NewOptionalIntervalVar(

        start0, duration, end0, performed_on_m0, 'interval_%i_on_m0' % i)

    intervals0.append(interval0)

    start1 = model.NewIntVar(0, horizon, 'start_%i_on_m1' % i)

    end1 = model.NewIntVar(0, horizon, 'end_%i_on_m1' % i)

    interval1 = model.NewOptionalIntervalVar(

        start1, duration, end1, performed_on_m0.Not(), 'interval_%i_on_m1' % i)

    intervals1.append(interval1)

    # We only propagate the constraint if the tasks is performed on the machine.

    model.Add(start0 == start).OnlyEnforceIf(performed_on_m0)

    model.Add(start1 == start).OnlyEnforceIf(performed_on_m0.Not())

  # Length constraint (modeled as a cumulative)

  model.AddCumulative(intervals, demands, max_length)

  # Choose which machine to perform the jobs on.

  model.AddNoOverlap(intervals0)

  model.AddNoOverlap(intervals1)

  # Objective variable.

  makespan = model.NewIntVar(0, horizon, 'makespan')

  model.AddMaxEquality(makespan, ends)

  model.Minimize(makespan)

  # Solve model.

  solver = cp_model.CpSolver()

  solver.Solve(model)

  print('Makespan = %i' % solver.ObjectiveValue())

  for i in all_jobs:

    performed_machine = 1 - solver.Value(performed[i])

    start = solver.Value(starts[i])

    print('Job %i starts at %i on machine %i' % (i, start, performed_machine))

On this small data set, this is solved trivially.

About the model, as we have a sat backend, we do have half-reified constraint (The OnlyEnforceIf() part).

They take as argument a boolean variable or its negation.

The rest is pretty straightforward.

I hope this helps.

Thanks

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

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

[jeanfranco...@gmail.com]

Hi,

Wow, awesome! That was quick, many thanks.

I'll take a look during the week. I'll soon get real/bigger data sets to perform on it too. I'll let you know.

Thank you!

[jeanfranco...@gmail.com]

Hi,

Sorry to bother.. Do you approximatively know when a update release including the new sat CP solver will occurs on pip repository? I definitely don't get the source to be built :(

[Laurent Perron]

November.

In the meantime, if you are on linux, you can can install docker and run make python in or-tools/tools/docker

It will create python modules in the export sub-directory.

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

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

[murat saglam]

Hi Laurent, 

I think there is a little mistake at https://developers.google.com/optimization/scheduling/job_shop

# Computes horizon.
  horizon = 0
  for i in all_machines:
    horizon += sum(processing_times[i])

should read:

# Computes horizon.
  horizon = 0
  for i in all_jobs:
    horizon += sum(processing_times[i])

[murat saglam]

Hi Laurent,

I'm trying to modify this jobshop (https://developers.google.com/optimization/scheduling/job_shop) to a flexible jobshop.

Could you give a python example on the usage of MapDomain() for the case you explained here?

Let's say we have two FixedDurationIntervalVars as for task A, for two possible machines:

t_a1=solver.FixedDurationIntervalVar(0,100,10,True,'task_A_on_machine_1') # I assume we need to keep the optional true

t_a2=solver.FixedDurationIntervalVar(0,100,10,True,'task_A_on_machine_2') # I assume we need to keep the optional true

and we have the following boolean variables:

b_a1=solver.BoolVar('boolean_Aon1')

b_a2=solver.BoolVar('boolean_Aon2')

How can we link them with MapDomain()?

Once we do that, how should we alter the search strategies given in  (https://developers.google.com/optimization/scheduling/job_shop)?

I could not simply make use of something like this: solver.Add(t_a1.PerformedExpr() + t_a2.PerformedExpr() == 1)

Thanks

[Paul Trow]

You're right - it should be for i in all_jobs, because the number of rows of the two arrays is all_jobs. Good catch - I'll fix it. (In this case it doesn't affect the outcome, because all_machines = all_jobs = 3.

[jeanfranco...@gmail.com]

Hi Laurent,

I finally got the python packages "pywrapsat" and "cp_model_pb2" to be built from the source. However I get the following error by running the file "gate_scheduling_sat.py":

Traceback (most recent call last):
  File "C:/.../PycharmProjects/test_CSP/gate_scheduling_sat.py", line 129, in <module>
    main()
  File "C:/.../PycharmProjects/test_CSP/gate_scheduling_sat.py", line 94, in main
    model.Add(start0 == start).OnlyEnforceIf(performed_on_m0)
  File "C:\...\AppData\Local\Programs\Python\Python36\lib\site-packages\ortools-6.5.4551-py3.6-win-amd64.egg\ortools\sat\python\cp_model.py", line 498, in Add
    coeffs_map, constant = ct.Expression().GetVarValueMap()
  File "C:\...\AppData\Local\Programs\Python\Python36\lib\site-packages\ortools-6.5.4551-py3.6-win-amd64.egg\ortools\sat\python\cp_model.py", line 131, in GetVarValueMap
    coeffs[expr] += coef
TypeError: unhashable type: 'IntVar'

Process finished with exit code 1


Any idea where this issue comes from?

Many thanks in advance.

[Laurent Perron]

Python 3 overloading of == :-(

Change to model.AddLinearConstraint([(start0, -1), (start, 1)], [0, 0]).OnlyEnforceIf(performed_on_m0)

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

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

[jeanfranco...@gmail.com]

Hi,

Many thanks!

By replacing the following parts:

# We only propagate the constraint if the tasks is performed on the machine.

# model.Add(start0 == start).OnlyEnforceIf(performed_on_m0)
# model.Add(start1 == start).OnlyEnforceIf(performed_on_m0.Not())
model.AddLinearConstraint([(start0, -1), (start, 1)], 0, 0).OnlyEnforceIf(performed_on_m0)
model.AddLinearConstraint([(start1, -1), (start, 1)], 0, 0).OnlyEnforceIf(performed_on_m0.Not())

and:

# Symmetry breaking.
# model.Add(performed[0] == 0)
zero_int = model.NewIntVar(0, 0, 'zero_int')
model.AddLinearConstraint([(performed[0], -1), (zero_int, 1)], 0, 0

it finally seems to work properly on the given little data set.

I'll now try this on bigger data sets + start/end constraints :)

[Laurent Perron]

Do not add the zero_int part.

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

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

[Jean-François Wegerich]

Ok, how will you proceed instead? I had the same as above error with the symmetry breaking:

model.Add(performed[0] == 0)

2017-10-23 12:42 GMT+02:00 'Laurent Perron' via or-tools-discuss <or-tools...@googlegroups.com>:

Do not add the zero_int part.

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

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

[Laurent Perron]

model.AddLinearConstraint([(performed[0], 1), 0, 0)

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

2017-10-23 13:29 GMT+02:00 Jean-François Wegerich <jeanfranco...@gmail.com>:

Ok, how will you proceed instead? I had the same as above error with the symmetry breaking:

model.Add(performed[0] == 0)

[Jean-François Wegerich]

Great! Thank you.

2017-10-23 13:34 GMT+02:00 'Laurent Perron' via or-tools-discuss <or-tools...@googlegroups.com>:

model.AddLinearConstraint([(performed[0], 1), 0, 0)

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