Хранить элементы массива между граничными пределами

Question

Мне нужно сгенерировать алгоритм для производственной очереди, и я уверен, что это было решено раньше. Это выглядит как стандартная проблема, но я не могу найти никаких ссылок, так что я немного озадачен ...

Давайте предположим, что у меня есть массив элементов с двумя значениями:

• Дата_начало
• delivery_date

Элементы не могут входить в очередь до начала_стали и должны выйти из очереди перед доставкой_данных. То есть, каждый элемент должен быть «обработан» в интервале (start_date, delivery_date].

min_date и max_date также являются произвольными. Для некоторых элементов есть 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 с:

• Источника, Vertex сек
• Раковины вершины т
• Вершины U_i для каждого задания я
• ребра (с, u_i) емкость 1 для каждого задания i
• Вершина v_j за каждый день j в расписании
• Ребро (v_j, t) емкости, равное количеству заданий, которые могут обрабатываться в день j
• Кромка (u_i, v_j) емкости 1, когда задание i может обрабатываться в день j - то есть, когда start_date [i] < = j < = delivery_date [i].

Теперь вычислите максимальный поток от s до t. Если значение этого потока равно числу n заданий, то все задания могут быть обработаны; если он ниже, то самое большее, что многие работы могут быть обработаны. (Поток не может быть выше n, так как из s есть только n ребер, каждый из которых имеет емкость 1.) В любом случае, сетевой симплекс-алгоритм предоставит вам потоки по 1 или 0 в каждом из края между заданием и днем, сообщая вам, какие рабочие места обрабатывать в какие дни.

Вышеупомянутая формулировка также с радостью решит более общую (хотя, возможно, не так полезную) проблему, в которой каждое задание может иметь произвольный набор дней, на которых он может быть запущен, а не ограничен интервалом дней от start_date [i] до delivery_date [i]. Из-за этого я не уверен, что вышеописанный подход является наилучшим решением для вашей более ограниченной проблемы, но он по крайней мере гарантирует оптимальное решение в полиномиальное время.

Answer 2

Я был бы склонен просто перебирать вперед день за раз, выделяя любые соответствующие и нераспределенные рабочие элементы на этот день в порядке доставки (чтобы сначала были назначены те, у кого самый сжатый крайний срок, и вся доступная емкость). С каждым днем ​​вы можете увидеть доступную запасную емкость или если есть нехватка мощности (которая была бы тогда, когда после распределения всей доступной емкости таким образом есть 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 + " **"); 
      } 
     } 

Резервные мощности по диапазону дат становится немного сложнее, поскольку есть несколько переменных, то есть возможность переложить работу вперед во времени для создания потенциала.