Задача минимизации максимального временного смещения для параллельных процессоров

Задачa минимизации максимального временного смещения для составления расписаний для параллельных идентичных процессоров — классическая комбинаторная оптимизационная задача, имеет много приложений и является $NP$-трудной. Эта задача составления расписаний обозначается как $P|r_j|L_{\mathrm{max}}$ и формулируется следующим образом: задания должны быть выполнены на нескольких параллельных идентичных процессорах; требуется определить, где и когда каждое задание должно быть выполнено так, чтобы минимизировать максимальное смещение. Для каждого задания известны время поступления задания на выполнение, время выполнения и директивный срок, к которому задание должно быть закончено. Прерывания выполнения заданий не допускаются. Большинство разработок приближенных алгоритмов концентрируется на построении незадерживающих расписаний, в которых процессор не может простаивать, если есть готовое к выполнению задание. Но для построения оптимального расписания необходимо рассматривать такие допустимые расписания, в которых невынужденный простой процессора возможен. Цель данной статьи — представить приближенный алгоритм с невынужденными простоями ELS/IIT (в котором наибольшим приоритетом обладает задание с минимальным поздним началом) и метод ветвей и границ, который строит допустимое расписание с заданным значением максимального смещения. Для нахождения оптимального решения предлагается комбинировать метод ветвей и границ с бинарным поиском. Библиогр. 14 назв. Табл. 5.