abstract: Рассматривается NP-трудная задача составления расписания минимальной длины для параллельных процессоров с ограничениями на порядок выполнения работ. Прерывания выполнения заданий не допускаются. Рассматриваются расписания, в которых процессор может простаивать при наличии готовых к выполнению заданий, если простои процессора приводят к сокращению общего времени выполнения заданий. Для этой задачи предлагается метод ветвей и границ, который строит допустимое расписание заданной длины. При построении оптимального расписания необходимо проверить все возможные варианты. Определяются нижняя и верхняя границы для длины расписания. Предложены и обоснованы правила, которые позволяют проанализировать частичное решение и отбросить неперспективные, применение этих правил приводит к значительному сокращению количества перебираемых вариантов. Рассматриваются и сравниваются различные подходы к выбору очередного задания для ветвления, обосновывается метод оценки частичного решения. Проведен вычислительный эксперимент на случайно сгенерированных задачах для проверки эффективности предложенных подходов. Результаты вычислительного эксперимента подтверждают перспективность алгоритма построения расписания. Библиогр. 8 назв. Табл. 4.
keywords: многопроцессорное расписание, расписание с простоями, метод ветвей и границ