Volume 15, No 5, 2008, P. 47-60
UDC 519.2+621.391
A. A. Romanova, V. V. Servakh
Optimization of identical jobs production on the base of cyclic schedules
Abstract:
Some cyclic job shop problems with identical jobs are researched. An exact algorithm for one of these problems based on the dynamic programming is proposed. We construct a fully polynomial time approximation scheme in the special case, when the number of simultaneously processing jobs is fixed.
Illustr. 1, bibl. 17.
Keywords: cyclic schedule, identical jobs, dynamic programming, approximation scheme.
Romanova Anna Anatoljevna 1
Servakh Vladimir Vicentjevich 2
1. F. M. Dostoevski Omsk State University,
55a Mira ave., 644077 Omsk, Russia
2.
Omsk Branch of S. L. Sobolev Institute of Mathematics, SB RAS,
13 Pevtsova str., 644099 Omsk, Russia
e-mail: svv_usa@rambler.ru, romanova_ann@bk.ru
