Flexible job shop problem in python

[Johnson Liu]

Hi, everyone.

    I tried to construct a flexible job shop problem and modify the Job shop example on the website.

Separate into two solve stages. The first stage is used to decide the task is processed on which machine. 

And all tasks are available to be processed on these three machines.  Each task is limited to be processed on only one machine.

Then, in order to find out the minimum makespan, I calculate the minimum makespan of all the possible task-machine combination. 

However, It takes too much time on finding these small scenario (i.e. 3 jobs and 3 alternative machine). 

Is there any flexible job shop problem coded in python as reference?

 

python code is as attachment.

[Laurent Perron]

I have pushed the examples using the CP-SAT solver here:

https://github.com/google/or-tools/blob/master/examples/python/flexible_job_shop_sat.py

Here is the output:

Horizon = 40
Solution 0, time = 0.014938 s, objective = 37
Solution 1, time = 0.016141 s, objective = 33
Solution 2, time = 0.017196 s, objective = 31
Solution 3, time = 0.018241 s, objective = 30
Solution 4, time = 0.019283 s, objective = 28
Solution 5, time = 0.020361 s, objective = 25
Solution 6, time = 0.021402 s, objective = 21
Solution 7, time = 0.022440 s, objective = 20
Solution 8, time = 0.023765 s, objective = 19
Solution 9, time = 0.025001 s, objective = 18
Solution 10, time = 0.026289 s, objective = 16
Solution 11, time = 0.027439 s, objective = 15
Solution 12, time = 0.028587 s, objective = 13
Solution 13, time = 0.029757 s, objective = 12
Solution 14, time = 0.031078 s, objective = 10
Solution 15, time = 0.032183 s, objective = 9
Solution 16, time = 0.033416 s, objective = 8
Solution 17, time = 0.034481 s, objective = 7
Solution 18, time = 0.035662 s, objective = 6
Job 0:
  task_0_0 starts at 1 (alt 1, machine 1, duration 1)
  task_0_1 starts at 3 (alt 0, machine 0, duration 2)
  task_0_2 starts at 5 (alt 2, machine 2, duration 1)
Job 1:
  task_1_0 starts at 0 (alt 0, machine 0, duration 2)
  task_1_1 starts at 2 (alt 0, machine 0, duration 1)
  task_1_2 starts at 3 (alt 1, machine 1, duration 1)
Job 2:
  task_2_0 starts at 0 (alt 1, machine 1, duration 1)
  task_2_1 starts at 1 (alt 2, machine 2, duration 4)
  task_2_2 starts at 5 (alt 1, machine 1, duration 1)
Solve status: OPTIMAL
Optimal objective value: 6
Statistics
  - conflicts : 19
  - branches : 1331
  - wall time : 0.023905 s

I guess optimization does work :-) (0.02s)

Please note that you need to compile or-tools from sources, as a I pushed a small fix. The fix should be in v6.8 that will happen soon.

PS: Note the discrepancy between the solution time and the final time is because the solver measure the solving time, while the python measure solving + building the model.

Thanks

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

[Johnson Liu]

Dear Laurent,

Thanks for the example. After compiling or-tools from sources, it works perfectly.

[Jan Fischer]

Hello Laurent,

Thanks for the example. After compiling or-tools from sources, there is still an error if a task has no alternative. 

In Line 129 the function NewConstant is not defined.

https://github.com/google/or-tools/blob/master/examples/python/flexible_job_shop_sat.py#L129

Best regards,

Jan 

[Laurent Perron]

Just replace model.MakeConstant(1) by model.IntVar(1, 1, '')

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

[Jan Fischer]

the line presences[(job_id, task_id, 0)] = model.NewIntVar(1, 1, "") did the job

by the way i'm trying to add constraints, which limits the machine utilization for each machine to a speicif value and a balanced utilization over all machines. Do you have any recommandation to me. 

My first thoughts were to sum up the durations for each machine with each task, but i stuck at finden the right variables and constraintns. than you in advance 

Jan 

[Laurent Perron]

For each machine, sum (presence[i] * duration[i] for all tasks on that machine)

I would use 3 linear equations:

\ .     /

 \__/

and a max of 0, and the 2 below threshold penalty, and above threshold penalty.

--Laurent

[Johnson Liu]

Dear Laurent,

Now I have another question about SAT solver in python. Is it possible to give the rank for Interval variable (NewOptionalIntervalVar) or NewIntVar like start time in SAT solver?

Since I would like to use the order of  ' NewOptionalIntervalVar ' to define the order of another variable object.

Just like the user's manual 6.3.1.3. SequenceVars and 6.3.1.4. Ranked IntervalVars. 

Looking forward to your reply. Thanks~ 

[Laurent Perron]

There are two ways of doing that.

First way, look at ortools/sat/cp_model_expand.cc

for each pair of intervals i, j

create a boolean variable s_i_j if i is before j

link that to the two interval presence literals and start times (see AddReifiedPrecedence).

Once you have all these

rank(i) = sum over j != i (s_j_i)

Second way, implemented in examples/cpp/jobshop_sat.cc

