Hello,
so you want to minimize the sum of the setup times for all the workers?
You can set the objective to be an expression summing the transition times for all the workers for all their tasks.
For example, for 2 workers (in C++, sorry, quicker for me):
#include <ilcp/cp.h>
IloInt NbTypes = 5;
IloInt SetupM1[] = {
22, 24, 7, 10, 9,
63, 21, 42, 1, 24,
60, 70, 37, 70, 39,
77, 57, 65, 33, 81,
51, 31, 18, 32, 48
};
IloInt SetupM2[] = {
27, 48, 44, 0, 21,
42, 44, 42, 40, 17,
36, 53, 31, 56, 50,
6, 43, 46, 38, 16,
25, 27, 45, 67, 37
};
IloInt NbTasks = 10;
IloInt TaskDur[] = {
19, 18, 16, 11, 16, 15, 19, 18, 17, 17
};
IloInt TaskType[] = {
3, 1, 1, 3, 4, 2, 0, 4, 3, 0
};
int main(int, const char*[]) {
IloEnv env;
try {
IloModel model(env);
IloTransitionDistance setup1(env, NbTypes);
IloTransitionDistance setup2(env, NbTypes);
for (IloInt i = 0; i < NbTypes; ++i) {
for (IloInt j = 0; j < NbTypes; ++j) {
setup1.setValue(i, j, SetupM1[NbTypes*i+j]);
setup2.setValue(i, j, SetupM2[NbTypes*i+j]);
}
}
IloIntArray tp(env, NbTasks);
IloIntervalVarArray a (env, NbTasks);
IloIntervalVarArray a1(env, NbTasks);
IloIntervalVarArray a2(env, NbTasks);
char name[100];
for (IloInt i = 0; i < NbTasks; ++i) {
IloInt type = TaskType[i];
IloInt d = TaskDur [i];
tp[i] = type;
sprintf(name, "A%ld_TP%ld", (long)i, (long)type);
a[i] = IloIntervalVar(env, d, name);
IloIntervalVarArray alt(env, 2);
sprintf(name, "A%ld_M1_TP%ld", (long)i, (long)type);
a1[i] = IloIntervalVar(env, name);
a1[i].setOptional();
alt[0] = a1[i];
sprintf(name, "A%ld_M2_TP%ld", (long)i, (long)type);
a2[i] = IloIntervalVar(env, name);
a2[i].setOptional();
alt[1] = a2[i];
model.add(IloAlternative(env, a[i], alt));
}
IloIntervalSequenceVar s1(env, a1, tp);
IloIntervalSequenceVar s2(env, a2, tp);
model.add(IloNoOverlap(env, s1, setup1, IloTrue));
model.add(IloNoOverlap(env, s2, setup2, IloTrue));
IloIntExpr setupsSum(env);
for (IloInt i = 0; i < NbTasks; ++i) {
IloInt tpi = TaskType[i];
IloIntArray setup1Array(env, NbTypes+1);
IloIntArray setup2Array(env, NbTypes+1);
for (IloInt j = 0; j < NbTypes; ++j) {
setup1Array[j] = SetupM1[NbTypes*tpi+j];
setup2Array[j] = SetupM2[NbTypes*tpi+j];
}
setup1Array[NbTypes] = 0; // Last on resource or resource not selected
setup2Array[NbTypes] = 0; // Last on resource or resource not selected
setupsSum += setup1Array[IloTypeOfNext(s1, a1[i], NbTypes, NbTypes)];
setupsSum += setup2Array[IloTypeOfNext(s2, a2[i], NbTypes, NbTypes)];
}
IloObjective objective = IloMinimize(env, setupsSum);
model.add(objective);
IloCP cp(model);
cp.setParameter(IloCP::LogPeriod, 10000);
cp.setParameter(IloCP::TimeLimit, 2);
if (cp.solve()) {
cp.out() << "Worker 1: " << std::endl;
IloIntervalVar act;
for (act = cp.getFirst(s1); act.getImpl() != 0; act = cp.getNext(s1, act))
cp.out() << cp.domain(act) << std::endl;
cp.out() << "Worker 2: " << std::endl;
for (act = cp.getFirst(s2); act.getImpl() != 0; act = cp.getNext(s2, act))
cp.out() << cp.domain(act) << std::endl;
cp.out() << "Sum of transition times \t: " << cp.getObjValue() << std::endl;
}
else {
cp.out() << "No solution found." << std::endl;
}
cp.end();
}
catch (IloException& ex) {
env.out() << "Caught: " << ex << std::endl;
}
env.end();
return 0;
}
It gives:
! ----------------------------------------------------------------------------
! Search terminated by limit, 11 solutions found.
! Best objective : 91 (gap is 100.0%)
! Best bound : 0
! ----------------------------------------------------------------------------
! Number of branches : 619750
! Number of fails : 296263
! Total memory usage : 6.2 MB (6.1 MB CP Optimizer + 0.1 MB Concert)
! Time spent in solve : 2.03s (2.02s engine + 0.01s extraction)
! Search speed (br. / s) : 306958.9
! ----------------------------------------------------------------------------
Worker 1:
A2_M1_TP1[1: 0 -- 16 --> 16]
A1_M1_TP1[1: 37 -- 18 --> 55]
A4_M1_TP4[1: 79 -- 16 --> 95]
A5_M1_TP2[1: 113 -- 15 --> 128]
Worker 2:
A3_M2_TP3[1: 0 -- 11 --> 11]
A9_M2_TP0[1: 17 -- 17 --> 34]
A0_M2_TP3[1: 34 -- 19 --> 53]
A6_M2_TP0[1: 59 -- 19 --> 78]
A8_M2_TP3[1: 78 -- 17 --> 95]
A7_M2_TP4[1: 111 -- 18 --> 129]
Sum of transition times : 91
Regards,
ol
------------------------------
Olivier Lhomme
------------------------------
Original Message:
Sent: Thu August 26, 2021 09:30 AM
From: Avinash Kumar
Subject: Reducing Transition time as cost in parallel sequencing problem
Is there a way to include the total transition time in the cost function?
My objective is to reduce transition time irrespective of how long it takes to execute tasks by a worker. So if a worker takes even a week to execute the tasks in 0 transition time, then all the work should be allocated to him.
Earlier I tried to reduce the total time span of all the intervals (which in turn should have reduced the transition time) but it didn't give the exact solution which I am looking for. I added up the time span from all the workers.
I am working in Python. Any advice will be helpful.
------------------------------
Avinash Kumar
------------------------------
#DecisionOptimization