Аннотация:
Рассматривается задача минимизации общего времени обработки идентичных деталей со сложным технологическим маршрутом, когда возможно неоднократное поступление деталей на некоторые машины. Исследуются вопросы вычислительной сложности данной задачи, доказана её NP-трудность в обычном смысле. При фиксированном числе деталей доказана псевдополиномиальная разрешимость задачи. Исследуется вопрос использования циклических расписаний при построении приближённых решений.
Ключевые слова:расписание, идентичные детали, NP-трудность, псевдополиномиальный алгоритм, теория сложности.
Полный текст:
PDF файл (1626 kB)