see: https://github.com/google/or-tools/blob/c65b13763090d220db8efedb8664d1c69cd66edb/examples/cpp/jobshop_sat.cc#L371

Create a circuit constraint, for each pair of interval i, j, create a literal is j is the direct successor of i. Link these literals with the start as done in the jobshop examples.

And now use these literals (0 is an extra source node in the circuit constraint)

Literal 0 -> (i + 1) is true => rank(i) == 1

literal (i + 1) -> (j + 1) is true => rank(j) = rank(i) + 1

You are reimplementing the path cumul constraint in the traditional CP solver.

I do not know which one is better.

Thanks

--

[Johnson Liu]

Dear Laurent,

I have tried to sort interval by your first suggestion. And I encounter some problem that BoundIntegerExpression does not support sum function. Attachment is my python code for sorting interval and take one alternative machine as example (machine 0). Since I would like to use the order of interval for each machine, then I can add set up time between each interval if some condition satisfy. Thanks~   

[Laurent Perron]

It has to be a bit more complex than that.

The following code:

https://github.com/google/or-tools/blob/master/ortools/sat/samples/ranking_sample.py

Outputs the correct ranking:

Optimal cost: -3

Makespan: 6

Task 0 starts at 3 with rank 1

Task 1 starts at 4 with rank 2

Task 2 starts at 0 with rank 0

Task 3 in not performed and ranked at -1

I hope this helps.

Le mer. 25 juil. 2018 à 20:53, Johnson Liu <d206...@gmail.com> a écrit :

Dear Laurent,

I have tried to sort interval by your first suggestion. And I encounter some problem that BoundIntegerExpression does not support sum function. Attachment is my python code for sorting interval and take one alternative machine as example (machine 0). Since I would like to use the order of interval for each machine, then I can add set up time between each interval if some condition satisfy. Thanks~   

[Johnson Liu]

Dear Laurent,

    I have tried to use the RankTasks function in ranking_sample and to fulfill the reduction of resource change. (Resource change must take specific setup time, so I wanna lower the counts of change resource) I want to complete this target by minimize the multi-objective value. (makespan + cost time * penalty) However, it takes couple of hours to find out solution which attain my goal. Is there any suggestion on tuning the code and the performance? Or can I run or-tools SAT solver parallelly? 

Cost_Out = []

for machine_id in all_machines:

    STARTS = All_Info_DF[All_Info_DF['MACHINE'] == machine_id]['START'].values.tolist()

    PRESENCES = All_Info_DF[All_Info_DF['MACHINE'] == machine_id]['PRESENCE'].values.tolist()

    ranks = All_Info_DF[All_Info_DF['MACHINE'] == machine_id]['RANK'].values.tolist()

    Resource = All_Info_DF[All_Info_DF['MACHINE'] == machine_id]['Resource_id'].values.tolist()

   

    # Add ranking constraint.

    RankTasks(model, STARTS, PRESENCES, ranks)

    

    Cost = []

    for k in range(len(STARTS)):

        Cost.append(model.NewIntVar(0, len(STARTS) - 1, 'Cost_%i_%i' %(machine_id,k)))

    

    follows = {}

    for i in range(len(STARTS)):

        for j in range(len(STARTS)):

            if i == j:

                follows[(i,j)] = 0

            elif ranks[i] != -1:

                prec = model.NewBoolVar('%i follows %i' % (j, i))

                model.Add((ranks[i]+1) == ranks[j]).OnlyEnforceIf(prec)

                model.Add((ranks[i]+1) != ranks[j]).OnlyEnforceIf(prec.Not())

                

                ### if precedence JOB's resource differenct from the previous then add cost 

                if Resource[i] != Resource[j]:

                    follows[(i,j)] = prec*1

                else :

                    follows[(i,j)] = prec*0

            ### if the task is not be performed then prec = 0

else :

                prec = model.NewBoolVar('%i follows %i' % (j, i))

                model.Add(ranks[i] != -1).OnlyEnforceIf(prec)

                model.Add(ranks[i] == -1).OnlyEnforceIf(prec.Not())

                follows[(i,j)] = prec

    for i in range(len(STARTS)):

        model.Add(Cost[i] == sum(follows[(j, i)] for j in range(len(STARTS))))

    Cost_Out.append(Cost)

#---------------------------------------------------------------------------------------------------

# objective setting

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

model.AddMaxEquality(makespan, job_ends)

cost = model.NewIntVar(0, num_jobs, 'cost')

model.Add(cost == (sum(Cost_Out[i]) for i in all_machines))

model.Minimize(makespan+cost*30)

[Stefan]

Thanks for the example. I try to adjust it to my problem I am trying to solve. How is it possible to add a constraint which allows either machine 1 OR machine 2 run at the same time?

[Laurent Perron]

Is this not exactly what alternatives are for ?

See flexible_job_shop_sat.py

--

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.

--

--Laurent

[Stefan]

When I run the example I will have this machine allocation:

What I am trying to do is to allow either machine 1 or machine 2 to run at the same time.

One solution:

[Laurent Perron]

OK, add all intervals on machine 1 + machine 2 to the same no_overlap.

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

