or-tools：约束间隔变量搜索过程更紧凑
我一直在尝试使用以下设置来对工作店问题进行建模：
- 变量＆amp;约束： 对于每个任务：
- 工作级变量：start（newintvar），end（newintvar），Interval（newIntervalvar）
- tardiness = max（task_end -task_end -task_due_date，0）
- 优先级约束：
for task_before, task_after in tasks_precedence:
model.Add(start[task_after] >= end[task_before])
对于每台机器：
- 无需重叠的所有“间隔”，这可能是所有“间隔”在机器
for machine in machines:
model.AddNoOverlap([intervals[machine, task] for task in machine_tasks[machine])
- 目标上产生的：最大程度地减少每项工作的迟钝性
model.Minimize(sum(tasks_tardiness))
时，当我在给定的时间限制内计算结果并且尚未证明其最佳性时，某些间隔的位置很差。
例如：时间表不是紧凑，最后任务（红色块）远离其截止日期很远。 尽管它符合所有指定的约束...将任务放在该位置仍然没有意义。
关于如何改进搜索过程并使模型可以推断出更好的解决方案的任何想法？
I have been trying to modelize the job-shop problem with the following setup:
- Variables & constraints:
For each task:
- job-level variables: start (NewIntVar), end(NewIntVar), interval(NewIntervalVar)
- tardiness = max(task_end - task_due_date, 0)
- precedence constraint:
for task_before, task_after in tasks_precedence:
model.Add(start[task_after] >= end[task_before])
For each machine:
- No overlap for all "intervals" that could be produced on the machine
for machine in machines:
model.AddNoOverlap([intervals[machine, task] for task in machine_tasks[machine])
- Objective: Minimising the tardiness for each job
model.Minimize(sum(tasks_tardiness))
However, when I compute the results within a given time-limit and no optimality is proven yet, some of the interval are very poorly positioned.
For instance: Schedule is not compact and the last task (red block) is very far from its due date.
While it meets all of the specified constraint... It still does not make sense to place the task at this position.
Any idea on how to improve the search procedure and enables the model to infer better solutions ?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
我的直觉是分两个阶段解决。
解决您当前的型号。记录每台机器上间隔的顺序。
然后创建第二个模型，在该模型中，您可以修复间隔的顺序（不需要NO_OVERLAP约束），然后更改目标以最大化紧凑度。
My intuition is to solve in two phases.
Solve your current model. Record the order of the intervals on each machine.
Then create a second model, where you fix the order of intervals (no need for the no_overlap constraint), and change the objective to maximize compactness.