Упаковка в корзину частей динамического набора с учетом последнего обновления

Там большой набор объектов. Набор динамичен: объекты можно добавлять или удалять в любое время. Назовем общее количество объектов N.

У каждого объекта есть два свойства: масса (M) и время (T) последнего обновления.

Каждые X минут небольшая группа из них должна быть выбрана для обработки, которая обновляет их T до текущего времени. Общее количество M всех объектов в пакете ограничено: не более L.

Здесь я хочу решить три задачи:

  1. найти алгоритм выбора следующего пакетного объекта;
  2. ввести классы объектов: простой, приоритетный (предоставляется вписывающийся хотя бы в каждую n-ю партию) и частый (вписывается в каждую партию);
  3. прогнозировать исчерпание емкости системы (время добавления следующего сервера = увеличение L).

Какая модель лучше всего описывает такую ​​систему?

Все дело в сервисе, который обрабатывает «объекты» во временных интервалах. Каждый объект необходимо «измерять» каждые N часов. N может варьироваться в диапазоне. X исправлено.

Объекты добавляются/удаляются людьми. N растет экспоненциально, довольно медленно, с некоторыми всплесками, вызванными публикациями. Конечно, прогноз не может быть точным, это всего лишь некоторая оценка. M варьируется от 0 до 1E7 с экспоненциальным распределением, большинство из них ближе к 0.

Я вижу, что здесь может быть несколько стратегий:

A. полный газ — упаковывайте каждую партию максимально близко к 100%. По мере роста N средний интервал попадания в конкретный объект будет расти.

B. равный темперамент :) - старайтесь держать средний интервал вокруг некоторого значения. Уровень заполнения партии будет расти с некоторого низкого уровня. Когда он приближается к 100 %, пора приобретать больше серверов.

К. - ?


optimization algorithm bin-packing dynamic-programming modeling
person Serge    schedule 17.10.2014    source источник

Ответы (2)


arrow_upward
3
arrow_downward

Вот довольно полный дизайн для вашей проблемы.

Ваш вопрос не совсем соответствует вашему описанию системы, для которой он предназначен. Так что буду считать, что описание верное.

Когда вы планируете измерение, вы должны пройти мимо объекта, в первый раз, когда он может быть измерен, и когда вы хотите, чтобы измерение произошло. Объект должен иметь атрибут weight и метод measured. Когда произойдет измерение, будет вызван метод measured, и разница между вашими классами будет заключаться в том, будут ли они перепланировать себя и с какими параметрами.

Внутри вам понадобится пара приоритетных очередей. См. http://en.wikipedia.org/wiki/Heap_(data_structure). подробности о том, как реализовать один.

Первая очередь — это время, когда измерение может произойти, все объекты, которые еще не могут быть измерены. Каждый раз, когда вы планируете партию, вы будете использовать ее для поиска всех новых измерений, которые могут произойти.

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

Теперь нужно знать, сколько класть в каждую партию. Учитывая систему, которую вы описали, всплеск событий можно ввести вручную, но со временем вы хотели бы, чтобы эти всплески сгладились. Поэтому я бы рекомендовал вариант Б, равный темперамент. Итак, для этого, когда вы помещаете каждый объект в очередь «готово сейчас», вы можете рассчитать его «средний рабочий вес» как его вес, деленный на количество периодов, пока это не должно произойти. Сохраните это вместе с объектом и подсчитывайте текущую скорость, с которой вы должны работать. Каждый период я ​​бы посоветовал вам продолжать добавлять в партию, пока не будет выполнено одно из трех условий:

  1. У вас закончились объекты.
  2. Вы достигли максимальной емкости партии.
  3. Вы превышаете свой средний рабочий вес в 1,1 раза. Дополнительные 10 % связаны с тем, что лучше использовать немного больше ресурсов сейчас, чем использовать их позже.

И, наконец, планирование мощностей.

Для этого нужно использовать некоторую эвристику. Вот разумный вариант, который может потребовать некоторой настройки для вашей системы. Поддерживайте массив ваших последних 10 измерений промежуточной суммы среднего рабочего веса. Поддерживайте «экспоненциально затухающее среднее значение вашей максимальной отметки». Делайте это, обновляя каждый раз по формуле:

medium_high_water_mark = 0,95 * medium_high_water_mark + 0,5 * max(последние 10 рабочих весов)

Если average_high_water_mark когда-либо окажется в пределах, скажем, 2 серверов вашей максимальной мощности, добавьте больше серверов. (Идея состоит в том, что сервер должен иметь возможность умереть, не оставив вас без воды.)

person btilly    schedule 20.10.2014
comment
Спасибо, Бен! Оцените подробный и вдумчивый ответ. Я создаю модель макета на основе вашего описания, чтобы поиграть с числами и возможными условиями. - person Serge; 20.10.2014

arrow_upward
0
arrow_downward

Я думаю, что ответ А хорош. Корзинная упаковка предназначена для максимизации или минимизации, и у вас есть только одна партия. Рассортируйте предметы по m и n.

person Gigamegs    schedule 20.10.2014