Постановка задачи

Имеется вычислительная система (ВС), состоящая из несвязанных идентичных устройств (приборов, процессоров и т.п.)

На обслуживание в ВС поступает набор из независимых параллельных заданий (работ) известно время решения задания на любом из устройств. При этом каждое задание может выполняться на любом из устройств (процессоре), в каждый момент времени отдельный процессор обслуживает не более одного задания и выполнение задания не прерывается для передачи на другой процессор. Требуется найти такое распределение заданий по процессорам, при котором суммарное время выполнения заданий на каждом из процессоров было бы минимальным. Под расписанием следует понимать отображение , такое что, если , то говорят что задание , в расписании назначенного на процессор . При сделанных выше допущениях, расписание можно представить разбиением множества заданий на непересекающихся подмножеств

Критерий, используемый для минимизации времени завершения обслуживания заданий, является минимальным критерием и определяется в следующем виде: , где

- время завершения работы процессора .