Extended tabu search-based scheduling to improve profitability in heterogeneous parallel systems

Document Type : Research Paper

Authors

1 Department of Computer Engineering, Miyaneh Branch, Islamic Azad University, Miyaneh, Iran

2 School of Computer Engineering, Iran University of Science and Technology, Tehran, Iran

Abstract

Higher utilization of existing resources and facilities in order to increase efficiency and profitability is always one of the basic challenges for parallel processing systems and environments, and this challenge becomes more complicated when the system resources are heterogeneous. One way to achieve high efficiency and profitability of heterogeneous parallel systems is to schedule tasks optimally. In this paper, an extended tabu search-based scheduling algorithm (ESTS) is presented to improve the profitability of heterogeneous parallel systems, which can achieve suitable solutions in a short computational time. To evaluate the efficiency of the proposed solution, due to the lack of a suitable criterion to evaluate this problem, the obtained results are compared with both the results of an extended scheduling based on a genetic algorithm (ESGA) with a large number of chromosomes and a high number of generations, as well as an extended scheduling based on a simulated annealing algorithm (ESSA) with a linear temperature reduction. The benchmark files of different sizes were tested under the same conditions, and the comparison of results shows the superiority of the proposed solution in terms of profitability and computational time.

Keywords

Main Subjects

References

