У меня следующая проблема.Представьте себе набор заданий со временем начала (st) и временем окончания (et).Каждая работа имеет приоритетное значение.Мне нужно запланировать эти задания, используя количество компьютеров больше 1.
По сути, это та же проблема планирования интервалов в классе с несколькими классами, но вместо весов у меня есть приоритеты. Мне не нужно максимизировать весаМне просто нужно быть уверенным, что задание с более высоким приоритетом не будет отброшено, пока выбрано другое задание с более низким приоритетом и перекрывает его.
Кроме того, машины должны быть заняты большую часть времени.
Это похоже на другие известные проблемы?Справка: S
Редактировать с примером и моими мыслями (входные задания даются упорядоченными):
---- (a) 0---- (б) 1-------------------------- (с) 2----------- (д) 3---- (е) 5------------------------ (е) 3-------- (г) 4
--------- (ч) 4
--------- (i) 4
буква = идентификатор задания, номер = приоритет.Для istance, с 1 выходной очередью, алгоритм должен быть простым:-проверьте локальный максимум (т. е. сравнивайте последующие задания, сохраняя лучшее, пока задание с приоритетом x не пересекается с заданием с приоритетом> x).В этом случае «е» является локальным максимумом.Так что мы анализируем до работы ф.-Поиск совместимых заданий в предыдущей проанализированной работе, удаление заданий, которые сталкиваются.В нашем случае мы анализировали до «ф».Мы можем удалить задания, которые сталкиваются с «е», поэтому у нас остались «а» и «b».и мы можем повторить алгоритм с «a» и «b», получив в результате «b» и «e».Теперь мы можем продолжить работу с последующими заданиями, которые не были отброшены («g», «h» и «i») и т. Д.
Моя проблема в случае нескольких выходных очередей.Моя идея с 3 выходными очередями, например:- выберите локальный максимум «е».- выберите лучшие 2 работы в своей области коллизий или предыдущих работах: в нашем случае «d» и «f».-Проверьте в области коллизий «d» и «f», если есть 3 задания с более высоким приоритетом.В этом случае откажитесь и возьмите лучший, который сталкивается.-Обязательно обновить предыдущую выбранную работу.Предположим, что «b» длиннее, имеет приоритет 2.5 и сталкивается с f.Сначала мы выбираем «f», но затем нам нужно отменить его, чтобы выбрать «g», «h» и «i», и выбрать b.
Заранее спасибо