Parallel Jobs Scheduling with a Specific Due Date: Asemi-definite Relaxation-based Algorithm

Subject Areas : Business and Marketing

Javad  Behnamian ¹ (Department of Industrial Engineering, Faculty of Engineering, Bu-Ali Sina University, Hamedan, Iran)

Received: 2016-03-13 Accepted : 2017-11-20 Published : 2020-12-01

Keywords: Graph coloring, Parallel jobs scheduling, Semidefinite relaxation, Tardiness,

Abstract :

This paper considers a different version of the parallel machines scheduling problem in which the parallel jobs simultaneously requirea pre-specifiedjob-dependent number of machines when being processed.This relaxation departs from one of the classic scheduling assumptions. While the analytical conditions can be easily statedfor some simple models, a graph model approach is required when conflicts of processor usage are present. The main decisions and solving steps are as follows, respectively. (i) Converting the scheduling problem to graph model; (ii) Dividing jobs into independent sets: in this phase, we propose a semi-definite relaxation algorithm in which we use graph coloring concept; (iii) Sequencing the independent sets as a single-machine scheduling in which jobs in such a system arejob sets formed by using a semi-definite relaxation solution and determining the problem as a schedule that minimizes the sum of the tardiness of jobs. In this regard, after grouping the jobs by a semi-definite programming relaxation algorithm, we used the rounding algorithm for graph coloring. We also proposed a variable neighborhood search algorithm for sequencing the obtained job sets in order to minimize the sum of the tardiness. Experimental results show that this methodology is interesting by obtaining good results.

References:

Almeida, M.T., & Centeno, M. (1998). A composite heuristic for the single machine early/tardy job scheduling problem. Computers andOperations Research, 25, 625-635.

Babbar, D., & Krueger, P. (1994). On-line hard real-time scheduling of parallel tasks on partitionable multiprocessors. In Proceedings of International Conference on Parallel Processing (ICPP’94), pages II–29–II–38. IEEE Computer Society, Los Alamitos, CA, USA.

Barbosa, J.G., & Moreira, B. (2011). Dynamic scheduling of a batch of parallel task jobs on heterogeneous clusters, Parallel Computing, 37(8), 428–438.

Birman, M., & Mosheiov, G. (2004). A note on a due-date assignment on a two-machine flow-shop. Computers and Operations Research, 31, 473–480.

Bischof, S., & Mayr, E.W. (2001). On-line scheduling of parallel jobs with runtime restrictions. Theoretical Computer Science, 268, 1, 67–90.

Bougeret, M., Dutot, P-F., Trystram, D., Jansen, K., & Robenek, C. (2015). Improved approximation algorithms for scheduling parallel jobs on identical clusters, Theoretical Computer Science, 600(4), 70-85.

Brelsford, D., Chochia, G., Falk, N., Marthi, K., Sure, R., Bobroff, N., Fong, L., & Seelam, S. (2013). Partitioned parallel job scheduling for extreme scale computing, In: Job Scheduling Strategies for Parallel Processing, Lecture Notes in Computer Science, 7698, 157-177.

Bülbül, K., Kaminsky, P., & Yano, C. (2007). Preemption in single machine earliness/tardiness scheduling. Journal of Scheduling, 10, 271–292.

Chen, B., & Vestjens, A.P.A. (1997). Scheduling on identical machines: How good is LPT in an on-line setting?. Operations Research Letters, 21, 165–169.

Chen, Z.L. (1996). Scheduling and common due date assignment with earliness-tardiness penalties and batch delivery costs. European Journal of Operational Research, 93, 49-60.

Chen, Z.L., & Powell, W.B. (1999). A column generation based decomposition algorithm for a parallel machines just-in-time scheduling problem. European Journal of Operational Research, 116, 221-233.

Cheng, B., Wang, Q., Yang, S., & Hu, X. (2013). An improved ant colony optimization for scheduling identical parallel batching machines with arbitrary job sizes, Applied Soft Computing, 13, 765–772.

Damodaran, P., & Vélez-Gallego, M.C. (2012). A simulated annealing algorithm to minimize makespan of parallel batch processing machines with unequal job ready times, Expert Systems with Applications, 39, 1451–1458.

Damodaran, P., & Vélez-Gallego, M.C. (2012). A simulated annealing algorithm to minimize makespan of parallel batch processing machines with unequal job ready times, Expert Systems with Applications, 39, 1451–1458.

Dell’Olmo, P., & Gentili, M. (2006). Graph models for scheduling systems with machine saturation property, Mathematical Methods of Operations Research, 63, 329–340.

Deng, X., Gu, N., Brecht, T., & Lu, K. (2000). Preemptive scheduling of parallel jobs on multiprocessors. SIAM Journal on Computing, 30(1), 145–160.

