ГЛАВНАЯ
> Вернуться к содержанию
Статьи автора Селищев Иван Алексеевич
Программные системы и вычислительные методы, 2021-1
|
Селищев И.А., Олейникова С.А. - Математическая модель и алгоритм решения задачи планирования работы многофазных систем с гетерогенными ресурсами и временными ограничениями |
|
c. 35-45
|
DOI: 10.7256/2454-0714.2021.1.35005
Аннотация: Объектом исследования являются современные обслуживающие и производственные системы, специфика функционирования которых заключается в выполнении множества последовательно-параллельных работ со случайной длительностью. Принципиальной особенностью таких систем является стохастический характер длительности выполнения отдельных работ, которая зависит не только от внешних случайных факторов, но и выбора ресурсов, в частности, от исполнителя. Это обуславливает параллельное решение задачи формирования графика взаимно-зависимых работ и задачи о назначении данным работам исполнителей. В условиях ресурсных и временных ограничений данная задача является NP трудной и требует разработки алгоритмов, позволяющих предложить решение близкое к оптимальному за приемлемое время. Для разработки математического и алгоритмического обеспечения для решения данной задачи использовались метод критического пути, метод PERT, метод критической цепи, метод набегающей волны, а также методы решения задачи о назначениях. В результате получена математическая модель, учитывающая стохастический характер длительности выполнения отдельных работ, зависящий не только от случайных факторов, но и от исполнителей. С ее использованием сформулирована оптимизационная задача, позволяющая найти такое время начала работ и соответствующих исполнителей, чтобы полученная прибыль была наибольшей. На основании анализа существующих подходов и специфики рассматриваемой задачи был предложен алгоритм решения задачи, основанный на последовательном уточнении временных характеристик работ.
|