ACO and PSO Methods to Solve Single Machine Scheduling Problems

Finding the sequence that yields the best or most efficient solution for a function that combines minimizing the sum of the maximum total late work and the maximum completion time is the primary aim of this study, which focuses on the scheduling problem on a single machine. In certain special cases, the best solution was obtained using exact methods. However, local search strategies like Ant Colony Optimization (ACO) and Particle Swarm Optimization (PSO) were employed to get rough answers and guide the search toward promising regions of the solution space. Comprehensive computational experiments showed that the PSO algorithm efficiently solves instances involving up to 1500 tasks in under ten minutes while maintaining high-quality results. In comparison, the ACO algorithm showed effectiveness for problem sizes of up to 1000 tasks. These results underscore the potential of swarm intelligence techniques in solving complex scheduling problems, particularly when exact methods are computationally expensive or impractical for large-scale cases.

References

[1] Blazewicz J. Scheduchy preemptible task on parallel process with in loss. Rech Tech Sci Inform. 1984;3:415-20.

[2] Potts CN, Van Wassenhove LN. Single machine to minimize total late work. Oper Res. 1991;40(3):586-95.

[3] Hariri AM, Potts CN, Van Wassenhove LN. Single scheduling to minimize weighted total late work. ORSA J Comput. 1995;7(2):232-42. doi:10.1287/ijoc.7.2.232.

[4] Chen R, Yuan J, Ng CT, Cheng TCE. Single-machine scheduling with deadlines to minimize the total weighted late work. Nav Res Logist. 2019;66(7):582-95. doi:10.1002/nav.21869.

[5] Mosheiov G, Oron D, Shabtay D. A no-delay single machine scheduling problem to minimize total weighted early and late work. Optim Lett. 2023;17:2113-31. doi:10.1007/s11590-022-01849-x.

[6] Al Zuwaini MK. A comparative study of local search method for some machine scheduling problems with the usage of hybridizations as a tool [PhD thesis]. Baghdad: University of Baghdad; 2006.

[7] Potts CN, Van Wassenhove LN. Single machine to minimize total late work. Oper Res. 1991;40(3):586-95.

[8] Smith WE. Various optimizers for single stage production. Nav Res Logist Q. 1956;3(1):59-66.

[9] Potts CN, Van Wassenhove LN. Approximation algorithms for scheduling a single machine to minimize total late work. Oper Res Lett. 1992;11(5):261-6.

[10] Dorigo M, Gambardella LM. Ant colony system: a cooperative learning approach to the traveling salesman problem. IEEE Trans Evol Comput. 1997;1(1):53-6.

[11] Blum C, Dorigo M. The hypercube framework for ant colony optimization. IEEE Trans Evol Comput. 2004;34(2):1161-72.

[12] Xiao J, Chen F, Tang J. Review on multi-objective ant colony optimization. J South China Norm Univ (Nat Sci Ed). 2014;46(1):1-6.

[13] Ventresca M, Ombuki BM. Ant colony optimization for job shop scheduling problem. Brock University, Canada, L25-3A1; 2004.

[14] Keivan G, Fahimeh M. ACS-TS: train scheduling using ant colony system. J Appl Math Decis Sci. 2006;95060:1-28.

[15] Kennedy J, Eberhart R. Particle swarm optimization. In: Proceedings of ICNN’95 - International Conference on Neural Networks; 1995 Nov 27-Dec 1; Perth, WA, Australia. Vol 4. Piscataway: IEEE; 1995. p. 1942-8.

[16] Shi Y, Eberhart RC. A modified particle swarm optimizer. In: 1998 IEEE International Conference on Evolutionary Computation Proceedings; 1998 May 4-9; Anchorage, AK, USA. Piscataway: IEEE; 1998. p. 69-73.

[17] Suresh A, Balasubramanie P, Thangavelu A. Task scheduling in cloud computing using modified particle swarm optimization algorithm. Eng Comput. 2020;36(4):1463-75.
doi:10.1007/s12065-019-00216-7.

[18] Zhang J, Wang J, Xu Y. A comprehensive survey on particle swarm optimization algorithm and its applications. Arch Comput Methods Eng. 2021;29:2325-55. doi:10.1007/s11831-021-09694-4.

[19] Zhang X, Li M, Zhao Y. Self-learning particle swarm optimization for integrated production scheduling. Comput Ind Eng. 2024;189:109226. doi:10.1016/j.cie.2024.109226.

How to cite this paper

ACO and PSO Methods to Solve Single Machine Scheduling Problems

How to cite this paper: Asmaa Ali Zeyad, Nada A. Laabi, Wedad Salman Muhammad. (2025) ACO and PSO Methods to Solve Single Machine Scheduling Problems. Scientific Access, 1(1), 26-32.

DOI: http://dx.doi.org/10.26855/sa.2025.06.007

Scientific Access

Journal Menu

Volumes & Issues

Current Issue

More Articles

ACO and PSO Methods to Solve Single Machine Scheduling Problems

Abstract

References

How to cite this paper