Flexible Job Shop Scheduling with Job Rejection Policy and Rate-Modifying Preventive Maintenance Activities

Document Type : Original Article


1 Ph.D. Candidate, Department of Industrial Management, Faculty of Management and Accounting, Allameh Tabataba’i University, Tehran, Iran.

2 Professor, Department of Industrial Management, Faculty of Management and Accounting, Allameh Tabataba’i University, Tehran, Iran.

3 Associate Professor, Department of Industrial Engineering, Qazvin Branch, Islamic Azad University, Qazvin, Iran.



Introduction: The flexible job shop system is one of the most widely used scheduling systems in production environments, consistently attracting researchers' attention due to its diverse applications. Many studies in this field assume fixed and predetermined processing times. However, processing times can increase due to the deterioration effect, and after implementing rate-modifying activities (RMA), these times return to their original values. This study examines the flexible job shop scheduling system, considering job rejection policies, dual resource constraints (human and machine), and RMA maintenance activities.
Methods: The objective of flexible job shop scheduling is to assign each operation to a machine and a worker from a set of eligible machines and workers in a way that optimizes the sequence of operations on the machines. A mathematical model based on the mixed-integer linear programming approach was developed for this purpose. Literature review classifies the problem with the stated assumptions as NP-hard, making the use of meta-heuristic methods essential for finding near-optimal solutions. Thus, Variable Neighborhood Search (VNS), Simulated Annealing (SA), and a combined VNS-SA algorithm were employed to solve the problem.
Results and discussion: Twenty sub-problems were analyzed, categorized into small, medium, and large-sized problems. The characteristics of each problem were defined by parameters such as the number of jobs, machines, workers, total operations, and buckets. Meta-heuristic methods, including VNS, SA, and their combination, were utilized to solve the problem. Seven neighborhood structures based on changes in assigned machines and workers, operation and job replacements, execution of RMA activities, and job acceptance/rejection were developed to enhance solution space exploration. The solution generation structure ensures feasibility within the flexible job shop system's requirements. The parameters of the meta-heuristic methods were tuned using the Taguchi method. Parameters related to the combined VNS-SA algorithm, such as initial temperature, number of neighborhood searches, and shake procedure counter, were reported. The results of the meta-heuristic methods were compared, and for small-sized problems, they were also compared with exact solutions.
Conclusion: The results of the twenty sub-problems solved using the three meta-heuristic approaches were compared statistically. The combined method of simulated annealing and variable neighborhood search showed superior performance in solving the problem.


