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

Question

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

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

start_date
delivery_date

项目不能在 start_date 之前进入队列，并且应该在 delivery_date 之前退出队列。也就是说，每个项目都应该是 "processed" 在区间 (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

我倾向于一次只向前迭代一天，按照交付日期的顺序将所有相关和未分配的工作项目分配到那一天（以便最紧迫的截止日期首先分配，所有可用容量用过的）。然后，您可以每天查看可用的备用产能，或者是否存在产能短缺（即在以这种方式分配所有可用产能后，有 1 个或多个工作项目的交付日期等于当前日期） .

例如在 C# 中类似于：

        public class WorkItem
        {
            public DateTime StartDate {get;set;}
            public DateTime DeliveryDate {get;set;}
        }

        public class ProductionCapacity
        {
            public DateTime Date {get;set;}
            public int Capacity {get;set;}
        }

        public void AllocateWork(ProductionCapacity[] productionCapacity, WorkItem[] workItems)
        {
            // tackle work items in order of delivery date
            var activeWorkItemList = workItems.OrderBy(w => w.DeliveryDate).ThenBy(w => w.StartDate).ToList();

            // iterate a day at a time
            foreach (var day in productionCapacity.OrderBy(p => p.Date))
            {
                // get the set of work items we can handle on this day
                var workWeCanDo = (from w in activeWorkItemList where w.StartDate <= day.Date && w.DeliveryDate >= day.Date select w).Take(day.Capacity);

                // Remove them all from the active workitems list
                foreach (var workItem in workWeCanDo)
                    activeWorkItemList.Remove(workItem);

                Console.WriteLine("Handling " + workWeCanDo.Count() + " work items on " + day.Date + " - spare capacity of " + (day.Capacity - workWeCanDo.Count()));

                var workWeCannotDo = (from w in activeWorkItemList where w.DeliveryDate <= day.Date select w);

                if (workWeCannotDo.Count() > 0)
                   Console.WriteLine("** Over capacity by " + workWeCannotDo.Count() + " work items on " + day.Date + " **");
            }
        }

按日期范围划分的备用容量会变得有点棘手，因为存在更多变量，即及时向前转移工作以创造容量的能力。

Answer 2

您可以将其表述为 maximum flow problem, and solve it with the network simplex algorithm。

创建图 G：

一个源顶点s
一个汇点t
每个作业 i
每个作业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 中的每个流工作和一天之间的边缘，告诉您在哪几天处理哪些工作。

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

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

Keep array items between boundary limits

sorting

algorithm

linear-programming