[Stefan]

Thanks, I got it working for now by using:

    # Create machines constraints.
    intervals = intervals_per_resources[0]
    if len(intervals) > 1:
     model.AddNoOverlap(intervals)
     
    intervals = intervals_per_resources[1]
    for interv in  intervals_per_resources[2]:
     intervals.append(interv)
    if len(intervals) > 1:
     model.AddNoOverlap(intervals)
     

[Stefan]

Hi all,

How can one add a constraint which means "the task after should use the same machine as the task before"?  I appreciate your help.

Cheers!

Am Donnerstag, 31. Mai 2018 10:13:23 UTC+2 schrieb Johnson Liu:

[Laurent Perron]

AddImplication(presence_literal_of_task1_on_machine_1, presence_literal_of_task2_on_machine_1)

AddImplication(presence_literal_of_task1_on_machine_2, presence_literal_of_task2_on_machine_2)

...

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

--

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.

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/450fcc57-9990-4225-88b0-dc7d9e8b5497%40googlegroups.com.

[Laurent Perron]

Or even an equality between the two.

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

[Weihang Zhu]

I have a similar flexible job shop scheduling problem. The difference in my problem is I also need to assign our resources to the task to make it work. For example, I need to add two technician, one machine A and one machine B to work together on a task. What kind of constraint should I add? 

Also, I saw the visualization of the work schedule in the previous posts. Is there a plot library provided for plotting the schedule? 

Thank you,

On Wednesday, July 3, 2019 at 8:30:50 AM UTC-5, Laurent Perron wrote:

Or even an equality between the two.

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

Le mer. 3 juil. 2019 à 15:30, Laurent Perron <lpe...@google.com> a écrit :

AddImplication(presence_literal_of_task1_on_machine_1, presence_literal_of_task2_on_machine_1)

AddImplication(presence_literal_of_task1_on_machine_2, presence_literal_of_task2_on_machine_2)

...

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

Le mer. 3 juil. 2019 à 15:04, Stefan <stefan...@gmail.com> a écrit :

Hi all,

How can one add a constraint which means "the task after should use the same machine as the task before"?  I appreciate your help.

Cheers!

Am Donnerstag, 31. Mai 2018 10:13:23 UTC+2 schrieb Johnson Liu:

Hi, everyone.

    I tried to construct a flexible job shop problem and modify the Job shop example on the website.

Separate into two solve stages. The first stage is used to decide the task is processed on which machine. 

And all tasks are available to be processed on these three machines.  Each task is limited to be processed on only one machine.

Then, in order to find out the minimum makespan, I calculate the minimum makespan of all the possible task-machine combination. 

However, It takes too much time on finding these small scenario (i.e. 3 jobs and 3 alternative machine). 

Is there any flexible job shop problem coded in python as reference?

 

python code is as attachment.

--
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...@googlegroups.com.

[Laurent Perron]

You can use the same interval variables in multiple no_overlap/cumulative constraints.

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-discu...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/f122fc4b-8026-4565-ab09-62772ce844d5%40googlegroups.com.

[Weihang Zhu]

I used IBM DOCPlex before. It was very easy to implement precedence constraint and alternatives in Cplex. In OR-tools CP, I did not see similar functions. From the examples, it seems that we have handle these constraints with many lines of codes as explained in the flexible JSP example. Is this correct? I also do not see a schedule or result visualization tool in OR-tools. Or is there one I did not notice?

Thank you,

[Laurent Perron]

It is true, the interface is more verbose, and lower level. This is a design choice.

And there are plenty of visualization tools  for gantt chart. Why propose another one ?

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-discu...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/985e110f-246a-48a3-ba54-406c0e032015%40googlegroups.com.

[Weihang Zhu]

Hi Laurent,

Thank you for the information. I have implemented my problem and solved it in DOCPlex. Recently I have also tried to implement the same problem in OR-tools. But it seems to be running much slower. I found out what slows down the solver is the constraint that I want to make sure all tasks under the same event start at the same time. My Python code is attached. I have described the problem at the beginning of the Python file. Could you please help to see how I can improve the code? Thank you very much!

I am also pasting my problem description below:

>>>What is the known information in this problem ?

There are Events to be built by a few workers. For each event, there are a few 

tasks starting at the same time, each with the same duration as the event. Each worker has a cost. There 

is an overall deadline for the work to be completed on all the Events. Each 

event has a fixed duration.

>>>What are the decision variables or unknowns in this problem ?

The unknown is the point in time that each task will start, and 

which worker will be assigned to each task.

>>>What are the constraints on these variables ?

2. There are constraints that specify that each task must have workers assigned 

to it, that a worker can be assigned to only one task at a time and that a 

worker can be assigned only to tasks for which he has the skill. 

>>>What is the objective ?

The objective is to minimize the makespan.

[Laurent Perron]

I have not fixed the printing of the solution,  but if you remove unnecessary duplications, it proves optimality in 0.5s

def fjsp():

factor = 1 # for scale-up test

# how many Events

NbEvents = 10*factor

RangeEvents = range(NbEvents)

