A new algorithm for solving the parallel machine scheduling problem to maximize benefit and the number of jobs processed

Document Type : Research Paper

Authors

1 Department of Industrial Engineering, Faculty of Engineering, University of Kashan, Kashan, Iran

2 Department of Computer Engineering, Ayatollah Amoli Branch, Islamic Azad University, Amol, Iran

3 Department of Computer Engineering, Faculty of Mahmoudabad, Technical and Vocational University, Mazandaran, Iran

10.22070/jqepo.2021.14209.1182

Abstract

This paper provides a mathematical model and a bi-phase heuristic algorithm for the uniform parallel machines scheduling problem to maximize benefits and the number of jobs processed before their due dates as the weighted objective function. In the first phase of this heuristic, named “the neighborhood combined dispatching rules algorithm” (NCDRA), an initial sequence by the segmentation of the dispatching rules (DRs) is generated. Then, the output sequence is segmented, and required efforts are made to derive a sequence combined with these rules to improve the objective. The second phase involves a local search in which operators such as swapping, insertion, and reversion are concurrently implemented there on. The proposed algorithm is examined on four classes of problems with 50, 100, and 1000 jobs on 5, 10, and 50 machines, respectively. Results obtained by NCDRA and a Simulated Annealing (SA) algorithm developed on problem instances indicate that the NCDRA provides high-quality results on objective function for solving problems in different scales.

Keywords

References

Bard, J. F., & Rojanasoonthon, S. (2006). A branch and price algorithm for parallel machine scheduling with time windows and job priorities. Naval Research Logistics, 53(1), 24-44.
Bitar, A., Dauzère-Pérès, S., Yugma, C., & Roussel, R. (2016). A memetic algorithm to solve an unrelated parallel machine scheduling problem with auxiliary resources in semiconductor manufacturing. Journal of Scheduling, 19(4), 367-376.
Cao, D., Chen, M., & Wan, G. (2005). Parallel machine selection and job scheduling to minimize machine cost and job tardiness. Computers & Operations Research, 32(8), 1995-2012.
Croce, D. F., T’kindt V. & Ploton, O. (2021). Parallel machine scheduling with minimum number of tardy jobs: Approximation and exponential algorithms. Applied Mathematics and Computation, 397, 125888.
Chen, B., & Vestjens, A.P.A. (1997). Scheduling on identical machines: how good is LPT in an on-line setting?. Operational Research Letters, 21, 165-169.
Chung, S.H., Pearn, W.L. & Tai, Y.T. (2009). Fast and effective algorithms for the liquid crystal display module (LCM) scheduling problem with sequence-dependent setup time. Journal of the Operational Research Society, 60, 921–933.
Fanjul-Peyro, L., & Ruiz, R. (2010). Iterated greedy local search methods for unrelated parallel machine scheduling. European Journal of Operational Research, 207(1), 55-69.
Gholami, O., Sotskov, Y. N., Werner, F., & Zatsiupo, A. S. (2019). Heuristic algorithms to maximize revenue and the number of jobs processed on parallel machines. Automation and Remote Control, 80(2), 297-316.
Hoseini, S.F., Omran, M.M., Márquez, A.C. & Makui, A. (2018). Simultaneous optimisation of seaside operations in container terminals: a case study of the Iranian Rajaee port. International Journal of Shipping and Transport Logistics, 10(5-6), 587-617.
Huang, J., Li, S., & Chen, Y. (2020). Revenue-optimal task scheduling and resource management for IoT batch jobs in mobile edge computing. Networking and Applications, 13, 1776–1787.
Kaban, A. K., Othman, Z., & Rohmah, D. S. (2012). Comparison of dispatching rules in job-shop scheduling problem using simulation: a case study. International Journal of Simulation Modelling, 11(3), 129-140.
Kowalczyk, D., & Leus, R. (2017). An exact algorithm for parallel machine scheduling with conflicts. Journal of Scheduling, 20(4), 355-372.
Islam, M., Khanna, G., & Sadayappan, P. (2008). Revenue Maximization in Market-Based Parallel Job Schedulers. Ohio State University Library.
Joo, C. M., & Kim, B. S. (2015). Hybrid genetic algorithms with dispatching rules for unrelated parallel machine scheduling with setup time and production availability. Computers & Industrial Engineering, 85, 102-109.
Juraszek, J., Sterna, M., & Pesch, E., (2009). Revenue maximization on parallel machines. Institute of Computing Science, Poznan University of Technology, 960-965.
Laha, D., & Gupta, J. N. (2018). An improved cuckoo search algorithm for scheduling jobs on identical parallel machines”. Computers & Industrial Engineering, 126, 348-360.
Lee, C. H., (2018). A dispatching rule and a random iterated greedy metaheuristic for identical parallel machine scheduling to minimize total tardiness. International Journal of Production Research, 56(6), 2292-2308.
Mensendiek, A., Gupta, J. N., & Herrmann, J. (2015). Scheduling identical parallel machines with fixed delivery dates to minimize total tardiness. European Journal of Operational Research, 243(2), 514-522.
Nattaf, M., Dauzère-Pérès, S., Yugma, C., & Wu, C. H. (2019). Parallel machine scheduling with time constraints on machine qualifications. Computers & Operations Research, 107, 61-76.
Pinedo, M. (2012). Scheduling (Vol. 29). New York: Springer.
Phanden, R. K., Jain, A., & Verma, R. (2013). An approach for integration of process planning and scheduling. International Journal of Computer Integrated Manufacturing, 26(4), 284-302. doi:10.1080/0951192X.2012.684721.
Rojanasoonthon, S., Bard, J. F., & Reddy, S. D. (2003). Algorithms for parallel machine scheduling: a case study of the tracking and data relay satellite system. Journal of the Operational Research Society, 54(8), 806-821.
Raghu, T. S., & Rajendran, C. (1993). An efficient dynamic dispatching rule for scheduling in a job shop. International Journal of Production Economics, 32(3), 301-313.
Yang-Kuei, L., & Chi-Wei, L. (2013). Dispatching rules for unrelated parallel machine scheduling with release dates. The International Journal of Advanced Manufacturing Technology, 67(1-4), 269-279. doi:10.1007/s00170-013-4773-8.
Journal of Quality Engineering and Production Optimization
Volume 6, Issue 2
December 2021
Pages 115-142

Files

Share

How to cite

Statistics