Choco求解器的建模约束
我在玩巧克力求解器来解决一些任务调度问题。
我有几个作业和可能的插槽(在那里可以执行作业)。有一些制约因素，如：
- 每个插槽只能有一个作业(C.1)
- 作业需要一定的时间
t，插槽有可用的持续时间d。该工作必须符合可持续时间：t<=d(C.2)
因此，基本上用一些基本/伪类来表示：
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);这正如期而至。但现在我也想建立其他约束的模型。但是我正在讨论如何将作业/插槽与时间/持续时间结合起来，因为时间和持续时间是一个因变量。
在第一步中，我为时间和持续时间建模了另外两个变量：
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)相适应。
是否可以定义这样的约束(不工作/有效伪代码)：
for(int i=0;i<jobCount;i++){
times[i].le(durations[jobs[i]]).post();
}还是模特完全错了？！
也许有人有解决办法或想法？！
回答 1
Stack Overflow用户
发布于 2018-08-23 07:50:37
如果您说每个插槽只能有一个作业，那么很自然地选择slot作为您的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，以便解决程序可以选择有效的项。然后，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(){...})中描述的所有解决方案。
https://stackoverflow.com/questions/51964719
复制相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号