Deadline = 50*factor

# each event's duration (all tasks in the event have the same duraion in the event)

Durations = [2, 2, 2, 4, 4, 4, 6, 6, 6, 8]

Durations = Durations * factor

# worker name, skill (task name), skill level (or worker cost)

Skills = [("Joe","mechanic",9),

("Jac","mechanic",8),

("Jim","mechanic",9),

("Kay","electric",7),

("Ken","electric",6),

("Kim","electric",7),

("Leo","others",6),

("Len","others",5),

# ("Lim","others",5),

# ("May","others",5)

]

NbWorkers = len(Skills)

# Event requires [(Skill, # of workers for each skill)]

EReqS = [

(("electric", 1), ("mechanic", 2), ("others", 1)),

(("electric", 1), ("mechanic", 1)),

(("electric", 2), ("mechanic", 1)),

(("electric", 1), ("mechanic", 2)),

(("mechanic", 2), ("others", 1)),

(("electric", 2), ("others", 1)),

(("electric", 1), ("mechanic", 2)),

(("electric", 1), ("mechanic", 1)),

(("mechanic", 1), ("others", 2)),

(("electric", 1), ("mechanic", 2), ("others", 1)),

]

EReqS = EReqS * factor

"""

Start modeling

"""

# start the Constraint Programming model

fjsp = cp_model.CpModel()

# Global storage of variables.

intervals_per_resources = defaultdict(list)

starts = {} # indexed by (event id, task_name).

presences = {} # indexed by (event id, task_name, worker_name).

event_ends = []

for h in RangeEvents:

suffix_name = '_h%i' % h

start = fjsp.NewIntVar(0, Deadline, 'start' + suffix_name)

duration = fjsp.NewIntVar(Durations[h], Durations[h], 'duration' + suffix_name)

end = fjsp.NewIntVar(0, Deadline, 'end' + suffix_name)

# Store the start for the solution.

starts[h] = start

event_ends.append(end)

for es in EReqS[h]: # all tasks for the Events (all tasks in the event have the same duration in the event)

# Create main interval for the task. #es: ("mechanic", 2)

# create alternative intervals (every worker with the required skill es[0] is an alternative)

l_presences = []

# check Workers with that skill (task), look up in Skills

for s in Skills: # s: ("Joe","mechanic",9)

if s[1] == es[0]:

alt_suffix = '_h%i_%s_%s_%.2f' % (h, es[0], s[0], s[2])

l_presence = fjsp.NewBoolVar('presence' + alt_suffix)

l_interval = fjsp.NewOptionalIntervalVar(start, duration, end, l_presence,'interval' + alt_suffix)

l_presences.append(l_presence)

# Add the local interval to the right worker. # s: ("Joe","mechanic",9)

intervals_per_resources[s[0]].append(l_interval)

# Store the presences for the solution. (event, task/skill, worker name)

presences[(h, es[0], s[0])] = l_presence

# Select the required number of workers with presence variable.

fjsp.Add(sum(l_presences) == es[1]) # es[1]: # of workers needed from this skill group

# disjunctive constraints: each worker can only work on one task any time.

for w in Skills:

intervals = intervals_per_resources[w[0]]

#if w[0] == "Joe" : print(intervals)

if len(intervals) > 1:

fjsp.AddNoOverlap(intervals)

# minimize the overall completion date (makespan)

makespan = fjsp.NewIntVar(0, Deadline, 'makespan')

fjsp.AddMaxEquality(makespan, event_ends)

fjsp.Minimize(makespan)

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-discu...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/bc04b37f-11e6-4898-ac1e-78e2773b9485%40googlegroups.com.

[Laurent Perron]

And the full solution

"""

>>>What is the known information in this problem ?

There are Events to be built by a few workers. For each event, there are a few

tasks, each with the same duration as the event. Each worker has a cost. There

is an overall deadline for the work to be completed on all the Events. Each

event has a fixed duration.

>>>What are the decision variables or unknowns in this problem ?

The unknown is the point in time that each task will start, and

which worker will be assigned to each task.

>>>What are the constraints on these variables ?

2. There are constraints that specify that each task must have workers assigned

to it, that a worker can be assigned to only one task at a time and that a

worker can be assigned only to tasks for which he has some level of skill.

>>>What is the objective ?

The objective is to minimize the makespan.

"""

from __future__ import print_function

import collections

from ortools.sat.python import cp_model

class SolutionPrinter(cp_model.CpSolverSolutionCallback):

"""Print intermediate solutions."""

def __init__(self):

cp_model.CpSolverSolutionCallback.__init__(self)

self.__solution_count = 0

def on_solution_callback(self):

"""Called at each new solution."""

print('Solution %i, time = %f s, objective = %i' %

(self.__solution_count, self.WallTime(), self.ObjectiveValue()))

self.__solution_count += 1

intervals_per_resources = collections.defaultdict(list)

starts = {} # indexed by (event id, task_name).

presences = {} # indexed by (event id, task_name, worker_name).

event_ends = []

for h in RangeEvents:

suffix_name = '_h%i' % h

