Том 13, серия 2, номер 2, 2006 г., Стр. 44-55
УДК 519.854
В. В. Сервах
Полиномиально разрешимый случай трехстаночной задачи Джонсона
Аннотация:
Рассматривается классическая NP-трудная задача трёх станков: за минимальное время необходимо обработать $N$ деталей на трёх станках. Времена обработки деталей на каждом станке заданы. Технологические маршруты всех деталей одинаковы. Одновременная обработка двух деталей на одном станке невозможна. В работе исследуются свойства этой задачи. Выделен новый полиномиально разрешимый случай, описан соответствующий алгоритм.
Библ. 6.
Сервах В. В. 1
1. Омский филиал Института математики им. С. Л. Соболева СО РАН,
ул. Певцова, 13, 644099 Омск, Россия
е-mail: svv@iitam.omsk.net.ru
Статья поступила 18 июля 2006 г.