Drozdowski, M. (1996). Real-time scheduling of linear speedup parallel tasks. Information Processing Letters, 57(1), 35–40.

Du, J., & Leung, J. (1989). Complexity of scheduling parallel job system. SIAM Journal on Discrete Mathematics, 2, 473–487.

Dutot, P.F., Mounié, G., & Trystram, D. (2004). Scheduling parallel tasks: Approximation algorithms. In J.Y. Leung, editor, Handbook of Scheduling: Algorithms, Models, and Performance Analysis, pages 26.1–26.24. CRC Press, Boca Raton.

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.

Emmons, H. (1987). Scheduling to a common due-date on parallel uniform processors. Naval Research Logistics Quarterly, 34, 803–810.

Esteve, B., Aubijoux, C., Chartier, A., & Tkindt, V. (2006). A recovering beam search algorithm for the single machine just-in-time scheduling problem. European Journal of Operational Research, 172, 798–813.

Feitelson, D.G., & Rudolph, L. (1998). Metrics and benchmarking for parallel job scheduling. In D.G. Feitelson and L. Rudolph, editors, Job Scheduling Strategies for Parallel Processing. LNCS, volume 1459, pages 1–24. Springer, Berlin.

Feldmann, A., Kao, M.-Y., Sgall, J., & Teng, S.-H. (1998). Optimal online scheduling of parallel jobs with dependencies. Journal of Combinatorial Optimization, 1(4), 393–411.

Feldmann, A., Sgall J., & Teng, S.H. (1994). Dynamic scheduling on parallel machines. Theoretical Computer Science, 130(1), 49–72.

Frachtenberg, E., Feitelson, D.G., Petrini, F., & Fernandez, J. (2005). Adaptive parallel job scheduling with flexible coscheduling. IEEE Transactions on Parallel and Distributed Systems, 16(11), 1066–1077.

Glasgow, J., & Shachnai, H. (1997). Channel based scheduling of parallelizable tasks. In Proceedings of 5th IEEE International Workshop on Modeling, Analysis, and Simulation of Computer and Telecommunications Systems (MASCOTS’97), pages 11–16. IEEE Computer Society, Los Alamitos, CA, USA.

Gordon, V., Proth, J.M., & Chu, C. (2002). A survey of the state-of-the-art of common due-date assignment and scheduling research. European Journal of Operational Research, 135, 1–25.

Guo, S., & Kang, L. (2010). Online scheduling of malleable parallel jobs with setup times on two identical machines, European Journal of Operational Research, 206, 555–561.

Herrmann, J.W., & Lee., C.Y. (1993). On scheduling to minimize earliness-tardiness and batch delivery costs with a common due date. European Journal of Operational Research, 70, 272-288.

Hoogeveen, J.A. (2005). Multicriteria scheduling. European Journal of Operational Research, 167, 592–623.

