Двухуровневая оптимизация распределения заданий по пакетам и расписаний их выполнения в конвейерных системах с буферами ограниченных размеров

Аннотация

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