Задача Qm ll Cmax с ограничениями на количество работ, выполняющихся на каждом приборе

Abstract

В данной работе рассматривается задача с ограничениями на множестве параллельных приборов различной производительности Q | m | Cmax, которая формулируется следующим образом. Задано множество N={i₁, i₂, ..., in} из n – независимых работ, где работа ij имеет время обработки pj. Работы выполняются на множестве M={j₁, j₂, ..., jm} из m приборов с различными скоростями sj, j = 1,...,m , при этом время выполнения i-й работы на j-м приборе равно tij = pj/sj . Дополнительно требуется, чтобы на каждом приборе выполнялось не более k работ. Необходимо построить расписание, у которого время завершения последней выполняемой работы минимально. Предлагается алгоритм, который строит расписание с гарантированной оценкой, равной 2. В работе используется методика пересчета динамической нижней оценки оптимального решения и сведение задачи к задаче меньшей размерности.