------------------------------
Natalia Peralta
------------------------------

#DecisionOptimization

So if I understand well, a job is a fully ordered set of groups of operations and within a group, the operations will have to be sequenced but the order is not fixed. I'm I right?
In this case, the simplest model is to re-use the open shop model (unfixed sequence on all the operations of a job), but to add additional precedence constraints between the operations of consecutive groups. Typically, if group G_i is before groups G_i+1 in the job, post a precedence endBeforeStart between each pair of operation o_i_k and o_i+1_l for k in group G_i and l in group G_i+. Of course the risk is to post a quadratic number of precedence constraints. In order to prevent that, you can also represent the groups G_i as interval variables. G_i will span all the operation of the group (constraint span(G_i, [..., o_i_k, ...]) and you will post the precedence constraint between the group intervals (endBeforeStart(G_i, G_i+1)). In this model, you can still add the noOverlap constraint between all the operations of a given job.

Philippe

------------------------------
Philippe Laborie
------------------------------

Original Message:
Sent: Mon November 02, 2020 07:13 PM
From: Natalia Peralta
Subject: Group Shop Scheduling Problem

Good afternoon, I find myself solving a group shop scheduling problem, which is a hybrid model between a Job Shop and an Open Shop, with the peculiarity that there are groups of jobs, with setup times dependent on the sequence and with the following characteristics :

- Operations must satisfy precedence restrictions if placed in different groups. (as in a Job Shop)

- Operations that are not subject to precedence restrictions and can be processed in any order are placed in the same group. (as in an Open Shop)

- All group operations must be scheduled before any operation of the next group begins.

So far I carry this advance in the code:

using CP;

int nbJobs = ...;

int nbMchs = ...;

int timeLimit = ...;

range Jobs = 0..nbJobs-1; 

range Mchs = 0..nbMchs-1;

int setup[Mchs][Jobs][Jobs] = ...;

int OpDurations[j in Jobs][m in Mchs] = ...;

int W [j in Jobs] = ...; 

int duedate [j in Jobs] = ...;

tuple triplet { int i; int j; int sij; }

{triplet} M[m in Mchs] = { <i,j,setup[m][i][j]> | i,j in Jobs };

dvar interval itvs [j in Jobs][m in Mchs] size OpDurations[j][m];

dvar sequence mchs [m in Mchs] in all(j in Jobs) itvs[j][m] types all(j in Jobs) j;

dvar sequence jobs [j in Jobs] in all(m in Mchs) itvs [j][m] types all(m in Mchs) m;

dexpr int T[j in Jobs] = maxl(0, (endOf(itvs[j][nbMchs])-duedate[j]));

execute {

 cp.param.TimeLimit = timeLimit;

}

minimize sum(j in Jobs) W[j]*T[j];

subject to {

  forall (j in Jobs)

    noOverlap(jobs[j]);

  forall (j in Jobs, o in 0..nbMchs-2)

    endBeforeStart(itvs[j][o], itvs[j][o+1]);

  forall (m in Mchs)

    noOverlap(mchs[m],M[m]);  

  

} 

My consultation is that way I can make the restriction that allows me to set the scheduling of working groups with the aim of minimizing the weighted delay.

------------------------------
Natalia Peralta
------------------------------

#DecisionOptimization