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

Abstract:
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

References

[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.