Jansen, K. (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, volume 2461, pages 562–574, Springer, Berlin.

Jansen, K., & Porkolab, L. (2000). Preemptive parallel task scheduling in o(n) + poly(m) time. In D.T. Lee and S.H. Teng, editors, Proceedings of ISAAC 2000. LNCS, volume 1969, pages 398–409, Springer, Berlin.

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.

Johannes, B. (2006). Scheduling parallel jobs to minimize the makespan. Journal of Scheduling, 9(5), 433–452.

Karger, D., Motwani, R., & Sudan, M. (1998). Approximate graph coloring by semidefiniteprogramming. J. ACM, 45(2), 246–265.

Krishnamurti, R., & Gaur, D.R. (1999). An approximation algorithm for nonpreemptive scheduling on hypercube parallel task systems. Information Processing Letters, 72(5–6), 183–188.

Krishnamurti, R., & Narahari, B. (1995). An approximation algorithm for preemptive scheduling on parallel-task systems. SIAM Journal on Discrete Mathematics, 8(4), 661–669.

Kubiak, W., Lou, S., & Sethi, R. (1990). Equivalence of mean flow time problems and mean absolute deviation problems. Operations Research Letters, 9, 371–374.

Kwon, O.H., & Chwa, K.-Y. (1999). Scheduling parallel tasks with individual deadlines. Theoretical Computer Science, 215(1-2), 209–223.

Lauff,  V., &  Werner, F. (2004). Scheduling with common due date, earliness and tardiness penalties for multimachine problems: A survey. Mathematical and Computer Modelling, 40, 637–655.

Li, K. (1999a). Analysis of an approximation algorithm for scheduling independent parallel tasks. Discrete Mathematics and Theoretical Computer Science, 3(4), 155–166.

Li, K. (1999b). Analysis of the list scheduling algorithm for precedence constrained parallel tasks. Journal of Combinatorial Optimization, 3(1), 73–88.

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, P., & Liu, Z. (2008). A report on approximate graph coloring by semidefinite programming, Instructor Kartik,K. Sivaramakrishnan, Edward P. Fitts Department of Industrial and Systems Engineering, North Carolina State University.

Low, C., & Yuling, Y. (2009). Genetic algorithm-based heuristics for an open shop scheduling problem with setup, processing, and removal times separated. Robotics and Computer-Integrated Manufacturing, 2(25), 314-322.

Ludwig, W., & Tiwari, P. (1994). Scheduling malleable and nonmalleable parallel jobs. In Proceedings of the 5th ACM-SIAM symposium on discrete algorithms (SODA). pp. 167–176.

Lushchakova, I.N. (2012). Preemptive scheduling of two uniform parallel machines to minimize total tardiness, European Journal of Operational Research, 219(1), 27-33.

Montgomery, D.C. (2000. Design and Analysis of Experiments, Fifth ed. New York: John Wiley & Sons.

Naroska, E., & Schwiegelshohn, U. (2002). On an on-line scheduling problem for parallel jobs. Information Processing Letters, 81, 6, 297–304.

Pinedo, M.L. (2008). Scheduling: Theory, Algorithms, and Systems, Third Edition, Springer Science+Business Media, LLC, NY: USA.

Rapine, C.H., Scherson, I., & Trystram, D. (1998). On-line scheduling of parallelizable jobs. In D. Pritchard and J. Reeve, editors, Proceedings of Euro-Par 1998. LNCS, 1470, 322–327. Springer, Berlin.

Rocha, M., Gómez Ravetti, M., Mateus, G.R., & Pardalos, P.M. (2007). Solving parallel machines scheduling problems with sequence-dependent setup times using variable neighborhood search. IMA Journal of Management Mathematics, 18, 101−115.

Sgall, J. (1996). Randomized on-line scheduling of parallel jobs. Journal od Algorithms, 21(1), 149– 175.

Shmoys, D., Wein, J., & Williamson, D. (1995). Scheduling parallel machines on-line, SIAM Journal on Computing, 24, 1313–1331.

Srinivasan, S., Subramani, V., Kettimuthu, R., Holenarsipur, P., & Sadayappan, P. (2002). Effective selection of partition sizes for moldable scheduling of parallel jobs. In S. Sahni, V.K. Prasanna, and U. Shukla, editors, Proceedings of 9th International Conference on High Performance Computing (HiPC’02). LNCS, 2552, 174–183.

Sun, H., Hsu, W-J., & Cao, Y. (2014). Competitive online adaptive scheduling for sets of parallel jobs with fairness and efficiency, Journal of Parallel and Distributed Computing, 74(3), 2180–2192.

Turek, J. Wolf, J.L. Pattipati, K.R., & Yu, P.S. (1992). Scheduling parallelizable tasks: Putting it all on the shelf. ACM SIGMETRICS Performance Evaluation Review, 20, 1, 225–236.

Turek, J., Ludwig, W., Wolf, J.L., Fleischer, L., Tiwari, P., Glasgow, J., Schwiegelshohn, U., & Yu, P. S. (1994). Scheduling parallelizable tasks to minimize average response time. In Proceedings of 6th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA’94), pages 200–209. ACM, New York, NY, USA.

Turek, J., Schwiegelshohn, U., Wolf, J.L., & Yu, P.S. (1994). Scheduling parallel tasks to minimize average response time. In Proceedings of the 5th Annual ACM-SIAM Symposium on Discrete algorithms (SODA’94), pages 112–121. SIAM, Philadelphia PA, USA.

Turek, J., Wolf, J. L., & Yu, P. S. (1992). Approximate algorithms for scheduling parallelizable tasks. In Proceedings of 4th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA’92), pages 323–332. ACM, New York, NY, USA.

Wang, Q., & Cheng, K.-H. (1991). List scheduling of parallel tasks. Information Processing Letters, 37(5), 291–297.

Wang, Q., & Cheng, K.-H. (1992). A heuristic of scheduling parallel tasks and its analysis. SIAM Journal on Computing, 21(2), 281–294.

Ye, D., & Zhang, G. (2003). On-line scheduling of parallel jobs with dependencies on 2-dimensional mesh. In T. Ibaraki, N. Katoh, and H. Ono, editors, Proceedings of 14th International Symposium Algorithms and Computation (ISAAC’03). LNCS, 2906, 329–338.

Ye, D., & Zhang, G. (2007). On-line scheduling of parallel jobs in a list, Journal of Scheduling, 10, 407–413.