Здравствуйте.
Достаточно длительное время я изучал различные задачи составления расписаний, в которых введен
порядок предшествования (частичный порядок) на множестве заданий, причем
прерывания выполнения заданий
запрещены. Кроме того, на задания могут быть наложения различные ограничения, например, директивные сроки выполнения заданий. В общем случае, это задачи относятся к типу DAG Scheduling Problem (пример:
http://charm.cs.uiuc.edu/users/arya/docs/4.pdf). Для решения этой задачи мной были построены как однопоточные модели, так и параллельные эвристические алгоритмы.
Следующим шагом, хотелось бы попробовать решить практическую задачу, которая имеет схожие ограничения. Понятно, что задачи, имеющие относительные небольшие графы частичных порядков (например, состоящие из 500 заданий), не столь интересны, так как простой метод ветвей и границ сработает достаточно быстро, еще и точное решение найдет... Интересны задачи с тысячами, миллионами, а то и миллиардами зависящих друг от друга заданий (может что-то в масштабах города-миллионника или страны, а может есть небольшие задачи, в которых тоже скрыты такие зависимости).
Пока я не смог придумать такую задачу. Сначала показалось, что на эту модуль ложится задача оптимального плана ремонта дорог, но тут как-то непонятно, как же все-таки логически граф предшествования построить - получается нечеткий граф, функций принадлежности которого является вычисление приоритета каждой дороги. Это скорее задача без частичного порядка, но с учетом весов - задача о ранце. Во-вторых, даже такой граф - граф с циклами... Да и техника достаточно гибко перемещаться может, не учитывая порядок...
Не могли бы вы подсказать область или конкретную задачу, которая бы укладывалась в рамки данной модели? Возможно, кто-то сможет дать ссылки на статьи или другие ресурсы.
Кроме того, если кому-то тоже интересна эта тема, можно было бы взяться за совместное исследование (с возможностью написания статьи. Благо, лаборатория это позволяет).
