Hello
@Petr Vilím and
@Paul Rubin,
Thanks for all your reply, I could model non-anticipatory setup times with additional interval variable (setup[i, j]), but I needed to create a new sequence variable (job[j]) and a new constraint (UniqueMaqJobAtTime) to prevent that an operation (setup + process time) cannot be processed in more of one machine in the same time. There is no sequence order of operation in each machine.
The final code is bellow:
dvar interval x[i in m, j in n] size p[i, j];
dvar interval setup[i in m, j in n];
dvar sequence mac[i in m] in append(all(j in n) x[i, j], all(j in n) setup[i, j]) types append(t, t);
dvar sequence job[j in n] in append(all(i in m) x[i, j], all(i in m) setup[i, j]) types append(t, t);
minimize max(i in m, j in n) endOf(x[i, j]);//Makespan minimization
subject to{
UniqueJobMaqAtTime:
forall(i in m)
noOverlap(mac[i]);
UniqueMaqJobAtTime:
forall(j in n)
noOverlap(job[j]);
SetupBeforeProc:
forall(i in m, j in n)
endAtStart(setup[i, j], x[i, j]);
SetupDepSeq:
forall(i in m, j in n)
lengthOf(setup[i,j]) == s[i][j][typeOfPrev(mac[i], setup[i,j], j, j)];
};
And I will try to simplify the model, adding xwithsetup interval variable. I have another question about typeOfPrev. How to use this function in python docplex? I modeling "SetupDepSeq:" constraint but I get a error when acess index of s matrix (a numpy array):
for i in m:
for j in n:
k = modelo.type_of_prev(mac[i], setup[i][j], j, j)
modelo.add( modelo.length_of(setup[i][j]) == s[i][j][k] )
typeOfPrev(mac[i], setup[i,j], j, j) returns "docplex.cp.expression.CpoFunctionCall" and gets an error to access index k in setup matrix:
IndexError: only integers, slices (`:`), ellipsis (`...`), numpy.newaxis (`None`) and integer or boolean arrays are valid indices
How to access the integer index of the type of operation in type_of_prev function?
Many Thanks,
------------------------------
Levi Abreu
------------------------------
Original Message:
Sent: Tue May 19, 2020 04:44 AM
From: Petr Vilím
Subject: How to modelling non-antecipatory setup times in CP Optimizer?
Hello,
If I understand correctly, setup time before x[i,j] should not start while operation on the previous machine x[i-1, j] is still executing. Indeed, I don't see a way how to model it using standard setup times. One possibility I see is to introduce additional interval variables setup[i,j] for the setup just before x[i,j]. Then we can constrain the setup to start after x[i-1, j] by:
endBeforeStart(x[i-1, j], setup[i, j]);
The operation must start right after the setup:
endAtStart(setup[i, j]), x[i, j]);
And length of the setup depends on the type of previous interval on the sequence:
lengthOf(setup[i,j]) == s[i][typeOfPrev(mac[i], setup[i,j], j, j)][j];
In the constraint above it is necessary to be careful about the case when the setup is the first interval in the sequence variable. Then typeOfPrev will be j (the third parameter of typeOfPrev) and I assume that s[i,j,j] is 0, therefore the length of the first setup is 0.
Note that intervals setup[i, j] must be part of sequence variable mac[i] therefore they also must have a type (in declaration of a sequence variable it is possible to specify types of the intervals in the sequence). Types of setup[i, j] doesn't matter though since there shouldn't be two consecutive setups on the sequence. Therefore all setups can use one single type (for example).
Depending on other constraints in your model, it may be possible to simplify the model above: use just one interval variable xwithsetup[i,j] for both x[i, j] and setup[i, j]. Then we have simple precedence between operations in one job:
endBeforeStart(xwithsetup[i-1, j], xwithsetup[i, j]);
And length of xwithsetup is a sum of length of the operation itself (lets say we have a 2D array length[i, j] for this purpose) and the setup:
lengthOf(xwithsetup[i,j]) == length[i,j] + s[i][typeOfPrev(mac[i], xwithsetup[i,j], j, j)][j];
Best regards, Petr
------------------------------
Petr Vilím
IBM
Original Message:
Sent: Fri May 15, 2020 10:02 PM
From: Levi Abreu
Subject: How to modelling non-antecipatory setup times in CP Optimizer?
Hi,
I try to modeling sequence-dependent setup times in a open shop scheduling problem with transition matrix and noOverlap constraint:
But, I get a solution where setup times are executed before the jobs finish on the previous machines, like anticipated setup times. I would like a restriction that forces setups to be performed only after the job is finished on the previous machine.
I try with sequence expressions, where s[i, j, k] is the setup time of job j processed after job k in machine i, mac is a sequence variable of permutation of jobs in each machine and job is a sequence variable of permutation of machines in each job.
forall (i in m, j in n) startOfNext(mac[i], x[i, j], maxint, maxint) >= endOf(x[i, j], 0) + s[i][typeOfNext(mac[i], x[i, j], j, j)][j]; forall (i in m, j in n) startOfNext(job[j], x[i, j], maxint, maxint) >= endOf(x[i, j], 0);// + s[typeOfNext(job[j], x[i, j], i, i)][j][*];
* I need to indicate the index of the last job processed of the next machine of job j sequence
Is there another form of modeling non-anticipatory setup times?
or
Can someone help me to model this constraint with sequence variables?
Many Thanks,
Levi Abreu
------------------------------
Levi Abreu
------------------------------
#DecisionOptimization