start = fjsp.NewIntVar(0, Deadline, 'start' + suffix_name)

duration = fjsp.NewIntVar(Durations[h], Durations[h], 'duration' + suffix_name)

end = fjsp.NewIntVar(0, Deadline, 'end' + suffix_name)

# Store the start for the solution.

starts[h] = start

event_ends.append(end)

for es in EReqS[h]: # all tasks for the Events (all tasks in the event have the same duraion in the event)

# Solve the model

print("\nSolving model (%i events, %i workers)...." % (NbEvents, NbWorkers))

# Solve model.

solver = cp_model.CpSolver()

solver.parameters.max_time_in_seconds = 60.0 # # Sets a time limit of 60 seconds

solver.parameters.log_search_progress = True

status = solver.Solve(fjsp)

print("--- done")

print('Solve status: %s' % solver.StatusName(status))

if(solver.StatusName(status) != "INFEASIBLE"):

makespan = solver.ObjectiveValue()

print('Optimal objective value: %i' % makespan)

worker_idx = {w[0] : i for i,w in enumerate(Skills)} # worker indexed with worker name

worker_tasks = collections.defaultdict(list)

worker_cost = [0] * NbWorkers # cost of each worker

worker_time = [0] * NbWorkers # work hours assigned to each worker

worker_util = [0] * NbWorkers # utilization of each worker

print("Event View Schedule:")

# Print final solution.

for h in RangeEvents:

start_value = solver.Value(starts[h])

duration = Durations[h]

print('Event %i: starts at %i for %i hours' % (h, start_value, duration))

for es in EReqS[h]:

worker = -1

for s in Skills:

if s[1] == es[0]:

if solver.BooleanValue(presences[(h, s[1], s[0])]):

duration = Durations[h]

worker = s[0]

task = s[1]

print(' worker %s, task %s' % (worker, task))

worker_tasks[worker].append((h, task, start_value, duration))

worker_cost[worker_idx[worker]] += s[2] * duration

worker_time[worker_idx[worker]] += duration

worker_util = [round(x * 100 / makespan, 2) for x in worker_time]

print("Worker View Schedule:")

for w in Skills:

print("Worker " + w[0] + "(" + str(worker_time[worker_idx[w[0]]]) + " hours; $" + str(worker_cost[worker_idx[w[0]]]) + ")")

for wt in worker_tasks[w[0]]:

print("Event", wt[0], wt[1], "start at", wt[2], "for", wt[3], "hours") # event, task, start, duration

print("worker cost ($):", worker_cost)

print("worker time (hour):", worker_time)

print("worker utilization (%):", worker_util)

print('Statistics')

print(' - conflicts : %i' % solver.NumConflicts())

print(' - branches : %i' % solver.NumBranches())

print(' - wall time : %f s' % solver.WallTime())

fjsp()

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

[Weihang Zhu]

Hi Laurent,

This is very helpful. Thank you for fixing this overnight! I tested with 10 events and 8 workers and it did solve to optimal at 0.45 seconds. Unfortunately, the performance drops quickly when the problem size grows. When I tested with 20 events and 8 workers, it cannot solve to optimal after 60 seconds. In the program, if you change factor to 2, you can test with 20 events. Is there any more potential to increase the optimization speed?

In the real world, we have thousands of events and hundreds of workers. I tested with 2000 events and 50 workers with my CPlex model which can solve to optimal in 53 minutes. 100 events x 10 workers was solved in 1.7 seconds. I was expecting OR-tools to be slower but did not know it is much slower. 

BTW, what tools do you use for visualization. I tried Plotly. I was able to plot Gantt chart with it but the trouble is I cannot easily add label to each box in the Gantt chart. 

if <span style="co

[Laurent Perron]

Here is a working version, please tell me if the optimal solution found are valid.

I have added some trivial lower computation (does not help), and some cumulative reasoning (helps a lot).

I prove the 100x10 in 0.12 s on my laptop.

"""

>>>What is the known information in this problem ?

There are Events to be built by a few workers. For each event, there are a few

tasks, each with the same duration as the event. Each worker has a cost. There

is an overall deadline for the work to be completed on all the Events. Each

event has a fixed duration.

>>>What are the decision variables or unknowns in this problem ?

The unknown is the point in time that each task will start, and

which worker will be assigned to each task.

>>>What are the constraints on these variables ?

2. There are constraints that specify that each task must have workers assigned

to it, that a worker can be assigned to only one task at a time and that a

worker can be assigned only to tasks for which he has some level of skill.

>>>What is the objective ?

The objective is to minimize the makespan.

"""

from __future__ import print_function

import collections

import math

from ortools.sat.python import cp_model

class SolutionPrinter(cp_model.CpSolverSolutionCallback):

"""Print intermediate solutions."""

def __init__(self):

cp_model.CpSolverSolutionCallback.__init__(self)

self.__solution_count = 0

def on_solution_callback(self):

"""Called at each new solution."""

print('Solution %i, time = %f s, objective = %i' %

(self.__solution_count, self.WallTime(), self.ObjectiveValue()))

self.__solution_count += 1

def fjsp():

