Муравьиный алгоритм для построения однопроцессорного расписания с минимизацией пикового использования ресурса

Муравьиный алгоритм для построения однопроцессорного расписания с минимизацией пикового использования ресурса

Балашов В. В., Абрамов А. В., Чупахин А. А., Туркин А. В., Гао Ц., Сунь Ш., Чжоу Л., Сунь Ц.
Дискретный анализ и исследование операций, 31, 2, 5-27 (2024)
Скачать статью

УДК 519.854.2 
DOI: 10.33048/daio.2024.31.760

Аннотация:

Рассматривается задача построения однопроцессорного расписания с минимизацией пикового использования ресурса вычислителя. В качестве ресурса может выступать оперативная память. Набор заданий для планирования представлен в виде ориентированного ациклического графа, в каждой вершине которого указан объём занимаемого соответствующим заданием ресурса. Высвобождение ресурса, выделенного заданию, происходит по завершении последнего (согласно расписанию) непосредственного потомка этого задания в графе. Ограничением корректности на расписание является соблюдение частичного порядка, определённого графом заданий. Длительности заданий не рассматриваются. Приводится формальная постановка задачи. В качестве алгоритма для её решения предлагается муравьиный алгоритм, модифицированный так, что матрица феромона отражает желательность взаимного расположения (порядка) в расписании для любой пары заданий, а не только для пар соседних заданий. При построении расписания алгоритм для каждого задания выбирает его позицию в расписании, в отличие от известных муравьиных алгоритмов, которые строят расписание в порядке увеличения номеров позиций («слева направо») и для каждой очередной позиции выбирают задание. Выполнено экспериментальное исследование алгоритма на двух наборах заданий. Графы из первого набора построены так, чтобы априорно была известна оценка оптимального значения целевой функции. Графы из второго набора «слоистые», что соответствует структуре приложений по многостадийной обработке данных. В рамках каждого из наборов графы сформированы случайным образом, с соблюдением заданных параметров генерации и ограничений на структуру графа. Экспериментальное исследование показало высокую точность и стабильность предложенного муравьиного алгоритма. 
Табл. 1, ил. 12, библиогр. 17.

Литература:
  1. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982. 416 с.
     
  2. Abdel-Wahab H. M. Scheduling with applications to register allocation and deadlock problems: PhD Thes. Waterloo, ON: Univ. Waterloo, 1976. 440 p.
     
  3. Sethi R. Complete register allocation problems // SIAM J. Comput. 1975. V. 4, No. 3. P. 226–248.
     
  4. Bauer A., Straus C., Hartle R. F. Minimizing total tardiness on a single machine using ant colony optimization // Cent. Eur. J. Oper. Res. Econ. 2000. V. 8, No. 2. P. 125–141.
     
  5. Гафаров Е. Р. Гибридный алгоритм решения задачи минимизации суммарного запаздывания для одного прибора // Информ. технологии. 2007. № 1. С. 30–37.
     
  6. Jha S. Balanced ant colony algorithm for scheduling DAG to grid heterogeneous system // Int. J. Sci. Eng. Res. 2011. V. 2, No. 6. 10 p.
     
  7. Myszkowski P., Skowronski M., Olech L., Oslizlo K. Hybrid ant colony optimization in solving multi-skill resource-constrained project scheduling problem // Soft Comput. 2015. No. 19. P. 3599–3619.
     
  8. Костенко В. А., Плакунов А. В. Муравьиные алгоритмы для планирования вычислений в центрах обработки данных // Вестн. Моск. ун-та. Сер. 15. Вычисл. математика и кибернетика. 2017. № 1. С. 44–50. 
     
  9. Gagne C., Price W. L., Grave M. Comparing an ACO algorithm with other heuristics for the single machine scheduling problem with sequencedependent setup times // J. Oper. Res. Soc. 2002. V. 53. P. 895–906.
     
  10. Gurobi optimizer. Gurobi optimization, 2023. URL: www.gurobi.com/solutions/gurobi-optimizer (accessed Mar. 22, 2024).
     
  11. MOSEK solver. MOSEK ApS, 2023. URL: www.mosek.com/products/mosek (accessed Mar. 22, 2024).
     
  12. SCIP: Solving Constraint Integer Programs. Berlin: Zuse Inst. Berlin, 2023. URL: www.scipopt.org (accessed Mar. 22, 2024).
     
  13. COIN-OR: Computations Infrastructure for Operations Research. Projects by Category. Towson: COIN-OR Found., 2023. URL: www.coin-or.org/projects (accessed Mar. 22, 2024).
     
  14. Xuan H. H., Linh-Trung N., Dong D. D., Huynh T. Solving the Traveling Salesman Problem with ant colony optimization: A revisit and new efficient algorithms // J. Electron. Commun. 2012. V. 2. P. 121–129.
     
  15. Tong C. J., Lau H. C., Lim A. Ant colony optimization for the Ship Berthing Problem // Advances in computing science — ASIAN’99. Proc. 5th Asian Computing Science Conf. (Phuket, Thailand, Dec. 10–12, 1999). Heidelberg: Springer, 1999. P. 359–370. (Lect. Notes Comput. Sci.; V. 1742). DOI: 10.1007/3-540-46674-6_30. 
     
  16. Kayaaslan E., Lambert T., Marchal L., Uçar B. Scheduling series-parallel task graphs to minimize peak memory // Theor. Comput. Sci. 2018. V. 707. P. 1–23.
     
  17. Canon L.-C., El Sayah M., Héam P.-C. A comparison of random task graph generation methods for scheduling problems // Euro-Par 2019: Parallel processing. Proc. 25th Int. Conf. Parallel and Distributed Computing (Göttingen, Germany, Aug. 26–30, 2019). Cham: Springer, 2019. P. 61–73. (Lect. Notes Comput. Sci.; V. 11725). DOI: 10.1007/978-3-030-29400-7_5.

Исследование выполнено за счёт бюджетов организаций, обозначенных авторами на первой странице статьи. Дополнительных грантов на проведение или руководство этим исследованием получено не было.

Балашов Василий Викторович
  1. Московский гос. университет им. М. В. Ломоносова, 
    Ленинские горы, 1, 119991 Москва, Россия

E-mail: hbd@cs.msu.ru

Абрамов Алексей Владимирович
  1. Московский гос. университет им. М. В. Ломоносова, 
    Ленинские горы, 1, 119991 Москва, Россия

E-mail: avabramov@lvk.cs.msu.ru

Чупахин Андрей Андреевич
  1. Московский гос. университет им. М. В. Ломоносова, 
    Ленинские горы, 1, 119991 Москва, Россия

E-mail: andrewchup@lvk.cs.msu.ru

Туркин Андрей Владимирович
  1. Московский исследовательский центр Хуавэй, 
    Смоленская пл., 7-9, 121099 Москва, Россия

E-mail: andrei.turkin@huawei.com

Гао Цзесин
  1. Московский исследовательский центр Хуавэй, 
    Смоленская пл., 7-9, 121099 Москва, Россия

E-mail: gaojiexing@huawei.com

Сунь Шумин
  1. Гонконгский исследовательский центр Хуавэй, 
    Сайнс Парк Вест Авеню, 2, 8/F, 999077 Гонконг, КНР

E-mail: sunchumin@huawei.com

Чжоу Ли
  1. Гонконгский исследовательский центр Хуавэй, 
    Сайнс Парк Вест Авеню, 2, 8/F, 999077 Гонконг, КНР

E-mail: zhouli107@huawei.com

Сунь Цзе
  1. Гонконгский исследовательский центр Хуавэй, 
    Сайнс Парк Вест Авеню, 2, 8/F, 999077 Гонконг, КНР

E-mail: j.sun@huawei.com

Статья поступила 19 декабря 2022 г. 
После доработки — 25 октября 2023 г. 
Принята к публикации 22 декабря 2023 г.

Abstract:

We consider the problem of constructing a single processor task schedule with minimization of peak resource usage. An example of the resource is the main memory of the target computer. Task set to be scheduled is represented as a directed acyclic graph every node of which is marked with the amount of resource used by the corresponding task. The resource allocated to a task is released on completion of the last (according to the schedule) immediate successor of this task in the graph. Correctness constraint on the schedule is the partial order specified by the task graph. Task duration values are not considered. The formal statement of the problem is provided. To solve the problem, we propose an ant colony algorithm modified so that the pheromone matrix reflects the desirability of pairwise order in the schedule for every pair of tasks, not only for pairs of adjacent tasks. During the schedule construction, for every task the algorithm chooses its position in the schedule, in contrast to existing ant colony scheduling algorithms that construct schedule in increasing order of positions (left-to-right) choosing a task for every next position. Experimental evaluation of the algorithm was conducted on two sets of task graphs. The first set contains graphs generated in such a way that the estimation for the optimum value of the goal function is known a priori. Graphs from the second set are “layered,” and their structure corresponds to the structure of multistage data processing applications. In both sets, the graphs are generated randomly with respect to specified generation parameters and constraints on the graph structure. The experiments indicate high precision and stability of the proposed ant colony algorithm. 
Tab. 1, illustr. 12, bibliogr. 17.

References:
  1. M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (Freeman, San Francisco, 1979; Mir, Moscow, 1982 [Russian]).
     
  2. H. M. Abdel-Wahab, Scheduling with applications to register allocation and deadlock problems, PhD Thesis (Univ. Waterloo, Waterloo, ON, 1976).
     
  3. R. Sethi, Complete register allocation problems, SIAM J. Comput. 4 (3), 226–248 (1975).
     
  4. A. Bauer, C. Straus, and R. F. Hartle, Minimizing total tardiness on a single machine using ant colony optimization, Cent. Eur. J. Oper. Res. Econ. 8 (2), 125–141 (2000).
     
  5. E. R. Gafarov, A hybrid algorithm for solution to the total delay minimization problem with one device, Inf. Tekhnol., No. 1, 30–37 (2007) [Russian].
     
  6. S. Jha, Balanced ant colony algorithm for scheduling DAG to grid heterogeneous system, Int. J. Sci. Eng. Res. 2 (6) (2011).
     
  7. P. Myszkowski, M. Skowronski, L. Olech, and K. Oslizlo, Hybrid ant colony optimization in solving multi-skill resource-constrained project scheduling problem, Soft Comput., No. 19, 3599–3619 (2015).
     
  8. V. A. Kostenko and A. V. Plakunov, Ant algorithms for scheduling computations in data centers, Vestn. Mosk. Univ., Ser. 15, No. 1, 44–50 (2017) [Russian] [Mosc. Univ. Comput. Math. Cybern. 41 (1), 44–50 (2017)].
     
  9. C. Gagne, W. L. Price, and M. Grave, Comparing an ACO algorithm with other heuristics for the single machine scheduling problem with sequencedependent setup times, J. Oper. Res. Soc. 53, 895–906 (2002).
     
  10. Gurobi Optimizer (Gurobi Optimization, 2023), URL: www.gurobi.com/solutions/gurobi-optimizer (accessed Mar. 22, 2024).
     
  11. MOSEK Solver (MOSEK ApS, 2023), URL: www.mosek.com/products/mosek (accessed Mar. 22, 2024).
     
  12. SCIP: Solving Constraint Integer Programs (Zuse Inst. Berlin, Berlin, 2023), URL: www.scipopt.org (accessed Mar. 22, 2024).
     
  13. COIN-OR: Computations Infrastructure for Operations Research. Projects by Category (COIN-OR Found., Towson, 2023), URL: www.coin-or.org/projects (accessed Mar. 22, 2024).
     
  14. H. H. Xuan, N. Linh-Trung, D. D. Dong, and T. Huynh, Solving the Traveling Salesman Problem with ant colony optimization: A revisit and new efficient algorithms, J. Electron. Commun. 2, 121–129 (2012).
     
  15. C. J. Tong, H. C. Lau, and A. Lim, Ant colony optimization for the Ship Berthing Problem, in Advances in Computing Science — ASIAN’99 (Proc. 5th Asian Computing Science Conf., Phuket, Thailand, Dec. 10–12, 1999) (Springer, Heidelberg, 1999), pp. 359–370 (Lect. Notes Comput. Sci., Vol. 1742), DOI: 10.1007/3-540-46674-6_30.
     
  16. E. Kayaaslan, T. Lambert, L. Marchal, and B. Uçar, Scheduling seriesparallel task graphs to minimize peak memory, Theor. Comput. Sci. 707, 1–23 (2018).
     
  17. L.-C. Canon, Sayah M. El, and P.-C. Héam, A comparison of random task graph generation methods for scheduling problems, in Euro-Par 2019: Parallel Processing (Proc. 25th Int. Conf. Parallel and Distributed Computing, Göttingen, Germany, Aug. 26–30, 2019) (Springer, Cham, 2019), pp. 61–73 (Lect. Notes Comput. Sci., Vol. 11725), DOI: 10.1007/978-3-030-29400-7_5.