algorithm - 将数组项保持在边界限制之间

Question

我需要为生产队列生成一个算法，我确信这之前已经解决了。看起来很标准的问题，但是我找不到任何引用，所以我有点困惑......

假设我有一个包含两个值的项目数组:

• 开始日期
• 交付日期

元素不能在start_date 之前进入队列，并且应该在delivery_date 之前退出队列。也就是说，每个项目都应该在间隔(start_date，delivery_date)内“处理”。

min_date 和 max_date 也是任意的。对于某些项目，间隔为 3 天，而对于其他项目，间隔可能为 3 年。

然后，对于日历中的每一天，我都有能力处理任意数量的项目。

• 2016-02-01:60 件
• 2016-02-02:30 件
• 2016-02-03:45 件
• 2016-02-04:0 项
• 2016-02-05:48 项

我需要确认给定日历容量，我们的系统将能够将所有项目放入生产队列。

乍一看，我想到了一些非常简单的顺序(delivery_date desc、start_date asc)，但很明显这并不能解决问题。

你们知道有什么标准算法或开发库可以做到这一点吗？

PS:如果我能知道在给定时间间隔 [start_date, delivery_date] 我有多少备用容量，那也很棒。

Answer 1

您可以将其表示为 maximum flow problem , 并用 network simplex algorithm 解决.

创建图 G:

• 源顶点s
• 汇点t
• 每个作业i的顶点u_i
• 每个作业 i 的容量为 1 的边 (s, u_i)
• 时间表中每一天j的顶点v_j
• 边(v_j, t)的容量等于第j天可以处理的作业数
• 当作业 i 可以在第 j 天处理时容量 1 的边 (u_i, v_j) -- 也就是说，每当 start_date[i] <= j <= delivery_date[i]。

现在计算从 s 到 t 的最大流量。如果这个flow的值等于job的数量n，那么所有的job都可以被处理；如果它较低，那么最多可以处理许多作业。 (流不能高于 n，因为 s 中只有 n 条边，每条边的容量为 1。)无论哪种方式，网络单纯形算法都会为您提供 1 或 0 中的每个流工作和一天之间的边缘，告诉您在哪几天处理哪些工作。

上面的公式也将愉快地解决一个更一般的(虽然可能不是很有用)问题，其中每个作业我可以有一个任意的集合它可以运行的天数，而不是被限于从 start_date[i] 到 delivery_date[i] 的天数间隔。因此，我不确定以上是否是针对您的更受限问题的最佳解决方案——但它至少可以保证在多项式时间内获得最佳解决方案。