factor = 10 # for scale-up test

# how many Events

NbEvents = 10*factor

RangeEvents = range(NbEvents)

Deadline = 50*factor

# each event's duration (all tasks in the event have the same duraion in the event)

Durations = [2, 2, 2, 4, 4, 4, 6, 6, 6, 8]

Durations = Durations * factor

# worker name, skill (task name), skill level (or worker cost)

Skills = [("Joe","mechanic",9),

("Jac","mechanic",8),

("Jim","mechanic",9),

("Kay","electric",7),

("Ken","electric",6),

("Kim","electric",7),

("Leo","others",6),

("Len","others",5),

("Lim","others",5),

("May","others",5)

]

NbWorkers = len(Skills)

# Event requires [(Skill, # of workers for each skill)]

EReqS = [

(("electric", 1), ("mechanic", 2), ("others", 1)),

(("electric", 1), ("mechanic", 1)),

(("electric", 2), ("mechanic", 1)),

(("electric", 1), ("mechanic", 2)),

(("mechanic", 2), ("others", 1)),

(("electric", 2), ("others", 1)),

(("electric", 1), ("mechanic", 2)),

(("electric", 1), ("mechanic", 1)),

(("mechanic", 1), ("others", 2)),

(("electric", 1), ("mechanic", 2), ("others", 1)),

]

EReqS = EReqS * factor

"""

Start modeling

"""

# start the Constraint Programming model

fjsp = cp_model.CpModel()

# Compute lower bound.

demands_per_task = collections.defaultdict(int)

workers_per_task = collections.defaultdict(int)

for skill in Skills:

workers_per_task[skill[1]] += 1

for h in RangeEvents:

duration = Durations[h]

for es in EReqS[h]:

demands_per_task[es[0]] += duration * es[1]

lower_bound = max(int(math.ceil(demand / workers_per_task[task]))

for task, demand in demands_per_task.items())

print("Lower bound =", lower_bound)

# Global storage of variables.

intervals_per_resources = collections.defaultdict(list)

starts = {} # indexed by (event id, task_name).

presences = {} # indexed by (event id, task_name, worker_name).

event_ends = []

cumulative_demands = collections.defaultdict(list)

cumulative_intervals = collections.defaultdict(list)

for h in RangeEvents:

suffix_name = '_h%i' % h

start = fjsp.NewIntVar(0, Deadline, 'start' + suffix_name)

duration = fjsp.NewIntVar(Durations[h], Durations[h], 'duration' + suffix_name)

end = fjsp.NewIntVar(0, Deadline, 'end' + suffix_name)

master = fjsp.NewIntervalVar(start, duration, end, '')

# Store the start for the solution.

starts[h] = start

event_ends.append(end)

for es in EReqS[h]: # all tasks for the Events (all tasks in the event have the same duraion in the event)

# Add to the cumulative lists.

cumulative_demands[es[0]].append(es[1])

cumulative_intervals[es[0]].append(master)

# Create main interval for the task. #es: ("mechanic", 2)

# create alternative intervals (every worker with the required skill es[0] is an alternative)

l_presences = []

# check Workers with that skill (task), look up in Skills

for s in Skills: # s: ("Joe","mechanic",9)

if s[1] == es[0]:

alt_suffix = '_h%i_%s_%s_%.2f' % (h, es[0], s[0], s[2])

l_presence = fjsp.NewBoolVar('presence' + alt_suffix)

l_interval = fjsp.NewOptionalIntervalVar(start, duration, end, l_presence,'interval' + alt_suffix)

l_presences.append(l_presence)

# Add the local interval to the right worker. # s: ("Joe","mechanic",9)

intervals_per_resources[s[0]].append(l_interval)

# Store the presences for the solution. (event, task/skill, worker name)

presences[(h, es[0], s[0])] = l_presence

# Select the required number of workers with presence variable.

fjsp.Add(sum(l_presences) == es[1]) # es[1]: # of workers needed from this skill group

# disjunctive constraints: each worker can only work on one task any time.

for w in Skills:

intervals = intervals_per_resources[w[0]]

#if w[0] == "Joe" : print(intervals)

if len(intervals) > 1:

fjsp.AddNoOverlap(intervals)

# cumulative constraints.

for task, capacity in workers_per_task.items():

fjsp.AddCumulative(cumulative_intervals[task], cumulative_demands[task], capacity)

# minimize the overall completion date (makespan)

makespan = fjsp.NewIntVar(lower_bound, Deadline, 'makespan')

fjsp.AddMaxEquality(makespan, event_ends)

fjsp.Minimize(makespan)

# Solve the model

print("\nSolving model (%i events, %i workers)...." % (NbEvents, NbWorkers))

# Solve model.

solver = cp_model.CpSolver()

# solver.parameters.max_time_in_seconds = 60.0 # # Sets a time limit of 60 seconds

solver.parameters.log_search_progress = True

solver.parameters.num_search_workers = 8

--

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.

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/e93d3dd9-7f34-4767-bac6-9102c561cd3d%40googlegroups.com.

[Weihang Zhu]

Hi Laurent,

