ENRU
English version: Journal of Applied and Industrial Mathematics, 2017, 11:1, 1725 

Volume 24, No 1, 2017, P. 520 UDC 519.8
Keywords: cyclic schedule, dynamic programming, pseudopolynomial algorithm. DOI: 10.17377/daio.2017.24.500 Ekaterina A. Bobrova ^{1} Received 3 July 2015 References[1] E. A. Bobrova, A. A. Romanova, and V. V. Servakh, The complexity of cyclic scheduling for identical jobs, Diskretn. Anal. Issled. Oper., 20, No. 4, 3–14, 2013 [Russian].[2] A. A. Romanova and V. V. Servakh, Optimization of processing identical jobs by means of cyclic schedules, Diskretn. Anal. Issled. Oper., 15, No. 5, 47–60, 2008 [Russian]. Translated in J. Appl. Ind. Math., 3, No. 4, 496–504, 2009. [3] V. V. Servakh, An effectively solvable case of a project scheduling problem with renewable resources, Diskretn. Anal. Issled. Oper., Ser. 2, 7, No. 1, 75–82, 2000 [Russian]. [4] V. G. Timkovsky, Approximate solution of schedule construction problem for cyclic system, Ekon. Mat. Metody, 22, No. 1, 171–174, 1986 [Russian]. [5] T. Boudoukh, M. Penn, and G. Weiss, Jobshop — an application of fluid approximation, in Proc. 10th Conf. Ind. Eng. Manag., Haifa, Israel, June 10–12, 1998, pp. 254–258, Isr. Inst. Technol., Haifa, 1998 [Hebrew]. [6] T. Boudoukh, M. Penn, and G. Weiss, Scheduling jobshops with some identical or similar jobs, J. Sched., 4, No. 4, 177–199, 2001. [7] P. Brucker, Scheduling Algorithms, Springer, Heidelberg, 2007. [8] N. G. Hall, T. E. Lee, and M. E. Posner, The complexity of cyclic shop scheduling problems, J. Sched., 5, No. 4, 307–327, 2002. [9] C. Hanen, Study of a NPhard cyclic scheduling problem: The recurrent jobshop, Eur. J. Oper. Res., 72, No. 1, 82–101, 1994. [10] H. Kamoun and C. Sriskandarajah, The complexity of scheduling jobs in repetitive manufacturing systems, Eur. J. Oper. Res., 70, No. 3, 350–364, 1993. [11] E. Levner, V. Kats, D. Pablo, and E. Cheng, Complexity of cyclic scheduling problems: A stateoftheart survey, Comput. Ind. Eng., 59, No. 2, 352–361, 2010. [12] S. T. McCormick and U. S. Rao, Some complexity results in cyclic scheduling, Math. Comput. Model., 20, No. 2, 107–122, 1994. [13] U. S. Rao and P. L. Jackson, Subproblems in identical jobs cyclic scheduling: Properties, complexity and solution approaches, Tech. Rep., Cornell Univ., Ithaca, NY, USA, 1993. Available at http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.45.3814. Accessed Oct. 5, 2016. [14] R. Roundy, Cyclic schedules for job shops with identical jobs, Math. Oper. Res., 17, No. 4, 842–865, 1992. [15] V. V. Servakh, A dynamic algorithm for some project management problems, in Proc. Int. Workshop “Discrete Optimization Methods in Scheduling and ComputerAided Design”, Minsk, Belarus, Sept. 5–6, pp. 90–92, Inst. Eng. Cybern. NAS Belarus, Minsk, 2000. [16] V. G. Timkovsky, Cycle shop scheduling, in Handbook of Scheduling: Algorithms, Models, and Performance Analysis, pp. 127–148, CRC Press, Boca Raton, 2004. 

© Sobolev Institute of Mathematics, 2015  