Geodesic
Optimization of identical jobs production on the base of cyclic schedules
Diskretnyj analiz i issledovanie operacij, Tome 15 (2008) no. 5, pp. 47-60.

Voir la notice de l'article provenant de la source Math-Net.Ru

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. 
@article{DA_2008_15_5_a4,
     author = {A. A. Romanova and V. V. Servakh},
     title = {Optimization of identical jobs production on the base of cyclic schedules},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {47--60},
     publisher = {mathdoc},
     volume = {15},
     number = {5},
     year = {2008},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2008_15_5_a4/}
}
TY  - JOUR
AU  - A. A. Romanova
AU  - V. V. Servakh
TI  - Optimization of identical jobs production on the base of cyclic schedules
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2008
SP  - 47
EP  - 60
VL  - 15
IS  - 5
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2008_15_5_a4/
LA  - ru
ID  - DA_2008_15_5_a4
ER  - 
%0 Journal Article
%A A. A. Romanova
%A V. V. Servakh
%T Optimization of identical jobs production on the base of cyclic schedules
%J Diskretnyj analiz i issledovanie operacij
%D 2008
%P 47-60
%V 15
%N 5
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2008_15_5_a4/
%G ru
%F DA_2008_15_5_a4
A. A. Romanova; V. V. Servakh. Optimization of identical jobs production on the base of cyclic schedules. Diskretnyj analiz i issledovanie operacij, Tome 15 (2008) no. 5, pp. 47-60. http://geodesic.mathdoc.fr/item/DA_2008_15_5_a4/

[1] Gens G. V., Levner E. V., Effektivnye priblizhënnye algoritmy dlya kombinatornykh zadach, Preprint, TsEMI, M., 1981, 38 pp.

[2] Servakh V. V., “Effektivno razreshimyi sluchai zadachi kalendarnogo planirovaniya s vozobnovimymi resursami”, Diskret. analiz i issled. operatsii. Ser. 2, 7:1 (2000), 75–82 | MR | Zbl

[3] Aldakhilallah K. A., Ramesh R., “Cyclic scheduling heuristics for a re-entrant job shop manufacturing environment”, Internat. J. Production Research, 39 (2001), 2635–2675 | DOI

[4] Akers S. E., “A graphical approach to production scheduling problems”, Operations Research, 4:2 (1956), 244–245 | DOI

[5] Boudoukh T., Penn M., Weiss G., “Scheduling job shops with some identical or similar jobs”, J. Scheduling, 4 (2001), 177–199 | DOI | MR | Zbl

[6] Brucker P., Kampmeyer T., Tabu search algorithms for cyclic machine scheduling problems, Preprint, Osnabrueck, 2002, 24 pp. | MR

[7] Hall N. G., Lee T. E., Posner M. E., “The complexity of cyclic shop scheduling problems”, J. Scheduling, 5 (2002), 307–327 | DOI | MR | Zbl

[8] Hanen C., “Study of a NP-hard cyclic scheduling problem: the recurrent job-shop”, Europ. J. Operational Research, 71 (1994), 82–101 | DOI

[9] Hardgrave W. W., Nemhauser G. L., “A geometric model and a graphical algorithm for a sequencing problem”, Operations Research, 11:6 (1963), 889–900 | DOI | Zbl

[10] Ibarra O. H., Kim C. E., “Fast approximation algorithms for the knapsack and sum of subset problems”, J. Assoc. Comput. Mach., 22:4 (1975), 463–468 | MR | Zbl

[11] Kamoun H., Sriskandarajah C., “The complexity of scheduling jobs in repetitive manufacturing systems”, Europ. J. Operational Research, 70 (1993), 350–364 | DOI | Zbl

[12] Lee T., Posner M., “Performance measure and schedules in periodic job shop”, Operations Research, 45 (1997), 72–91 | DOI | Zbl

[13] McCormick S. T., Rao U. S., “Some complexity results in cyclic scheduling”, Mathematical and Computer Modelling, 20 (1994), 107–122 | DOI | MR | Zbl

[14] Rao U., Jackson P., Identical jobs cyclic scheduling: subproblems, properties, complexity and solution approaches, Cornell Univ. Press, Ithaca, NY, 1993, 47 pp. | Zbl

[15] Romanova A. A., Servakh V. V., “On some cyclic machine scheduling problem”, Abstracts of the XVII European Conference of Combinatorial Optimization (ECCO' 2005), United Institute of Informatics Problems of the National Academy of Sciences of Belarus, Minsk, 2005, 58–59

[16] Roundy R., “Cyclic schedules for job shops with identical jobs”, Mathematics of Operations Research, 17:4 (1992), 842–865 | DOI | MR | Zbl

[17] Servakh V. V., “A dynamic algorithm for some project management problems”, Proceedings of the International Workshop “Discrete optimization methods in scheduling and computer-aided design”, National Academy of Sciences of Belarus Institute of Engineering Cybernetics, Minsk, 2005, 90–92