English version:
Journal of Applied and Industrial Mathematics, 2016, 10:4, 494-504

Volume 23, No 4, 2016, P. 5-25

UDC 519.8
A. V. Kononov and P. A. Kononova
On minimizing dataset transfer time in an acyclic network with four servers

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, polynomial time algorithm, NP-hardness.

DOI: 10.17377/daio.2016.23.525

Alexander V. Kononov 1,2
Polina A. Kononova 1,2

1. Sobolev Institute of Mathematics,
4 Koptyug Ave., 630090 Novosibirsk, Russia
2. Novosibirsk State University,
2 Pirogov St., 630090 Novosibirsk, Russia
e-mail: alvenko@math.nsc.ru, polik83@ngs.ru

Received 4 February 2016
Revised 24 June 2016


[1] M. R. Garey and D. S. Johnson, Computers and Intractability: A Guideto the Theory of NP-Completeness, Freeman, San Francisco, 1979. Translated under the title Vychislitel’nye mashiny i trudnoreshaemye zadachi, Mir, Moscow, 1982.

[2] V. S. Tanaev, Yu. N. Sotskov, and V. A. Strusevich, Teoriya raspisanii: Mnogostadiinye sistemy, Nauka, Moscow, 1989. Translated under the title Scheduling Theory. Multi-Stage Systems, Kluwer Acad. Publ., Dordrecht, 1994 (Math. Its Appl., Vol. 285).

[3] A. K. Amoura, E. Bampis, C. Kenyon, and Y. Manoussakis, Scheduling independent multiprocessor tasks, Algorithmica, 32, No. 2, 247–261, 2002.

[4] B. Chen, C. N. Potts, and G. J. Woeginger, A review of machine scheduling: complexity, algorithms and approximability, in D.-Z. Du and P. M. Pardalos (eds.), Handbook of Combinatorial Optimization, Vol. 3, pp. 21–169, Kluwer Acad. Publ., Dordrecht, 1998.

[5] C. Bierwirth and F. Meisel, A survey of berth allocation and quay crane scheduling problems in container terminals, Eur. J. Oper. Res., 244, No. 3, 675–689, 2015.

[6] J. Blazewicz, P. Dell’Olmo, M. Drozdowski, and M. G. Speranza, Scheduling multiprocessor task on three dedicated processors, Inf. Process. Lett., 41, No. 5, 275–280, 1992.

[7] A. L. Buchsbaum, H. Karloff, C. Kenyon, N. Reingold, and M. Thorup, OPT versus LOAD in dynamic storage allocation, SIAM J. Comput., 33, No. 3, 632–646, 2012.

[8] H. W. Chun, Scheduling as a multi-dimensional placement problem, Eng. Appl. Artif. Intell., 9, No. 3, 261–273, 1996.

[9] M. Drozdowski, Scheduling for Parallel Processing, Springer, London, 2009 (Comput. Commun. Netw.).

[10] C. W. Duin and E. V. Sluis, On the complexity of adjacent resource scheduling, J. Sched., 9, No. 1, 49–62, 2006.

[11] G. Even, M. M. Halldersson, L. Kaplan, and D. Ron, Scheduling with conflicts: Online and offline algorithms, J. Sched., 12, No. 2, 199–224, 2009.

[12] J. A. Hoogeveen, S. L. van de Velde, and B. Veltman, Complexity of scheduling multiprocessor task with prespecified processor allocations, Discrete Appl. Math., 55, No. 3, 259–272, 1994.

[13] A. Lim, The berth planning problem, Oper. Res. Lett., 22, No. 2–3, 105–110, 1998.

[14] J. J. Paulus and J. Hurink, Adjacent-resource scheduling: Why spatial resources are so hard to
incorporate, Electron. Notes Discrete Math., 25, 113–116, 2006.

 © Sobolev Institute of Mathematics, 2015