Аннотация:В главе рассмотрена задача теории расписаний для одного прибора с заданными моментами поступления требований и двумя целевыми функциями. Первая целевая функция - минимизировать максимальное временное смещение, то есть максимальную разницу между сроком выполнения каждого задания и фактическим временем завершения. Вторая целевая функция - минимизировать максимальное время выполнения, то есть завершить все задания как можно скорее. Задача является NP-трудной в сильном смысле. Представлен полиномиальный алгоритм построения Парето-оптимального набора расписаний по критериям максимальной задержки и максимального времени завершения, то есть задачи 1 | rj | Lmax, Cmax, для случая, когда d1 = dn-rn-pn.
