Том 23, номер 4, 2016 г., Стр. 5-25

УДК 519.8
Кононов А. В., Кононова П. А.
О минимизации времени передачи пакетов в ациклической сети с четырьмя серверами

Аннотация:
Рассматривается задача оптимизации, которая возникает при передаче пакетов в иерархической ациклической сети. Данная задача является специальным случаем задачи построения кратчайшего расписания многопроцеcсорных работ на специализированных машинах. Изучается комбинаторная сложность её подзадач, характеризующихся фиксированным набором типов работ, где типом работы называется подмножество машин, на котором она выполняется.
Ил. 17, библиогр. 14.

Ключевые слова: многопроцессорное расписание, полиномиальный алгоритм, NP-трудность.

DOI: 10.17377/daio.2016.23.525

Кононов Александр Вениаминович ^1,2
Кононова Полина Александровна ^1,2
1. Институт математики им. С. Л. Соболева,
пр. Коптюга, 4, 630090 Новосибирск, Россия
2. Новосибирский гос. университет,
ул. Пирогова, 2, 630090 Новосибирск, Россия
е-mail: alvenko@math.nsc.ru, polik83@ngs.ru

Статья поступила 4 февраля 2016 г.
Исправленный вариант — 24 июня 2016 г.

Литература

[1] Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982. 416 c.

[2] Танаев В. С., Сотсков Ю. Н., Струсевич В. А. Теория расписаний. Многостадийные системы. М.: Наука, 1989. 329 с.

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

[4] Bo Chen, Potts C. N., Woeginger G. J. A review of machine scheduling: complexity, algorithms and approximability // Handbook of combinatorial optimization (D.-Z. Du and P. M. Pardalos, Eds.). Amsterdam: Kluwer Acad. Publ., 1998. Vol. 3. P. 21–169.

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

[6] Blazewicz J., Dell’Olmo P., Drozdowski M., Speranza M. G. Scheduling multiprocessor tasks on three dedicated processors // Inf. Process. Lett. 1992. Vol. 41. P. 257–280.

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

[8] Chun H. N. Scheduling as a multidimensional placement problem // Engineering Appl. Artificial Intellegence. 1996. Vol. 9. P. 261–273.

[9] Drozdowski M. Scheduling for parallel processing. London: Springer-Verl., 2009. 386 p. (Comput. Commun. Netw).

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

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

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

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

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