Модели смешанного целочисленного линейного программирования оптимизации включения заданий в пакеты и порядков проведения операций с ними в конвейерных системах
Ключевые слова:
конвейерные системы, пакеты заданий, расписания, модели смешанного целочисленного линейного программированияАннотация
Введение: идентификация эффективных расписаний выполнения в конвейерных системах наборов однотипных заданий предусматривает поиск лучших решений по включению заданий из этих наборов в пакеты и по порядкам пакетов для осуществления операций с ними на приборах указанных систем. При незначительном размере задач решить их возможно путем построения математических моделей смешанного целочисленного линейного программирования. Цель: разработать математические модели смешанного целочисленного линейного программирования, позволяющие определять лучшие решения по включению однотипных заданий из наборов в пакеты и по порядкам пакетов для проведения операций с ними в конвейерных системах. Результаты: в концепцию разработки математических моделей указанного вида положен подход, связанный с типизацией заданий. В соответствии с ним к одному типу относятся задания с равными значениями длительностей их выполнения на приборах конвейерных систем и с равными значениями длительностей переналадок приборов на осуществление операций с ними. На основе этого подхода разработаны математические модели смешанного целочисленного нелинейного программирования, позволяющие включить задания из наборов в пакеты и осуществить оптимизацию их порядков для реализации операций с ними в конвейерных системах. Условиями оптимизации являются: минимизация общего времени выполнения пакетов заданий на приборах конвейерных систем; минимизация суммарного запаздывания с окончанием выполнения наборов заданий по сравнению с заданными для них директивными сроками. Полученные модели линеаризованы путем введения дополнительных переменных и соответствующих им ограничений. Предложен способ линеаризации операции определения максимума из двух значений, предусматривающий введение индикаторных переменных и позволивший повысить производительность вычислений. В целях верификации представленных моделей разработано приложение в среде IBM ILOG CPLEX. С его применением проведены исследования по оптимизации составов пакетов заданий и расписаний их выполнения для различных наборов значений параметров задач поиска эффективных решений. Практическая значимость: полученные результаты показали эффективность разработанных моделей при решении задач оптимизации в рассматриваемой постановке. Предложенные математические модели позволяют повысить степень использования ресурсов конвейерных систем разного вида при реализации в них производственных или вычислительных процессов.