You are awesome. That's an amazing speedup! May I ask why the cumulative constraints can help so much? I feel they are redundant. 

The other major parameter you changed is: solver.parameters.num_search_workers = 8. Does this mean parallel search? This helps a lot in computation speed too. 

I have tested this code further. What bothers me is: in some cases it computes very quickly while in other cases it is very slow. It sounds like hit or miss. My test code is attached. If you test 200 events x 20 workers, it takes 0.5 seconds. But if you test 200 events x 30 workers, it seems to be stuck and never solve to optimal. 

[Laurent Perron]

num_search_workers is indeed parallel search. 

The cumulative constraints actually break symmetries in a way.

Then the problems do actually become big and hard.

If or-tools does not prove optimality, does it find good solutions ?

 

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

--

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.

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/9bb769ff-831c-4874-b4bb-5f0cf9a740d7%40googlegroups.com.

[Weihang Zhu]

Hi Laurent,

At 200 events x 30 workers, the lower bound is 100. The search process is stuck at 154 forever and I decided to close Spyder to stop it from running. 

A few other test cases: 200 events x 50 workers, it solves to optimal in 6 seconds. 500 events x 50 workers: 29 seconds. 1000 events x 50 workers: 140 seconds. So it does have great performance in many cases. And why it is stuck in some cases is quite mysterious to me!

To compare with CPlex, when it works, this OR-tools runs faster than CPlex model (not using cumulative constraints). With 1000 events x 50 workers, it solves to optimal in 707 seconds. I don't know if this is a fair comparison as I don't know whether CPlex is using parallel search. The CPlex model is very stable in providing optimal solution (or perhaps it stops at near optimal solution?). For the case of 200 events x 30 workers, it stops in 16 seconds with 102 as the makespan while the lower bound is 100.  

[Laurent Perron]

Cplex uses all the cores by default. 

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

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/a8296c8e-5237-47f4-a175-34cb7b337e0c%40googlegroups.com.

[Weihang Zhu]

Hi Laurent,

I need to add a value and a due date for each event. For that, I want to change the objective function to maximize sum(value * earliness). Earliness is defined as due time - completion time. Could you please tell me how to define the objective? I attempted to define it as in line 214 in the attache file but it does not work. 

Thank you,

On Sunday, July 7, 2019 at 11:09:21 PM UTC-5, Laurent Perron wrote:

Cplex uses all the cores by default. 

Le lun. 8 juil. 2019 à 00:13, Weihang Zhu <humo...@gmail.com> a écrit :

Hi Laurent,

At 200 events x 30 workers, the lower bound is 100. The search process is stuck at 154 forever and I decided to close Spyder to stop it from running. 

A few other test cases: 200 events x 50 workers, it solves to optimal in 6 seconds. 500 events x 50 workers: 29 seconds. 1000 events x 50 workers: 140 seconds. So it does have great performance in many cases. And why it is stuck in some cases is quite mysterious to me!

To compare with CPlex, when it works, this OR-tools runs faster than CPlex model (not using cumulative constraints). With 1000 events x 50 workers, it solves to optimal in 707 seconds. I don't know if this is a fair comparison as I don't know whether CPlex is using parallel search. The CPlex model is very stable in providing optimal solution (or perhaps it stops at near optimal solution?). For the case of 200 events x 30 workers, it stops in 16 seconds with 102 as the makespan while the lower bound is 100.  

On Sunday, July 7, 2019 at 4:30:44 PM UTC-5, Laurent Perron wrote:

num_search_workers is indeed parallel search. 

The cumulative constraints actually break symmetries in a way.

Then the problems do actually become big and hard.

If or-tools does not prove optimality, does it find good solutions ?

--
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...@googlegroups.com.

[Laurent Perron]

https://github.com/google/or-tools/blob/stable/ortools/sat/doc/integer_arithmetic.md#earliness-tardiness-cost-function

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

Le mar. 9 juil. 2019 à 02:54, Weihang Zhu <humo...@gmail.com> a écrit :

Hi Laurent,

I need to add a value and a due date for each event. For that, I want to change the objective function to maximize sum(value * earliness). Earliness is defined as due time - completion time. Could you please tell me how to define the objective? I attempted to define it as in line 214 in the attache file but it does not work. 

Thank you,

On Sunday, July 7, 2019 at 11:09:21 PM UTC-5, Laurent Perron wrote:

Cplex uses all the cores by default. 

Le lun. 8 juil. 2019 à 00:13, Weihang Zhu <humo...@gmail.com> a écrit :

Hi Laurent,

At 200 events x 30 workers, the lower bound is 100. The search process is stuck at 154 forever and I decided to close Spyder to stop it from running. 

A few other test cases: 200 events x 50 workers, it solves to optimal in 6 seconds. 500 events x 50 workers: 29 seconds. 1000 events x 50 workers: 140 seconds. So it does have great performance in many cases. And why it is stuck in some cases is quite mysterious to me!

