Geodesic
On minimizing dataset transfer time in an acyclic network with four servers
Diskretnyj analiz i issledovanie operacij, Tome 23 (2016) no. 4, pp. 5-25.

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

Under consideration is some optimization problem of data transmission in a hierarchical acyclic network. This problem is a special case of the makespan minimization problem with multiprocessor jobs on dedicated machines.We study computational complexity of the subproblems with a specific set of job types, where the type of a job is a subset of the machines required by the job. Ill. 17, bibliogr. 14.
Keywords: multiprocessor scheduling, NP-hardness.
Mots-clés : polynomial time algorithm 
@article{DA_2016_23_4_a0,
     author = {A. V. Kononov and P. A. Kononova},
     title = {On minimizing dataset transfer time in an acyclic network with four servers},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {5--25},
     publisher = {mathdoc},
     volume = {23},
     number = {4},
     year = {2016},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2016_23_4_a0/}
}
TY  - JOUR
AU  - A. V. Kononov
AU  - P. A. Kononova
TI  - On minimizing dataset transfer time in an acyclic network with four servers
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2016
SP  - 5
EP  - 25
VL  - 23
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2016_23_4_a0/
LA  - ru
ID  - DA_2016_23_4_a0
ER  - 
%0 Journal Article
%A A. V. Kononov
%A P. A. Kononova
%T On minimizing dataset transfer time in an acyclic network with four servers
%J Diskretnyj analiz i issledovanie operacij
%D 2016
%P 5-25
%V 23
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2016_23_4_a0/
%G ru
%F DA_2016_23_4_a0
A. V. Kononov; P. A. Kononova. On minimizing dataset transfer time in an acyclic network with four servers. Diskretnyj analiz i issledovanie operacij, Tome 23 (2016) no. 4, pp. 5-25. http://geodesic.mathdoc.fr/item/DA_2016_23_4_a0/

[1] M. R. Garey, D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, San Francisco, 1979 | MR | MR | Zbl

[2] V. S. Tanaev, Yu. N. Sotskov, V. A. Strusevich, Scheduling Theory. Multi-Stage Systems, Math. Its Appl., 285, Kluwer Acad. Publ., Dordrecht, 1994 | MR | MR | Zbl

[3] Amoura A. K., Bampis E., Kenyon C., Manoussakis Y., “Scheduling independent multiprocessor tasks”, Algorithmica, 32:2 (2002), 247–261 | DOI | MR | Zbl

[4] Bo Chen, Potts C. N., Woeginger G. J., “A review of machine scheduling: complexity, algorithms and approximability”, Handbook of combinatorial optimization, v. 3, eds. D.-Z. Du, P. M. Pardalos, Kluwer Acad. Publ., Amsterdam, 1998, 21–169 | MR | Zbl

[5] Bierwirth C., Meisel F., “A survey of berth allocation and quay crane scheduling problems in container terminals”, Eur. J. Oper. Res., 244:3 (2015), 675–689 | DOI | MR | Zbl

[6] Blazewicz J., Dell'Olmo P., Drozdowski M., Speranza M. G., “Scheduling multiprocessor tasks on three dedicated processors”, Inf. Process. Lett., 41 (1992), 257–280 | DOI | MR

[7] Buchsbaum A. L., Karloff H., Kenyon C., Reingold N., Thorup M., “OPT versus LOAD in dynamic storage allocation”, SIAM J. Comput., 33:3 (2012), 632–646 | DOI | MR

[8] Chun H. N., “Scheduling as a multidimensional placement problem”, Engineering Appl. Artificial Intellegence, 9 (1996), 261–273 | DOI

[9] Drozdowski M., Scheduling for parallel processing, Comput. Commun. Netw., Springer-Verl., London, 2009, 386 pp. | DOI | MR | Zbl

[10] Duin C. W., Sluis E. V., “On the complexity of adjacent resource scheduling”, J. Scheduling, 9:1 (2006), 49–62 | DOI | MR | Zbl

[11] Even G., Halldersson M. M., Kaplan L., Ron D., “Scheduling with conflicts: online and offline algorithms”, J. Scheduling, 12:2 (2009), 199–224 | DOI | MR | Zbl

[12] Hoogeveen J. A., van de Velde S. L., Veltman B., “Complexity of scheduling multiprocessor task with prespecified processor allocations”, Discrete Appl. Math., 55:3 (1994), 259–272 | DOI | MR | Zbl

[13] Lim A., “The berth planning problem”, Oper. Res. Lett., 22:2–3 (1998), 105–110 | DOI | MR | Zbl

[14] Paulus J. J., Hurink J., “Adjacent-resource scheduling. Why spatial resources are so hard to incorporate”, Electron. Notes Discrete Math., 25 (2006), 113–116 | DOI | MR | Zbl