Том 4, серия 1, номер 1, 1997 г., Стр. 13-32
УДК 519.854
К. Н. Каширских, К. Н. Поттс, С. В. Севастьянов
Улучшенный алгоритм решения двухмашинной задачи flow shop
Аннотация:
Для задачи flow shop с двумя машинами и неодновременным поступлением работ представлен алгоритм трудоемкости$O(n^3\log n)$ для нахождения приближенного решения с относительной погрешностью (т. е. отношением длины полученного расписания к длине оптимального расписания), не превосходящей 3/2. Тем самым улучшены характеристики алгоритма одного из авторов (Поттс, 1985), решающего эту задачу с относительной погрешностью 5/3 при той же оценке трудоемкости.
Ил. 2, табл. 1, библиогр. 7.
Каширских К. Н. 1
Поттс К. Н. 2
Севастьянов С. В. 3
1. Новосибирский гос. университет,
ул. Пирогова, 2, 630090 Новосибирск, Россия
2. University of Southampton,
Southampton S09 5NH UK
3.
Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
е-mail: cnp@maths.soton.ac.uk, seva@math.nsc.ru
Статья поступила 19 декабря 1996 г.