To compare with CPlex, when it works, this OR-tools runs faster than CPlex model (not using cumulative constraints). With 1000 events x 50 workers, it solves to optimal in 707 seconds. I don't know if this is a fair comparison as I don't know whether CPlex is using parallel search. The CPlex model is very stable in providing optimal solution (or perhaps it stops at near optimal solution?). For the case of 200 events x 30 workers, it stops in 16 seconds with 102 as the makespan while the lower bound is 100.  

On Sunday, July 7, 2019 at 4:30:44 PM UTC-5, Laurent Perron wrote:

num_search_workers is indeed parallel search. 

The cumulative constraints actually break symmetries in a way.

Then the problems do actually become big and hard.

If or-tools does not prove optimality, does it find good solutions ?

--
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...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/a8296c8e-5237-47f4-a175-34cb7b337e0c%40googlegroups.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.
To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/c4e81ba2-94d0-4a96-92ef-16d4c1c66eb7%40googlegroups.com.

[Weihang Zhu]

Hi Laurent,

Thank you for the pointer. I have implemented the objective function with method explained in the link but the model is now running very slowly. The code is attached. Is there any way to improve this code? The following is the way I define the objective:

    large_constant = 10000

    costs = []

    for h in RangeEvents:

        suffix_name = '_h%i' % (h)

        costs.append(fjsp.NewIntVar(0, large_constant, 'cost' + suffix_name))

        s1 = fjsp.NewIntVar(-large_constant, large_constant, 's1' + suffix_name)

        fjsp.Add(s1 == EValues[h]*(DueDates[h] - event_ends[h]))

        fjsp.AddMaxEquality(costs[h], [s1, 0])

    fjsp.Maximize(sum(costs))

[Laurent Perron]

I would minimize lateness, instead of maximizing earliness.

It should improve somehow.

To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/116cf07b-ac94-4933-87b2-7323a30f68bf%40googlegroups.com.

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

--

--Laurent

[Weihang Zhu]

Hi Laurent,

My objective is to make sure each event finishes before the due date and an event with higher value should be completed first. I do not think Minimize(lateness) serves my purpose.

In CPlex, I simply write down the objective like below and it can complete computation with nearly the same speed as before: 

fjsp.add(fjsp.maximize(fjsp.sum(EValues[h] * fjsp.max([0, DueDates[h] - fjsp.end_of(tasks[h])]) for h in RangeEvents)))

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/116cf07b-ac94-4933-87b2-7323a30f68bf%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

--

--Laurent

[Laurent Perron]

minimize Max(end_i - due_date_i, 0)

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-discu...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/6078b237-24b4-4dd5-a2f8-2b3f0d6261b2%40googlegroups.com.

[Weihang Zhu]

This objective will only make sure all the due dates are met, but will not give the high value event a higher priority in the schedule.

[Laurent Perron]

minimize Max(wi * (end_i - due_date_i), 0)

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

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/ee40555b-a98f-4a3d-9f53-16a7051d71a6%40googlegroups.com.

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

--

--Laurent

[Laurent Perron]

Let me rewind

1) Each event finishes before the due data -> is this a hard constraint ?  If yes, just limit the domains of the end vars.

2) minimize sum(weights_i * end_i) will make sure high priority tasks finishes first.

Am I missing something ?

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/CAPyyUTtWAPnBq-2ZrFq4HixhRxoGC2PjmXvXu2ZgCBkzU7tmSA%40mail.gmail.com.

[Weihang Zhu]

Hi Laurent,

Thank you for the suggestions. I implemented the way you recommended but it is still very slow. For 20 events x 10 workers, it is already taking forever to compute. This is how I define the objective function:

    large_constant = 100000

    costs = []

    for h in RangeEvents:

        suffix_name = '_h%i' % (h)

        costs.append(fjsp.NewIntVar(0, large_constant, 'cost' + suffix_name))

        fjsp.Add(costs[h] == Weights[h]*event_ends[h])

    fjsp.Minimize(sum(costs))

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

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/ee40555b-a98f-4a3d-9f53-16a7051d71a6%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

--

--Laurent

--
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...@googlegroups.com.

[Weihang Zhu]

I forgot to attach the full code in the last email. Here it is as attached. 

[Weihang Zhu]

Hi Laurent,

I still don't have a good way to accelerate the computation for this new objective function. Do you have advice on how to make it run faster? 

Thank you,

[Laurent Perron]

I know. Looking at it.

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-discu...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/bf3f171f-29dc-4bc5-9f20-9c871f22c84f%40googlegroups.com.

[Servet BİRLİK]

Hi Laurent,

I have a flexible job shop problem but with a few different things. Here is my problem.

If a piece (job) can't go next target (machine) to process, this piece can go a buffer area in order to free that machine for other pieces to come. This is because of processing times are very long (with hours) and keep waiting some pieces in buffer areas significantly reduce makespan. Staying time at buffer area is not pre-determined. Whenever conditions met, this piece should go to next target. So how can i overcome such that problem? Can Flexible Job Shop Problem solve such a dynamic route problem? (Because decision of sending pieces to buffer area is not predetermined.) I will appreciate your help. Thanks in advance.   

14 Temmuz 2019 Pazar 00:33:48 UTC+3 tarihinde Laurent Perron yazdı: