Geodesic
Ant colony algorithm for single processor scheduling with minimization of peak resource usage
Diskretnyj analiz i issledovanie operacij, Tome 31 (2024) no. 2, pp. 5-27 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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.
Keywords: combinatorial optimization, single-processor schedule, resource minimization, ant colony algorithm. 
@article{DA_2024_31_2_a0,
     author = {V. V. Balashov and A. V. Abramov and A. A. Chupakhin and A. V. Turkin and J. Gao and C. Sun and L. Zhou and J. Sun},
     title = {Ant colony algorithm for~single~processor~scheduling with~minimization of peak resource usage},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {5--27},
     year = {2024},
     volume = {31},
     number = {2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2024_31_2_a0/}
}
TY  - JOUR
AU  - V. V. Balashov
AU  - A. V. Abramov
AU  - A. A. Chupakhin
AU  - A. V. Turkin
AU  - J. Gao
AU  - C. Sun
AU  - L. Zhou
AU  - J. Sun
TI  - Ant colony algorithm for single processor scheduling with minimization of peak resource usage
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2024
SP  - 5
EP  - 27
VL  - 31
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/DA_2024_31_2_a0/
LA  - ru
ID  - DA_2024_31_2_a0
ER  - 
%0 Journal Article
%A V. V. Balashov
%A A. V. Abramov
%A A. A. Chupakhin
%A A. V. Turkin
%A J. Gao
%A C. Sun
%A L. Zhou
%A J. Sun
%T Ant colony algorithm for single processor scheduling with minimization of peak resource usage
%J Diskretnyj analiz i issledovanie operacij
%D 2024
%P 5-27
%V 31
%N 2
%U http://geodesic.mathdoc.fr/item/DA_2024_31_2_a0/
%G ru
%F DA_2024_31_2_a0
V. V. Balashov; A. V. Abramov; A. A. Chupakhin; A. V. Turkin; J. Gao; C. Sun; L. Zhou; J. Sun. Ant colony algorithm for single processor scheduling with minimization of peak resource usage. Diskretnyj analiz i issledovanie operacij, Tome 31 (2024) no. 2, pp. 5-27. http://geodesic.mathdoc.fr/item/DA_2024_31_2_a0/

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

[2] Abdel-Wahab H. M., Scheduling with applications to register allocation and deadlock problems, PhD Thes., Univ. Waterloo, Waterloo, ON, 1976, 440 pp.

[3] Sethi R., “Complete register allocation problems”, SIAM J. Comput., 4:3 (1975), 226–248 | DOI | MR | Zbl

[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., 8:2 (2000), 125–141 | MR | Zbl

[5] E. R. Gafarov, “A hybrid algorithm for solution to the total delay minimization problem with one device”, Inf. Tekhnol., 2007, no. 1, 30–37 (Russian)

[6] Jha S., “Balanced ant colony algorithm for scheduling DAG to grid heterogeneous system”, Int. J. Sci. Eng. Res., 2:6 (2011), 10 pp.

[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, 3599–3619 | DOI

[8] V. A. Kostenko and A. V. Plakunov, “Ant algorithms for scheduling computations in data centers”, Mosc. Univ. Comput. Math. Cybern., 41:1 (2017), 44–50 | DOI | MR | Zbl

[9] Gagne C., Price W. L., Grave M., “Comparing an ACO algorithm with other heuristics for the single machine scheduling problem with sequence-dependent setup times”, J. Oper. Res. Soc., 53 (2002), 895–906 | DOI | Zbl

[10] Gurobi optimizer. Gurobi optimization, , 2023 (accessed Mar. 22, 2024) www.gurobi.com/solutions/gurobi-optimizer

[11] MOSEK solver. MOSEK ApS, , 2023 (accessed Mar. 22, 2024) www.mosek.com/products/mosek

[12] SCIP: Solving Constraint Integer Programs, Zuse Inst. Berlin, Berlin, 2023 (accessed Mar. 22, 2024) www.scipopt.org

[13] COIN-OR: Computations Infrastructure for Operations Research. Projects by Category, COIN-OR Found., Towson, 2023 (accessed Mar. 22, 2024) www.coin-or.org/projects

[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., 2 (2012), 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), Lect. Notes Comput. Sci., 1742, Springer, Heidelberg, 1999, 359–370 | DOI | MR

[16] Kayaaslan E., Lambert T., Marchal L., Uçar B., “Scheduling series-parallel task graphs to minimize peak memory”, Theor. Comput. Sci., 707 (2018), 1–23 | DOI | MR | Zbl

[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), Lect. Notes Comput. Sci., 11725, Springer, Cham, 2019, 61–73 | DOI | Zbl