JobShop Modelisation CP-SAT

[arnauddl]

Dear all,

I'm trying to modelize a jobshop problem in python with CP-SAT but I am stuck with some constraints.

The problem:
I have a set of Jobs, each job has a duration and a due date. My objective is to minimize the makespan and respect the due dates.

-The first constraint I can't find how to modelize is how to have maximum 14 Jobs runing in parallel.
-The second thing is in case the problem doesn't have a solution within the due dates range, how can I bypass some due datea constraints while minimizing the delayed Jobs?

Thank a lot for your help!

[lperron]

1. use the cumulative constraint.
2. look at examples/python/single_machine_scheduling_with_setup_release_due_dates_sat.py or examples/cpp/weighted_tardiness_sat.cc

[arnauddl]

Thanks a lot the cumulative constraint is working great!

Now I'd like to assign these 14 jobs which are running in parallel to some machines (I have a total of 14 machines), Almost all job can go on any machine but there a few constraints of compatibility that I stored in a matrix Job-Machine.

But I'm not sure this approach would work with the cumulative constraint.

[arnauddl]

For now I have only one idea:
Create optional interval variables for each combination of Job-Machine. Then create a relation between all boolean concerned by a Job to make their sum = 1 (so the Job will be assigned to only one machine).

Example with the following compatibility matrix (4 jobs, 4 machines):
JOB1[MA1,MA2,MA4]
JOB2[MA1,MA2,MA3]
JOB3[MA1]
JOB4[MA3,MA4]

I create the optional interval variables (JOBiMAi) with their presence variables (bii as booleans)
JOB1MA1b11, JOB1MA2b12, JOB1MA4b14
JOB2MA1b21, JOB2MA2b22, JOB2MA3b23
JOB3MA1b31
JOB4MA3b43, JOB4MA4*b44

Then the relations
b11 + b12 + b14 = 1
b21 + b22 + b23 = 1
b31 = 1
b43 + b44 = 1

After I can create a No Overlap constraint on all variables concerned by a Machine (JOB1MA1, JOB2MA1, JOB3MA1...), to have each machine running only one Job at once.
Also a cumulative constraint on all interval variables, to have max 4 jobs running in parallel (4 machines available).

Do you think this approach is correct? I'll have a total of 14 machines and about 50 jobs so about 700 optional interval variables...

Maybe there is a much easier way... If some expert can give me their opinion, I'd be very grateful!

[lperron]

This is what is implemented in the jobshop_sat.cc example. Laurent Perron | Operations Research | [email protected] | (33) 1 42 68 53 00 Le lun. 7 déc. 2020 à 18:12, arnauddl <[email protected]> a écrit :

…

For now I have only one idea: Create optional interval variables for each combination of Job-Machine. Then create a relation between all boolean concerned by a Job to make their sum = 1 (so the Job will be assigned to only one machine). Example with the following compatibility matrix (4 jobs, 4 machines): JOB1[MA1,MA2,MA4] JOB2[MA1,MA2,MA3] JOB3[MA1] JOB4[MA3,MA4] I create the optional interval variables (JOBiMAi) with their presence variables (bii as booleans) JOB1MA1*b11, JOB1MA2*b12, JOB1MA4 *b14 JOB2MA1*b21, JOB2MA2*b22, JOB2MA3*b23 JOB3MA1 *b31 JOB4MA3*b43, JOB4MA4*b44 Then the relations b11 + b12 + b14 = 1 b21 + b22 + b23 = 1 b31 = 1 b43 + b44 = 1 After I can create a No Overlap constraint on all variables concerned by a Machine (JOB1MA1, JOB2MA1, JOB3MA1...), to have each machine running only one Job at once. Also a cumulative constraint on all interval variables, to have max 4 jobs running in parallel (4 machines available). Do you think this approach is correct? I'll have a total of 14 machines and about 50 jobs so about 700 optional interval variables... Maybe there is a much easier way... If some expert can give me their opinion, I'd be very grateful! — You are receiving this because you commented. Reply to this email directly, view it on GitHub <#2255 (reply in thread)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ACUPL3MTFTHUXI3W62RAR7DSTUEHJANCNFSM4UKGJFTQ> .

[arnauddl]

Nice, I succeeded in what I wanted to do! I realy appreciate your help.

Now I'd like to add some specific constraints between some intervals I created (few pairs of machines can't run some jobs in parallel because they share the same molding time).

I made a matrix between my interval vars, which look like this:
JOB1MA2 JOB2MA2 JOB3MA2 JOB4MA2 JOB5MA2
JOB1MA1 X 1 1 1 1
JOB2MA1 1 X 1 0 0
JOB3MA1 1 1 X 1 1
JOB4MA1 0 0 0 X 1
JOB5MA1 1 0 1 1 X

X: represent an impossible combination because of previous constraints I built.
1: means both intervals can overlap
0: means both intervals can't overlap

I could build all the no overlapping constraints one by one but my matrix has over 1000 combinations.

Do you think about a faster way to create these constraints?