[1] Adamuthe, A. C., Bichkar, R. S. (2012). Tabu search for solving personnel scheduling problem. In 2012 International Conference on Communication. Information & Computing Technology (ICCICT). IEEE, 1{6. https://doi:10.1109/ICCICT.2012.6398097.
[2] Alazzam, H., Alhenawi, E., & Al, R. (2019). A hybrid job scheduling algorithm based on tabu and harmony search algorithms. J. Supercomput, 75(12),7994-8011. https://doi:10.1007/s11227-019-02936-0.
[3] Alkhateeb, F., & Abed-alguni, B. H. (2019). A hybrid cuckoo search and simulated annealing algorithm. Journal of Intelligent Systems, 28(4),683-698. https://doi:10.1515/jisys-2017-0268.
[4] Ben Abdellafou, K., Hadda, H., & Korbaa, O. (2019). An improved tabu search meta-heuristic approach for solving scheduling problem with non-availability constraints. Arab. J. Sci. Eng., 44:3369-3379. https://doi:10.1007/s13369-018-3525-3.
[5] Bisht, J., & Vampugani, V. S. (2022). Load and cost-aware min-min work ow scheduling algorithm for heterogeneous resources in fog, cloud, and edge scenarios. International Journal of Cloud Applications and Computing (IJCAC), 12(1),1-20. https://doi:10.4018/IJCAC.2022010105.
[6] Bozejko, W., Nadybski, P., &Wodecki, M., (2017). Two level algorithm with tabu search optimization for task scheduling problem in computing cluster environment. In 2017 22nd International Conference on Methods and Models in Automation and Robotics (MMAR), IEEE, 238{242. https://doi:10.1109/MMAR.2017.8046831.
[7] Bozejko, W., Gnatowski, A., Pempera, J., & Wodecki, M. (2017). Parallel tabu search for the cyclic job shop scheduling problem. Computers & Industrial Engineering, 113:512{524. https://doi:10.1016/j.cie.2017.09.042.
[8] Chandran, R., & Kumar, S. R., (2020). Genetic algorithm-based tabu search for optimal energy-aware allocation of data center resources. Soft Comput., 24(7),1-14. https://doi:10.1007/s00500-020-05240-9.
[9] Chawra, V. K., & Gupta, G. P. (2022). Optimization of the wake-up scheduling using a hybrid of memetic and tabu search algorithms for 3D-wireless sensor networks. International Journal of Software Science and Computational Intelligence (IJSSCI), 14(1), 1-18. https://doi:10.4018/IJSSCI.300359.
[10] Chen, C., Fathi, M., Khaki rooz, M., & Wu, K., (2022). Hybrid tabu search algorithm for unrelated parallel machine scheduling in semiconductor fabs with setup times, job release, and expired times. Comput. Ind. Eng., 165, 1-11. https://doi:10.1016/j.cie.2021.107915.
[11] Chen, L., & Li, X. (2017). Cloud work ow scheduling with hybrid resource provisioning. J. Supercomput., 74, 6529-6553. https://doi:10.1007/s11227-017-2043-5.
 [12] Cruz-Chavez, M. A., Martnez-Rangel, M. G., & Cruz-Rosales, M. H. (2017). Accelerated simulated annealing algorithm applied to the exible job shop scheduling problem. International Transactions in Operational Research, 24(5),1119{1137. https://doi:10.1111/itor.12195.
[13] Dai, H., Cheng, W., & Guo, P., (2018). An improved tabu search for multi-skill resource-constrained project scheduling problems under step-deterioration. Arab. J. Sci. Eng., 43,3279-3290. https://doi:10.1007/s13369-017-3047-4.
[14] Grabowski, J., & Wodecki, M. (2004). A very fast tabu search algorithm for the permutation ow shop problem with makespan criterion. Comput. Oper. Res., 31 (11), 1891-1909. https://doi.org/10.1016/S0305-0548(03)00145-X.
[15] Hajibabaei, M., & Behnamian, J. (2021). Flexible job-shop scheduling problem with unrelated parallel machines and resources-dependent processing times: a tabu search algorithm. Int. J. Manag. Sci. Eng. Manag., 16(4), 242{253. https://doi:10.1080/17509653.2021.1941368.
[16] Huang, K.C., Hung, C. H., & Hsieh, W. (2018). Revenue maximization for scheduling deadline-constrained mouldable jobs on high-performance computing as a service platform. Int. J. High Perform. Comput. Netw., 11(1),1{13. https://doi:10.1504/IJH-PCN.2018.088874.
[17] Juraszek, J., Sterna, M., & Pesch, E. (2009,December). Revenue maximization on parallel machines. Operations Research Proceedings, 0-21. https://doi:10.1007/978-3-642-00142-0.
[18] Krim, H., Zu erey, N., Potvin, J. Y., Benmansour, R., & Duvivier, D. (2022). Tabu search for a parallel-machine scheduling problem with periodic maintenance, job rejection and the weighted sum of completion times. J. Sched., 25, 89-105. https://doi:10.1007/s10951-021-00711-9.
[19] Liu, Y., Meng, L., & Tomiyama, H. (2019). A genetic algorithm for scheduling of data-parallel tasks on multicore architectures. IPSJ Trans. Syst. LSI Des. Methodol., 12, 74{77. https://doi:10.2197/ipsjtsldm.12.74.
[20] Mathlouthi, I., Gendreau, M., & Potvin, J. (2021). A metaheuristic based on tabu search for solving a technician routing and scheduling problem. Comput. Oper. Res., 125, 105079. https://doi:10.1016/j.cor.2020.105079.
[21] Momenikorbekandi, A., & F.Abbod, M. (2023). A novel metaheuristic hybrid parthenogenetic algorithm for job shop scheduling problems: Applying an optimization model. IEEE, 11:56027{56045. https://doi:10.1109/ACCESS.2023.3278372.
[22] Orr, M., & Sinnen, O. (2020). Optimal task scheduling bene ts from a duplicate-free state-space. journal of Parallel and Distributed Computing, 146, 158-174. http://arxiv.org/abs/1901.06899.
[23] Romero, M. A. F., Garca, E. A. R., Ponsich, A. & Gutierrez, R. A. M. (2018). A heuristic algorithm based on tabu search for the solution of exible job shop scheduling problems with lot streaming. In Proceedings of the Genetic and Evolutionary Computation Conference, 285{292. https://doi:10.1145/3205455.3205534.
[24] Singh, R. (2014). Task scheduling in parallel systems using genetic algorithm. Int. J. Comput. Appl., 108(16), 34{40.  https://doi:10.5120/18999-0470.
[25] Singh, S., Kumar, R., & Rao, U. P. (2022). Multi-objective adaptive manta-ray foraging optimization for work
ow scheduling with selected virtual machines using time-series-based prediction. International Journal of Software Science and Computational Intelligence (IJSSCI), 14(1),1-25. https://doi:10.4018/IJSSCI.312559.
[26] Sun, H., Elghazi, R., Gainaru, A., Aupy, G., & Raghavan, P. (2018). Scheduling parallel tasks under multiple resources: list scheduling vs. pack scheduling. In 2018 IEEE 32nd International Parallel and Distributed Processing Symposium (IPDPS), 194{203. https://doi:10.1109/IPDPS.2018.00029.
[27] Toshev, A. (2019). Particle swarm optimization and tabu search hybrid algorithm for exible job shop scheduling problem { analysis of test results. Cybernetics and Informa-tionTechnologies, 19(4):26{44. https://doi:10.2478/cait-2019-0034.
[28] Vela, C. R., Afsar, S., Jose, J., Gonzalez-rodrguez, I., & Puente, J., (2020). Evolutionary tabu search for exible due-date satisfaction in fuzzy job shop scheduling. Computers and Operations Research, 119:104931. https://doi:10.1016/j.cor.2020.104931.
[29] Umam, M. S., Musta d, M., & Suryono, S. (2022). A hybrid genetic algorithm and tabu search for minimizing makespan in ow shop scheduling problem. J. King Saud Univ. Comput. Inf. Sci., 34(9),7459-7467. https://doi:10.1016/j.jksuci.2021.08.025.
[30] Wang, S., & Ye, B. (2019). Exact methods for order acceptance and scheduling on unrelated parallel machines. Comput. Oper. Res., 104,159{173. https://doi:10.1016/j.cor.2018.12.016.
[31] Wei, H., Li, S., Jiang, H., & Hu, J. (2018). Hybrid genetic simulated annealing algorithm for improved ow shop  scheduling with makespan criterion. Appl. Sci., 8(12),2621. https://doi:10.3390/app8122621.
[32] Wu, G., Cheng, C., Yang, H., & Chena, C. (2017). An improved water ow-like algorithm for order acceptance and scheduling with identical parallel machines. Appl. Soft Comput. J., 71, 1072-1084. https://doi:10.1016/j.asoc.2017.10.015.
[33] Zhang, G., Zhang, L., Song, X., Wang, Y., & Zhou, C. (2018). A variable neighborhood search based genetic algorithm for exible job shop scheduling problem. Cluster Comput., 22, 11561-11572. https://doi:10.1007/s10586-017-1420-4.
[34] Zorin, D. A., & Kostenko, V. A. (2014). Simulated annealing algorithm in problems of multiprocessor scheduling. Automation and Remote Control, 75, 1790-1801. https://doi:10.1134/S0005117914100063.
Journal of Mahani Mathematical Research
Volume 13, Issue 1 - Serial Number 26
November 2023
Pages 535-562

Files

History

  • Receive Date: 26 May 2023
  • Revise Date: 28 August 2023
  • Accept Date: 13 October 2023

Share

How to cite

Statistics