Алгоритмы оптимизации очереди заданий
Простейшее решение:
Создать
var Status = Object.freeze({
"Connecting":0,
"Ready":1,
"Loading":2,
"Processing": 3
});
Получить значение
console.log(Status.Ready) // 1
Получить ключ
console.log(Object.keys(Status)[Status.Ready]) // Ready
9 ответов
Возможно, вы захотите изучить проблему рюкзака или проблему упаковки мусора , поскольку они в принципе аналогичны тому, что вы пытаетесь сделать здесь.
В описании проблемы вы упоминаете, что целью является выполнение заданий с наименьшей задержкой. Если это на самом деле ваша единственная цель, то решение простое - нанять все доступные ресурсы. Многие из них будут простаивать большую часть времени, но это в значительной степени гарантирует минимально возможную задержку.
Я подозреваю, что ваша настоящая цель состоит в том, чтобы как можно больше минимизировать как задержки, так и простаивающие ресурсы, поэтому здесь всегда будет некоторый компромисс между задержкой и потраченными впустую ресурсами.
Это похоже на несколько вещей: экономическое количество заказа, уравновешивание авансовой стоимости найма со стоимостью выполнения; LP или IP, минимизирующий формулу общей стоимости с учетом различных ограничений; а затем есть распределения вероятностей (время на набор; требуемые рабочие ресурсы?), делающие все это стохастическим.
Звучит достаточно сложно, что, если бы я делал это, я бы, вероятно, создал симуляцию. Система не кажется слишком сложной для этого или слишком математически обременительной для работы при большом количестве итераций или длительном времени работы, поэтому вы можете получить довольно стабильные и полезные результаты.
Эту проблему можно рассматривать как задачу линейной оптимизации, поэтому это должно быть началом. Я использовал эту библиотеку , но в ней есть много других вещей, так что это может быть излишним. Вместо этого нетрудно разработать свою собственную библиотеку, в этой книге есть хорошая глава о LP.
Я не знаю литературы по таким проблемам. Тем не менее, я предполагаю, что они есть, поскольку теория очередей - большая академическая область, и это не похоже на смехотворно надуманную ситуацию. Имейте в виду, что тот факт, что вы заботитесь о средней задержке, а не о задержке наихудшего случая или задержке N-го процентиля, может поставить вас в меньшинство.
Мой первый инстинкт состоит в том, что, поскольку, кажется, есть много рабочих мест, хороший решение будет иметь несколько «гибких» рабочих, постоянно работающих. Это набор рабочих, которые вместе могут выполнять большинство типов общих заданий с приемлемой задержкой. Чем ниже должна быть задержка, тем больше ресурсов в этом наборе и тем больше времени они проводят в режиме ожидания. Кроме того, более "прерывистый" ваш ввод (при условии, что пакеты непредсказуемы), тем больше времени простоя вам нужно, чтобы предотвратить большие задержки во время всплесков.
Затем в двух случаях вы нанимаете дополнительных «специализированных» работников:
1) Появляется редкий тип работы, на которой ваш текущий набор сотрудников может только обрабатывать с большими затратами времени или не обрабатывать вообще. Таким образом, вы нанимаете (грубо говоря) того, кто может его сместить, а затем выполняете как можно больше из остальной части вашей очереди.
2) Такой работы нет, но вы видите возможность нанять кого-то, кто просто так может чтобы взять некоторую комбинацию заданий из текущей очереди и выполнять их дешевле, чем ваши нынешние сотрудники, но не оставляя текущих сотрудников без дела. Так что вы нанимаете этот ресурс.
Что касается фактического алгоритма: почти наверняка невозможно найти лучшее решение с вычислительной точки зрения, поэтому правильный ответ зависит от ресурсов обработки и вас. мы рассматриваем эвристику и решаем частичные проблемы. Пока все, кого вы нанимаете, заняты, и вы не можете нанять кого-либо еще, не вызвав значительного простоя в какой-то момент в будущем, вы, вероятно, находитесь в непосредственной близости от хорошего решения и где-то рядом с "максимальной отдачей на доллар" "точка компромисса между задержкой и стоимостью. Наем дополнительных ресурсов после этого дает убывающую отдачу, но это не означает, что вы не желаете делать это с указанной задержкой и / или указанным бюджетом.
Но это зависит от того, как выглядят входящие задания: если у вас есть ресурс, который может выполнять только один тип работы, и эта работа приходит только один раз в день / неделю / год, тогда это ' Вероятно, лучше нанять их один раз в день, чем ждать, пока у вас будет достаточно работы, чтобы заполнить их минимально возможный временной отрезок (именно поэтому пожарные проводят большую часть своего времени, играя в карточные игры, а машинистки проводят большую часть своего времени за набором текста. Всегда есть достаточно набора текста, чтобы занять хотя бы одну машинистку, но пожары случаются редко. Более того, нам не нужно решение с «максимальной отдачей на доллар», мы хотим меньшую задержку, чем это). Так что, вероятно, есть возможности настроить алгоритм для вашего конкретного набора ресурсов и шаблона входящих заданий, если вы решаете один конкретный случай проблемы, а не пишете общее программное обеспечение для планирования.
Плюс, предположительно, если ресурсы - это люди. , вы не можете гарантировать, что найм будет успешным. Они не
Боюсь, у меня нет для вас простого ответа, но вот еще несколько связанных ресурсов, которые можно найти в поисках идей.
О многомерных проблемах упаковки
A Стратегия на основе векторов для динамического распределения ресурсов
Замечательный вопрос !!
Я бы изучал динамическое программирование, линейную оптимизацию и теорию массового обслуживания. К сожалению, для меня нет простого способа ответить на эти вопросы. У меня нет математических знаний, необходимых, чтобы дать вам твердый, оптимальный ответ на эти вопросы.
Однако, если вы увлечены такими вещами, это звучит как возможность получить хорошее, хотя, вероятно, не оптимальное решение, используя алгоритм искусственного интеллекта. Я бы порекомендовал либо генетический алгоритм, либо имитацию отжига. Кодирование любого из них не займет много времени. Идея состоит в том, что вы выбираете случайные действительные входные данные и можете настраивать эти потенциальные решения, развивая их в лучшие (или автоматически выбирая новые) с течением времени. Это хороший компромисс между получением оптимальных ответов и бесконечными затратами на код и доказательство правильности.
Я бы посмотрел на это с другой стороны ... не уверен, что он охватывает все.
1) «Ресурс» на самом деле может рассматриваться как «рабочий центр». Сколько рабочих центров у вас открыто для работы над «заданиями», зависит от того, кто вошел в систему.
2) Распределение ресурсов по времени ожидания - чем дольше они ждали задания, тем больше они должны быть в списке для следующего запроса. Так никто не замерзнет и не остановится. Вам нужно будет найти и установить порог, по которому (относительно ресурсов и рабочих мест). Вы можете решить, хотите ли вы, чтобы они щелкнули, чтобы выбрать свое следующее задание, или чтобы система автоматически получала одно между заданиями
3) Настроить очередь расписания заданий - Я не знаю, актуально ли это, но могут быть задания с высоким / низким приоритетом и т. д. Вам нужен пул заданий, перечислен «по порядку атаки». Каждая работа в графике работы может проходить различные этапы, поэтому вы знаете, где все находится, и знаете, когда вы закончите, чтобы перейти к следующему. Планировщик заданий будет искать доступные ресурсы и назначать их заданиям по расписанию. Скорее всего, это будет большая часть мозга вашей системы расписания.
Я просто надеюсь, что вы не строите центр обработки исходящих вызовов: P
Это очень похоже на Real -Время Операционная система Планирование. В Википедии подробно описаны некоторые из используемых алгоритмов:
- Совместное планирование
- Планирование с циклическим перебором.
- Упреждающее планирование
- Упреждающее планирование с фиксированным приоритетом, реализация упреждающее квантование времени
- Упреждающее планирование критической секции
- Статическое планирование времени
- Первый подход к первому сроку
- Расширенное планирование с использованием стохастика и MTG
Вы можете написать избыточную нейронную сеть для анализа результатов вашего алгоритма и ранжирования выходных данных на основе ожидаемых результатов. :)
Разбейте свой метод настолько, насколько сможете. Затем вы также можете провести модульный тест только для случайной части, чтобы проверить диапазон значений. Даже проведите тестовый запуск несколько раз, чтобы увидеть, изменится ли результат.
чем вы можете с самого начала снизить некоторую сложность, а затем использовать некоторую форму средневзвешенных значений для предпочтений. Также при приеме на работу, поскольку мин. вы можете набирать на 30 минут, и, предположив, что они стоят дороже, вы, вероятно, захотите убедиться, что у них самый высокий уровень загрузки.Вот несколько статей, которые могут помочь:
- Планирование работы цеха - http : //en.wikipedia.org/wiki/Job_Shop_Scheduling
- Конкурентный анализ - http://en.wikipedia.org/wiki/Competitive_analysis_ (онлайн-алгоритм)
- Проблема с сервером k - http: / /en.wikipedia.org/wiki/K-server_problem