英文:
Is there any smarter way to constrain the max size of continuous tasks with ortools cp-sat
问题
在制药行业，换型/清洁事件通常非常漫长，甚至可能需要不同水平的操作人员资源。因此，在安排任务和事件时，它们需要仔细建模。使用CP-SAT求解器，我们仍然可以轻松处理这个问题。
但是有一个概念叫做“Campaigning”。这意味着我们希望尽可能连续地生产一个产品的订单。而且对于同一产品的连续生产有一个最大数量/限制：
假设我们有10个产品A的订单，而活动规模是4。那么我们通常会这样做：
[A->A->A->A] -> 换型/清洁 -> [A->A->A->A] -> 换型/清洁 -> [A->A]
当然，在不同产品之间总是需要换型/清洁。
假设我们分别有1个产品A和B的订单。那么我们仍然必须执行：
A -> 换型/清洁 -> B 或 B -> 换型/清洁 -> A
我们找到了一种通过创建Campaigns并可选地将候选任务分配到Campaigns中，最终安排Campaigns来建模这一概念的方法。但是这种解决方案的可扩展性真的很差。在下面的图像中，当我有5个产品A和B的订单，限制为2个订单时，我的笔记本电脑几乎要死机。
我们想知道是否有更智能的方法告诉模型如何处理这个问题。
英文:
In pharceutical industry, the changeover/cleaning events are typically very long and may even need different level of operator resource. As a result, they need to modelled carefully when we schedule the tasks and events. This is still something we can work with easily using CP-SAT solver.
But there is a concept called "Campaigning". It means we want continuously produce the orders of one product as much as possible. And there is a max number/limit for number of continuous production of the same product:
Suppose we have 10 orders for product A and the campaign size is 4. Then we typically do:
[A->A->A->A] -> changeover/cleaning -> [A->A->A->A] -> changeover/cleaning -> [A->A]
Of course, there shall always be changeover/cleaning between different products.
Suppose we have 1 order for product A and B respectively. Then we still have to do:
A -> changeover/cleaning -> B or B -> changeover/cleaning -> A
We did find a way to model this by creating Campaigns and optionally assign candidate Tasks into Campaigns and finally schedule the Campaigns instead. But the scalability of this solution is really bad. In the image below, when I have 5 orders for product A and B with limit being 2 orders, my laptop is already close to dead.
And the code is here: https://github.com/jiayi9/cp/blob/main/study_04_campaigning.py
We wonder is there any smarter way to tell the model how to do it.
The result using cumulative counting of tasks in a campaign and indicators of task reaching max size or not:
https://github.com/jiayi9/cp/blob/main/example_24_campaigning_with_cumul.py
答案1
得分: 2
过去我是这样做的：
- 使用电路约束
- 对于每个节点，创建一个整数变量cumul，上限为4。
- 对于每个普通弧A -> A（从任务i到任务j）的文字等式：cumul[j] = cumul[i] + 1
- 对于每个清洁弧A -- cleaning -> A（从任务i到任务j），添加：
- 文字等式：cumul[j] = 0
- 文字等式：start[j] >= end[i] + 清洁时间
- 对于弧A -> B和B -> A也是一样的
- start_literal[i] => cumul[i] = 1
请查看这个示例。
英文:
The way I did it in the past:
- use the circuit constraint
- for each node, create an integer variable cumul capped at 4.
- for each normal arc A -> A (task i to task j) literal => cumul[j] = cumul[i] + 1
- for each cleaning arc A -- cleaning -> A (task i to task j), add
- literal => cumul[j] = 0
- literal => start[j] >= end[i] + cleaning time
- Do the same for arcs A -> B and B -> A
- start_literal[i] => cumul[i] = 1
See this example.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论