Document Type : Original Article
Author
Department of Industrial Engineering, Faculty of Engineering, Bu-Ali Sina University, Hamedan, Iran.
Abstract
This research extends a two-phase algorithm for parallel job scheduling problem by considering earliness and tardiness as multi-objective functions. Here, it is also assumed that the jobs may use more than one machine at the same time, which is known as parallel job scheduling. In the first phase, jobs are grouped into job sets according to their machine requirements. For this, here, a heuristic algorithm is proposed for coloring the associated graph. In the second phase, job sets will be sequenced as a single machine scheduling problem. In this stage, for sequencing the job sets which are obtained from the first phase, a discrete algorithm is proposed, which comprises two well-known metaheuristics. In the proposed hybrid algorithm, the genetic algorithm operators are used to discretize the particle swarm optimization algorithm. An extensive numerical study shows that the algorithm is very efficient for the instances which have different structures so that the proposed algorithm could balance exploration and exploitation and improve the quality of the solutions, especially for large-sized test problems.
Keywords
Barbosa, J.G. & Moreira, B. (2011). Dynamic scheduling of a batch of parallel task jobs on heterogeneous clusters, Parallel Computing, 37(8), 428–438.
Behnamian, J. (2016). Graph coloring-based algorithm to parallel job scheduling on parallel factories. International Journal of Computer Integrated Manufacturing, 29(6), 622-635.
Behnamian, J. (2020). Parallel Jobs Scheduling with a Specific Due Date: Asemi-definite Relaxation-based Algorithm, Journal of Optimization in Industrial Engineering, 13(2), 199-210.
Behnamian, J., Fatemi Ghomi, S.M.T. (2015), Minimizing cost-related objective in synchronous scheduling of parallel factories in virtual production network, Applied soft computing, 29, 221-232.
Bischof, S. & Mayr, E.W. (2001). On-line scheduling of parallel job with runtime restrictions. Theoretical Computer Science, 268, 1, 67–90.
Brelsford, D., Chochia, G., Falk, N., Marthi, K., Sure, R., Bobroff, N., ... & Seelam, S. (2012, May). Partitioned parallel job scheduling for extreme scale computing. In Workshop on Job Scheduling Strategies for Parallel Processing (pp. 157-177). Springer, Berlin, Heidelberg.
Dell’Olmo, P., & Gentili, M. (2006). Graph models for scheduling systems with machine saturation property. Mathematical Methods of Operations Research, 63(2), 329-340.
Dutot, P. F., Mounié, G., & Trystram, D. (2004). Scheduling parallel tasks: Approximation algorithms.
Ebrahimi Moghaddam, M., & Bonyadi, M. R. (2012). An immune-based genetic algorithm with reduced search space coding for multiprocessor task scheduling problem. International Journal of Parallel Programming, 40(2), 225-257.
Ebrahimi Zade, A., Fakhrzad, M., Hasaninezhad, M. (2016). A heuristic algorithm for solving single machine scheduling problem with periodic maintenance. Journal of System Management, 2(4), 1-12.
Garey, M. R. (1979). computers and intractqbility. A Guide to the Theory of NP-Completeness.
Guan, Y. Xiao, W-Q. Cheung, R. K. & Li, C-L. (2002). A multiprocessor task scheduling model for berth allocation: Heuristic and worst-case analysis, Operations Research Letters, 30(5), 343-350.
Guo, S., & Kang, L. (2010). Online scheduling of malleable parallel jobs with setup times on two identical machines. European Journal of Operational Research, 206(3), 555-561.
Hao, Y., Wang, L., Zheng, M. (2016). An adaptive algorithm for scheduling parallel job in meteorological Cloud, Knowledge-Based Systems, 98, 226-240.
Hao, Y., Xia, M., Wen, N., Hou, R., Deng, H., Wang, L., Wang, Q. (2017). Parallel task scheduling under multi-Clouds, KSII Transactions on Internet and Information Systems, 11, 1, 39-60.
Hoogeveen, J. A., van de Velde, S. L., & Veltman, B. (1994). Complexity of scheduling multiprocessor tasks with prespecified processor allocations. Discrete Applied Mathematics, 55(3), 259-272.
Jansen, K., & Porkolab, L. (2002). Linear-time approximation schemes for scheduling malleable parallel tasks. Algorithmica, 32(3), 507-520.
Jansen, K. & Porkolab, L. (2003). Computing optimal preemptive schedules for parallel tasks: Linear programming approaches. Mathematical Programming, 95, 3, 617–630.
Jansen, K., Trystram, D. (2016). Scheduling parallel job on heterogeneous platforms, Electronic Notes in Discrete Mathematics, 55, 9-12.
K. Jansen (2002). Scheduling malleable parallel tasks: An asymptotic fully polynomial-time approximation scheme. In R. Möhring and R. Raman, editors, Proceedings of ESA 2002. LNCS, 2461, 562–574, Springer, Berlin.
Lee, C. Y., & Cai, X. I. A. O. Q. I. A. N. G. (1999). Scheduling one and two-processor tasks on two parallel processors. IIE transactions, 31(5), 445-455.
Leung, K.K. Yung N.H.C. & Cheung, P.Y.S. (2002). Novel neighborhood search for multiprocessor scheduling with pipelining, Journal of Parallel and Distributed Computing 62, 85–110.
Li, K., & Pan, Y. (2000). Probabilistic analysis of scheduling precedence constrained parallel tasks on multicomputers with contiguous processor allocation. IEEE transactions on computers, 49(10), 1021-1030.
Li, K. (2018). Scheduling parallel tasks with energy and time constraints on multiple manycore processors in a cloud computing environment, Future Generation Computer Systems, 82, 591-605.
Liu, X., Zha, Y., Yin, Q., Peng, Y., Qin, L. (2015). Scheduling parallel job with tentative runs and consolidation in the cloud, Journal of Systems and Software, 104, 141-151.
Niu, Q. Jiao, B. Gu, X. (2008). Particle swarm optimization combined with genetic operators for job shop scheduling problem with fuzzy processing time, Applied Mathematics and Computation, 205(1), 148-158.
Parida, S., Nayak, S. C., Priyadarshi, P., Pattnaik, P. K., & Ray, G. (2018). Petri net: Design and analysis of parallel task scheduling algorithm. In Advances in Electronics, Communication and Computing (pp. 765-776). Springer, Singapore.
Pinedo, M. L. (2012). Scheduling (Vol. 29). New York: Springer.
Serafini, P. (1996). Scheduling jobs on several machines with the job splitting property. Operations Research, 44(4), 617-628.
Srinivasan, S., Subramani, V., Kettimuthu, R., Holenarsipur, P., & Sadayappan, P. (2002, December). Effective selection of partition sizes for moldable scheduling of parallel jobs. In International Conference on High-Performance Computing (pp. 174-183). Springer, Berlin, Heidelberg.
Su, L. H. (2009). Minimizing earliness and tardiness subject to total completion time in an identical parallel machine system. Computers & operations research, 36(2), 461-471.
Sun, H. Hsu, W-J. & Cao, Y. (2014). Competitive online adaptive scheduling for sets of parallel job with fairness and efficiency, Journal of Parallel and Distributed Computing, 74(3), 2180–2192.
Yazdani, M., Jolai, F. (2015). A genetic algorithm with modified crossover operator for a two-agent scheduling problem. Journal of System Management, 1(3), 1-13.
Ye, D., & Zhang, G. (2003). On-line scheduling of parallel jobs with dependencies on 2-dimensional meshes. In in proceedings of the 14th annual international symposium on algorithms and computation (ISAAC).
Ye, D. & Zhang, G. (2007). On-line scheduling of parallel job in a list, Journal of scheduling, 10, 407–413.
Zhang, L., Zhou, L., & Salah, A. (2020). Efficient scientific workflow scheduling for deadline-constrained parallel tasks in cloud computing environments. Information Sciences, 531, 31-46.
Zheng, B., Pan, L., & Liu, S. (2021). Market-oriented online bi-objective service scheduling for pleasingly parallel jobs with variable resources in cloud environments. Journal of Systems and Software, 176, 110934.
Zong, Z., Manzanares, A., Ruan, X., & Qin, X. (2010). EAD and PEBD: two energy-aware duplication scheduling algorithms for parallel tasks on homogeneous clusters. IEEE Transactions on Computers, 60(3), 360-374.
)