Main Subjects

  1. An, Y., Chen, X., Gao, K., Zhang, L., Li, Y., & Zhao, Z. (2023a). A hybrid multi-objective evolutionary algorithm for solving an adaptive flexible job-shop rescheduling problem with real-time order acceptance and condition-based preventive maintenance. Expert systems with applications, 212, 118711.
  2. An, Y., Chen, X., Gao, K., Zhang, L., Li, Y., & Zhao, Z. (2023b). Integrated optimization of real-time order acceptance and flexible job-shop rescheduling with multi-level imperfect maintenance constraints. Swarm and Evolutionary Computation, 77, 101243.
  3. An, Y., Chen, X., Zhang, J., & Li, Y. (2020). A hybrid multi-objective evolutionary algorithm to integrate optimization of the production scheduling and imperfect cutting tool maintenance considering total energy consumption. Journal of cleaner production, 268, 121540.
  4. Behnamian, J., Zandieh, M., & Ghomi, S. F. (2009). Parallel-machine scheduling problems with sequence-dependent setup times using an ACO, SA and VNS hybrid algorithm. Expert Systems with Applications, 36(6), 9637-9644.
  5. Caldeira, R. H., Gnanavelbabu, A., & Vaidyanathan, T. (2020). An effective backtracking search algorithm for multi-objective flexible job shop scheduling considering new job arrivals and energy consumption. Computers & Industrial Engineering, 149, 106863.
  6. Dabiri, M., Yazdani, M., Naderi, B., & Haleh, H. (2022). Modeling and solution methods for hybrid flow shop scheduling problem with job rejection. Operational Research, 1-45.
  7. Gabi, D., Ismail, A. S., Zainal, A., & Zakaria, Z. (2019). Quality of service task scheduling algorithm for time-cost trade off scheduling problem in cloud computing environment. International Journal of Intelligent Systems Technologies and Applications, 18(5), 448-469.
  8. Ghaleb, M., Taghipour, S., & Zolfagharinia, H. (2021). Real-time integrated production-scheduling and maintenance-planning in a flexible job shop with machine deterioration and condition-based maintenance. Journal of Manufacturing Systems, 61, 423-449.
  9. Golpîra, H., & Tirkolaee, E. B. (2019). Stable maintenance tasks scheduling: A bi-objective robust optimization model. Computers & Industrial Engineering, 137, 106007.
  10. He, Z., Tang, B., & Luan, F. (2022). An Improved African Vulture Optimization Algorithm for Dual-Resource Constrained Multi-Objective Flexible Job Shop Scheduling Problems. Sensors, 23(1),
  11. Kim, H., & Kim, B.-I. (2022). Optimal sequence for single server scheduling incorporating a rate-modifying activity under job-dependent linear deterioration. European Journal of Operational Research, 298(2), 439-450.
  12. Kim, T., Kim, Y.-w., & Cho, H. (2020). Dynamic production scheduling model under due date uncertainty in precast concrete construction. Journal of cleaner production, 257, 120527.
  13. Kim, Y. J., Jang, J. W., Kim, D. S., & Kim, B. S. (2022). Batch loading and scheduling problem with processing time deterioration and rate-modifying activities. International Journal of Production Research, 60(5), 1600-1620.
  14. Li, X.-J., & Wang, J.-J. (2018). Parallel machines scheduling based on the impact of deteriorating maintenance. Journal of Interdisciplinary Mathematics, 21(3), 729-741.
  15. Luan, F., Li, R., Liu, S. Q., Tang, B., Li, S., & Masoud, M. (2022). An improved sparrow search algorithm for solving the energy-saving flexible job shop scheduling problem. Machines, 10(10),
  16. Martins, M. S., Viegas, J. L., Coito, T., Firme, B., Costigliola, A., Figueiredo, J., Sousa, J. M. (2023). Minimizing total completion time in large-sized pharmaceutical quality control scheduling. Journal of Heuristics, 29(1), 177-206.
  17. Meng, L., Zhang, C., Zhang, B., & Ren, Y. (2019). Mathematical modeling and optimization of energy-conscious flexible job shop scheduling problem with worker flexibility. IEEE Access, 7, 68043-68059.
  18. Mosheiov, G., & Oron, D. (2021). A note on scheduling a rate modifying activity to minimize total late work. Computers & Industrial Engineering, 154, 107138.
  19. Nelson, R. T. (1967). Labor and machine limited production systems. Management Science, 13(9), 648-671.
  20. Nikouei, M. A., Zandieh, M., & Amiri, M. (2022). A two-stage assembly flow-shop scheduling problem with bi-level products structure and machines’ availability constraints. Journal of Industrial and Production Engineering, 39(6), 494-503.
  21. Oroujzadeh, M., Nikouei, M. A., Mehdipour-Ataei, S., & Amiri, M. (2022). Materials selection for choosing the best composite blend polymeric membrane for hydrogen/oxygen proton exchange membrane fuel cell. Journal of Power Sources, 538, 231566.
  22. Pal, M., Mittal, M. L., Soni, G., Chouhan, S. S., & Kumar, M. (2023). A multi-agent system for FJSP with setup and transportation times. Expert systems with applications, 216, 119474.
  23. Peng, Z., Zhang, H., Tang, H., Feng, Y., & Yin, W. (2021). Research on flexible job-shop scheduling problem in green sustainable manufacturing based on learning effect. Journal of Intelligent Manufacturing, 1-22.
  24. Renna, P., Thürer, M., & Stevenson, M. (2020). A game theory model based on Gale-Shapley for dual-resource constrained (DRC) flexible job shop scheduling. International Journal of Industrial Engineering Computations, 11(2), 173-184.
  25. Sadat, S. M., Jahan, S. T., & Haddadi, A. (2016). Effects of size and surface charge of polymeric nanoparticles on in vitro and in vivo applications. Journal of Biomaterials and Nanobiotechnology, 7(02),
  26. Saidat, S., Junoh, A. K., Wan Muhamad, W. Z. A., & Yahya, Z. (2022). Modified job shop scheduling via Taguchi method and genetic algorithm. Neural Computing and Applications, 1-18.
  27. Soofi, P., Yazdani, M., Amiri, M., & Adibi, M. A. (2021). Robust fuzzy-stochastic programming model and meta-heuristic algorithms for dual-resource constrained flexible job-shop scheduling problem under machine breakdown. IEEE Access, 9, 155740-155762.
  28. SUN, A., SONG, Y., YANG, Y., & LEI, Q. (2022). Dual Resource-constrained Flexible Job Shop Scheduling Algorithm Considering Machining Quality of Key Jobs. China Mechanical Engineering, 33(21),
  29. Sun, X., Liu, T., Geng, X.-N., Hu, Y., & Xu, J.-X. (2022). Optimization of scheduling problems with deterioration effects and an optional maintenance activity. Journal of Scheduling, 1-16.
  30. Tafakkori, K., Tavakkoli-Moghaddam, R., & Siadat, A. (2022). Sustainable negotiation-based nesting and scheduling in additive manufacturing systems: A case study and multi-objective meta-heuristic algorithms. Engineering Applications of Artificial Intelligence, 112, 104836.
  31. Tian, Y., Gao, Z., Zhang, L., Chen, Y., & Wang, T. (2023). A Multi-Objective Optimization Method for Flexible Job Shop Scheduling Considering Cutting-Tool Degradation with Energy-Saving Measures. Mathematics, 11(2),
  32. Vahedi-Nouri, B., Tavakkoli-Moghaddam, R., Hanzálek, Z., Arbabi, H., & Rohaninejad, M. (2021). Incorporating order acceptance, pricing and equity considerations in the scheduling of cloud manufacturing systems: matheuristic methods. International Journal of Production Research, 59(7), 2009-2027.
  33. Vital-Soto, A., Baki, M. F., & Azab, A. (2023). A multi-objective mathematical model and evolutionary algorithm for the dual-resource flexible job-shop scheduling problem with sequencing flexibility. Flexible Services and Manufacturing Journal, 35(3), 626-668.
  34. Wong, K. H., Mason, C. W., Devaraj, S., Ouyang, J., & Balaya, P. (2014). Low temperature aqueous electrodeposited TiO x thin films as electron extraction layer for efficient inverted organic solar cells. ACS applied materials & interfaces, 6(4), 2679-2685.
  35. Woo, Y.-B., & Kim, B. S. (2018). Matheuristic approaches for parallel machine scheduling problem with time-dependent deterioration and multiple rate-modifying activities. Computers & Operations Research, 95, 97-112.
  36. Wu, X., Peng, J., Xiao, X., & Wu, S. (2021). An effective approach for the dual-resource flexible job shop scheduling problem considering loading and unloading. Journal of Intelligent Manufacturing, 32, 707-728.
  37. Xie, J., Gao, L., Peng, K., Li, X., & Li, H. (2019). Review on flexible job shop scheduling. IET Collaborative Intelligent Manufacturing, 1(3), 67-77.
  38. Yan, Q., Wang, H., & Wu, F. (2022). Digital twin-enabled dynamic scheduling with preventive maintenance using a double-layer Q-learning algorithm. Computers & Operations Research, 144, 105823.
  39. Yang, G., Chung, B. D., & Lee, S. J. (2019). Limited search space-based algorithm for dual resource constrained scheduling problem with multilevel product structure. Applied Sciences, 9(19),
  40. Youn, S., Geismar, H. N., & Pinedo, M. (2022). Planning and scheduling in healthcare for better care coordination: Current understanding, trending topics, and future opportunities. Production and Operations Management, 31(12), 4407-4423.
  41. Zhang, S., Du, H., Borucki, S., Jin, S., Hou, T., & Li, Z. (2021). Dual resource constrained flexible job shop scheduling based on improved quantum genetic algorithm. Machines, 9(6),
  42. Zhang, S., Hou, T., Qu, Q., Glowacz, A., Alqhtani, S. M., Irfan, M., . . . Li, Z. (2022). An Improved Mayfly Method to Solve Distributed Flexible Job Shop Scheduling Problem under Dual Resource Constraints. Sustainability, 14(19), 12120.
  43. Zheng, X.-l., & Wang, L. (2016). A knowledge-guided fruit fly optimization algorithm for dual resource constrained flexible job-shop scheduling problem. International Journal of Production Research, 54(18), 5554-5566.
  44. Ziaee, M., Mortazavi, J., & Amra, M. (2022). Flexible job shop scheduling problem considering machine and order acceptance, transportation costs, and setup times. Soft Computing, 1-17.
  45. Zonta, T., Da Costa, C. A., da Rosa Righi, R., de Lima, M. J., da Trindade, E. S., & Li, G. P. (2020). Predictive maintenance in the Industry 4.0: A systematic literature review. Computers & Industrial Engineering, 150, 106889.