Choco 求解器中的建模约束
Modelling constraints in Choco solver
我正在使用 choco 求解器来解决一些任务调度问题。
我有几个作业和可能的插槽(可以执行作业的位置)。
有一些限制,例如:
- 每个插槽只能有一个作业 (C.1)
- 一项工作需要一定的时间
t
并且空档有可用的持续时间 d
。
该工作必须适合可用的持续时间:t<=d
(C.2)
所以,基本上用basic/pseudo类表示:
class Job {
int id;
int time;
}
class Slot {
int id;
int duration;
}
目前,我可以为每个作业分配一个插槽,假设一个作业的 id 和一个插槽是连续编号的
int jobCount = 5; // 5 jobs with ids from 0 to 4
int slotCount= 20; // 20 jobs with ids from 0 to 19
Model model = new Model("Example");
IntVar[] jobs = model.intVarArray("Job", jobCount, 0, slotCount, false);
// all jobs must have different slots (C.1)
model.allDifferent(jobs).post();
// solving - details omitted, because I think it is not relevant...
Solution solution = model.getSolver().findSolution();
// assign the jobs to the slots like (pseudo-code):
// foreach i in jobs.length do
// job = getJobForId(i);
// getSlotForId(jobs[i]).setJob(job);
这是按预期工作的。但现在我也想对其他约束进行建模。但我坚持如何将 job/slot 与 times/durations 结合起来,因为时间和持续时间是因变量。
第一步,我为时间和持续时间建模了另外两个变量:
int[] slotDurations = {10, 20, 10, 40, ..., 20} // 20 durations (d)
IntVar[] durations = model.intVarArray("Time", slotCount, slotDurations);
int[] jobTimes = {5, 16, 30, 2, 17} // 5 times (t)
IntVar[] times = model.intVarArray("Time", jobCount , jobTimes);
现在,我需要表达时间应适合持续时间的约束 (C.2)。
是否可以像这样定义约束(不是working/valid伪代码):
for(int i=0;i<jobCount;i++){
times[i].le(durations[jobs[i]]).post();
}
还是模型完全错误?!
也许有人有解决方案或想法?!
如果你说一个slot只能有一个job,那么自然是selectslot
作为你的IntVarArray
,所以:
IntVar[] slots = model.intVarArray("Slot", slotCount, 0, jobCount, false);
int[] jobTimes = {0, 5, 16, 30, 2, 17}; //6(!) items; see explanation below.
int[] slotDurations = {10, 20, 10, 40, ..., 20}; //20 items
这里,slots
指向jobTime
中的项目。如果您的槽数多于工作数,那么请注意 allDifferent
约束:您最终将没有解决方案。在这种情况下,使用修改后的约束,例如 allDifferentExcept0
,以便求解器可以 select 一个有效的项目。那么,jobTimes[0]
必须是满足所有槽位(比如 0)的条目。
那你们就很亲近了。您需要做的就是引入一个中间 IntVar
变量,比如 shadowTime
,它代表 slots
给出的顺序中的时间,例如:
IntVar[] shadowTime = model.intVarArray("shadowTime", slotDurations.length, 0, jobTimes.length, false); //has the jobTimes in the order indicated by slots.
for(int i=0;i<slotCount;i++){
model.element(shadowTime[i], jobTimes, slots[i]).post();
//this is similar to what you wanted to achieve with 'durations[jobs[i]]' in your code
}
然后你可以在同一个循环中添加约束 C.2:
//within in the above loop:
{
...
model.arithm(shadowTime[i], "<", slotDurations[i]).post();
}
然后您可以按照手册中的描述列举所有解决方案 (while (solver.solver(){...}
)。
我正在使用 choco 求解器来解决一些任务调度问题。
我有几个作业和可能的插槽(可以执行作业的位置)。 有一些限制,例如:
- 每个插槽只能有一个作业 (C.1)
- 一项工作需要一定的时间
t
并且空档有可用的持续时间d
。 该工作必须适合可用的持续时间:t<=d
(C.2)
所以,基本上用basic/pseudo类表示:
class Job {
int id;
int time;
}
class Slot {
int id;
int duration;
}
目前,我可以为每个作业分配一个插槽,假设一个作业的 id 和一个插槽是连续编号的
int jobCount = 5; // 5 jobs with ids from 0 to 4
int slotCount= 20; // 20 jobs with ids from 0 to 19
Model model = new Model("Example");
IntVar[] jobs = model.intVarArray("Job", jobCount, 0, slotCount, false);
// all jobs must have different slots (C.1)
model.allDifferent(jobs).post();
// solving - details omitted, because I think it is not relevant...
Solution solution = model.getSolver().findSolution();
// assign the jobs to the slots like (pseudo-code):
// foreach i in jobs.length do
// job = getJobForId(i);
// getSlotForId(jobs[i]).setJob(job);
这是按预期工作的。但现在我也想对其他约束进行建模。但我坚持如何将 job/slot 与 times/durations 结合起来,因为时间和持续时间是因变量。
第一步,我为时间和持续时间建模了另外两个变量:
int[] slotDurations = {10, 20, 10, 40, ..., 20} // 20 durations (d)
IntVar[] durations = model.intVarArray("Time", slotCount, slotDurations);
int[] jobTimes = {5, 16, 30, 2, 17} // 5 times (t)
IntVar[] times = model.intVarArray("Time", jobCount , jobTimes);
现在,我需要表达时间应适合持续时间的约束 (C.2)。
是否可以像这样定义约束(不是working/valid伪代码):
for(int i=0;i<jobCount;i++){
times[i].le(durations[jobs[i]]).post();
}
还是模型完全错误?!
也许有人有解决方案或想法?!
如果你说一个slot只能有一个job,那么自然是selectslot
作为你的IntVarArray
,所以:
IntVar[] slots = model.intVarArray("Slot", slotCount, 0, jobCount, false);
int[] jobTimes = {0, 5, 16, 30, 2, 17}; //6(!) items; see explanation below.
int[] slotDurations = {10, 20, 10, 40, ..., 20}; //20 items
这里,slots
指向jobTime
中的项目。如果您的槽数多于工作数,那么请注意 allDifferent
约束:您最终将没有解决方案。在这种情况下,使用修改后的约束,例如 allDifferentExcept0
,以便求解器可以 select 一个有效的项目。那么,jobTimes[0]
必须是满足所有槽位(比如 0)的条目。
那你们就很亲近了。您需要做的就是引入一个中间 IntVar
变量,比如 shadowTime
,它代表 slots
给出的顺序中的时间,例如:
IntVar[] shadowTime = model.intVarArray("shadowTime", slotDurations.length, 0, jobTimes.length, false); //has the jobTimes in the order indicated by slots.
for(int i=0;i<slotCount;i++){
model.element(shadowTime[i], jobTimes, slots[i]).post();
//this is similar to what you wanted to achieve with 'durations[jobs[i]]' in your code
}
然后你可以在同一个循环中添加约束 C.2:
//within in the above loop:
{
...
model.arithm(shadowTime[i], "<", slotDurations[i]).post();
}
然后您可以按照手册中的描述列举所有解决方案 (while (solver.solver(){...}
)。