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

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.ruromanova_ann@bk.ru

 © Sobolev Institute of Mathematics, 2015