A two-objective Mathematical Model for Job Scheduling on Parallel Machines and Solving by Particle Swarm Optimization

Document Type : Original Article

Author

Department of Industrial Engineering, Islamic Azad University, Tabriz Branch, Tabriz, Iran.

10.22116/jiems.2025.498885.1587
Abstract
Time is one of the most valuable assets in industry, and cost is another highly regarded factor. Optimal utilization of these resources can increase efficiency and profit. The parallel machine scheduling problem is a fundamental issue in industry and services. This research proposes a two-objective mathematical model for parallel machine scheduling. The first objective function is defined as the makespan, which is the completion time of the last job. The second objective function is defined as the maximum cost incurred by any single machine, which is a function of the sum of the processing costs of each operation and the fixed cost of purchasing and maintaining the machines. Each job consists of multiple operations, and all operations must be completed to finish the job. Additionally, it is assumed that jobs have priorities, and precedence constraints between operations must be satisfied. Due to the model's non-linearity and the problem's complexity, a metaheuristic algorithm based on the particle swarm optimization (PSO) approach is developed to solve the proposed model by aggregating the objective functions. The proposed method is simulated in MATLAB on three sample instances in small, medium, and large scales. The computational results demonstrate the robustness and efficiency of the proposed method.

Keywords


Abdyazdan, M., Rahmani, A. (2007). Task scheduling in multiprocessor systems using a new priority genetic algorithm based on the number of children. 13th Annual Conference of Computer Society of Iran. (in Persian)
Adler, D. (1993). Genetic algorithms and simulated annealing: A marriage proposal. IEEE International Conference on Neural Networks, 2, 1104-1109, DOI: 10.1109/ICNN.1993.298712.
Ak, B., Koc, E. (2012). A Guide for Genetic Algorithm Based on Parallel Machine Scheduling and Flexible Job-Shop Scheduling. Procedia-Social and Behavioral Sciences, 62, 817-823.
Aggoune, R., (2004). Minimizing the Makespan for the Flow Shop Scheduling Problem with Availability Constraints, European Journal of Operational Research, 153(3), 534–543.
Ayough, A., Khorshidvand, B. (2019). Designing a manufacturing cell system by assigning workforce. Journal of Industrial Engineering and Management, 12(1), 13-26. doi: https://doi.org/10.3926/jiem.2547
Ayough, A., Khorshidvand, B. (2023). Robust optimization for the integrated worker-cell assignment and sequencing problem in a lean U-shaped assembly line, Computers & Industrial Engineering, 178, 109139, https://doi.org/10.1016/j.cie.2023.109139.
Ayough, A., Rabieh, M., Javadi, M.N., and Khoshidvand, B. (2024). An MINLP model for project scheduling with feeding buffer, International Journal of Applied Decision Sciences, 17(6), 710-732.
Garey, H.M., Johnson, D., Sethi, R. (1976). The complexity of flow shop and job shop scheduling, Mathematics of Operation Research, 1, 117-129.
Garshasbi, M. (2012). Optimization of task scheduling on parallel multiprocessor systems using genetic algorithms. 2nd Lahijan National Conference on Software Engineering. (in Persian)
Gholipour Kanani, Y., Tavakkoli Moghaddam, R., Tabari, M., Jafari Zarandini, Y., & Aryanezhad, M. B. (2011). Solving a Novel Multi-Objective Scheduling Problem in a Cellular Manufacturing System by a Hybrid Algorithm. Research in Production and Operations Management, 2(2), 1-18. (in Persian)
Hao, G., Sam, K., Baojie F., Ran W. (2014).  A Hybrid Particle-Swarm Tabu Search Algorithm for Solving Job Shop Scheduling Problems, Industrial Informatics, IEEE Transactions, on, 10(4), 2044 – 2054.
Haouari, M., Gharbi, A., Jemmali, M. (2006). Tight bounds for the identical parallel machine scheduling problem. International Transactions in Operational Research, 13(6), 529-548.
Kennedy, J. and Eberhart, R. (1995). Particle Swarm Optimization. Proceedings of the IEEE International Conference on Neural Networks, 4, 1942-1948.
Javani, M., Fardad, Kh., Medadian, M. (2010) Scheduling Static Multiprocessor Systems with Multi-Agent Memetic Algorithm. 4th Iran Data Mining Conference (IDMC), Tehran. (in Persian)
Joulaei, F., Tavakoli Moghadam, R., & Azadian, F.. (2006). Parallel Machine Scheduling For Split Jobs With Sequence Dependent Setup Times. Journal Of Faculty Of Engineering (University Of Tehran), 40(4 (98)), 495-506. (in Persian)
Mattfeld, D., Bierwirth, C. (2014). An efficient genetic algorithm for job shop scheduling with tardiness objectives, European Journal of Operational Research, 155, 616–630.
Mousavi, S., Mahdavi, I., Rezaeian, J., Zandieh, M. (2018). Bi-objective scheduling for the re-entrant hybrid flow shop with learning effect and setup times. Scientia Iranica, 25(4), 2233-2253.
Mousavipoor, H., Farughi, H., Ahmadizar, F. (2019). Job shop scheduling problem based on learning effects, flexible maintenance activities and transportation times. Journal of Industrial and Systems Engineering, 12(3), 107-119.
Naderi, B., Zandieh, M., Ghomi, S.F. (2009). Scheduling sequence-dependent setup time job shops with preventive maintenance, The International Journal of Advanced Manufacturing Technology, 43(1-2), 170-18,
Namazi, A., Golmakani, H. (2013). Multiple Route Job Shop Scheduling with Maintenance Activity Constraints. International Journal of Industrial Engineering and Production Management. 23(4), 459-470.
Naseri, H., Khalili, F., Taghinezhad, N., Taleshian, F. (2013). Modeling the open workshop scheduling problem considering machine downtime, parameter availability, and time frame, Journal of Operations Research and Applications. 2, 131-143. (in Persian)
Parsa, S., Izadkhah, H., Hosseinzade,A. (2007). Combining object migration algorithm and genetic algorithm for task graph scheduling in multiprocessor architecture. 3rd International Conference on Information and Knowledge Technology, Tehran, (in Persian)
Pezzella, F., Morganti, G., Ciaschetti, G. (2008). A genetic algorithm for the Flexible Job-shop Scheduling Problem, Computers and Operations Research. 35(10), 3202-3212.
Pinedo. M.L. (2008). Scheduling, theory, algorithms, and systems. Springer, 3rd edition.
Rahmati, S. H. A., Zandieh, M. (2012). Developing two multi-objective algorithms for solving multi-objective flexible job shop scheduling problem considering total consumed power per month. Industrial Management Studies, 10(27), 118-143.
Roohnavazfar, M., Manerba, D., Fotio Tiotsop, L. (2021). Stochastic single-machine scheduling problem as a multi-stage dynamic random decision process. Computational Management Science, 18, 267–297.
Statsny, J., Skorpil, V., Balogh, Z., Klein, R., (2021). Job Shop Scheduling Problem Optimization by Means of Graph-Based Algorithm, Applied Science, 11.
Tavakkoli Moghaddam, R., Khodadagan, Y., Haghnevis, M. (2005). Presenting a combinatorial model for selecting parallel machines and scheduling jobs considering setup times. 4th International Industrial Engineering Conference, Tehran. (in Persian)
Wang, C.S., Uzsoy, R. (2012). A genetic algorithm to minimize maximum lateness on a batch processing machine, Computer and Operations Research, 9(12), 1014-1021. 
Geurtsen, M., Didden, J., Adan, J., Atan, Z., Adan, I. (2023). Production, maintenance and resource scheduling: A review," European Journal of Operational Research., 305(2), 501-529.
Ying, K.C., Pourhejazy, P., Huang, Z.Y, (2024). Revisiting the development trajectory of parallel machine scheduling, Computers & Operations Research, 168, 106709.
Liu, C.L., Tseng, C.J., Huang, T.H., Wang, J.W. (2023). Dynamic Parallel Machine Scheduling With Deep Q-Network." IEEE Explore, 53(11), 6792-6804.

Articles in Press, Accepted Manuscript
Available Online from 01 July 2025