Optimal solution of printing press-flexible job-shop scheduling problem (PP-FJSSP) with exact and heuristic algorithms

  • Authors

    • Nse Udoh Department of Statistics, University of Uyo https://orcid.org/0000-0002-3983-805X
    • Nkereuwem Okonna Department of Statistics, University of Uyo
    • Iniobong Uko Department of Statistics, University of Uyo
    2024-10-10
    https://doi.org/10.14419/v56nhd77
  • Scheduling; Flexible Job-Shop; Alldiferent Constraint Programming; Makespan; Optimality Gap; Integer Linear Programming.

  • Abstract

    In production related industries, optimizing scare resources and machine operations is one of the main goals toward improving operational efficiency and productivity while reducing cost. The Job shop scheduling problem (JSSP) model where one job can be process on one type of machine at a particular time is key to achieving this. However, Flexible job shop scheduling problem (FJSSP) extends JSSP by allowing machine operation to be processed by any qualified alternative machines. On this premise, this work seeks to optimize the operation of printing press system with j-jobs, k-tasks and m-machines using two optimization models viz: Integer Linear Programing (ILP) and Alldifferent Constraints Programing (ACP) models with a view to identifying the best model for this class of problem in terms of minimum makespan, optimality gap and computational time criteria as performance indicators. The ACP model yielded a comparative better result with makepan value of 233 minutes and optimal solution time of 0.21 seconds as against the ILP model with makespan value of 233 minutes and optimal solution time of 1.87 seconds. Hence, the ACP model is recommended for optimal operation in the printing company.

  • References

    1. Senthiil, P. V., Selladurai, V., & Rajesh, R. (2007). Parallel machine scheduling (PMS) in manufacturing systems using the ant colony optimization algorithmic rule. Journal of Applied Sciences, 7(2), 208-213. https://doi.org/10.3923/jas.2007.208.213.
    2. Roy, R. N. (2007). A modern approach to operations management. New Age International (P) Limited.
    3. Chaudhry, I. A., Mahmood, S., & Ahmad, R. (2010, June). Minimizing makespan for machine scheduling and worker assignment problem in identical parallel machine models using GA. Proceedings of the World Congress on Engineering, 3.
    4. Motaghedi-Larijani, A., Sabri-laghaie, K., & Heydari, M. (2010). Solving flexible job shop scheduling with multi-objective approach. International Journal of Industrial Engineering and Production Research, 21(4), 197-209.
    5. Agrawal, R., Pattanaik, L. N., & Kumar, S. (2012). Scheduling of a flexible job-shop using a multi-objective genetic algorithm. Journal of Advances in Management Research, 9(2), 178-188. https://doi.org/10.1108/09727981211271922.
    6. 23:25, 21/09/2024] +234 811 368 7403: [6] Krajewski, L. J., Malhotra, M. K., & Ritzman, L. P. (2016). Operations Management Pro-cesses and Supply Chains. Pearson Education.
    7. Ziaee, M., Mortazavi, J., & Amra, M. (2022). Flexible job shop scheduling problem considering machine and order acceptance, trans-portation costs, and setup times. Soft Computing, 1-17. https://doi.org/10.1007/s11740-022-01145-8.
    8. Schworm, P., Wu, X., Glatt, M., & Aurich, J. C. (2023). Solving flexible job shop scheduling problems in manufacturing with Quantum Annealing. Production Engineering, 17(1):105-115. https://doi.org/10.1007/978-3-030-27192-3.
    9. Błażewicz, J., Ecker, K., Pesch, E., Schmidt, G., Sterna, M., & Węglarz, J. (2019). Handbook on scheduling: From theory to practice. Springer. https://doi.org/10.1111/poms.13373.
    10. Naderi, B., Roshanaei, V., Begen, M. A., Aleman, D. M., & Urbach, D. R. (2021). Increased surgical capacity without additional re-sources: Generalized operating room planning and scheduling. Production and Operations Management, 30(8): 2608-2635.
    11. Pinedo, M. (2012). Scheduling: theory, algorithms and systems. Springer Science & Business Media. LLC. https://doi.org/10.1007/978-1-4614-2361-4.
    12. Vaghefinezhad, S., & Wong, K. Y. (2012). A genetic algorithm approach for solving a flexible job shop scheduling problem. arXiv preprint arXiv:1207.2253.
    13. 23:26, 21/09/2024] +234 811 368 7403: [13] Anshulika & Bewoor, L. A. (2017). A genetic algorithm approach for solving a job shop scheduling problem, 2017 International Conference on Computer Communication and Informatics (ICCCI), Coimbatore, 1-6. https://doi.org/10.1109/ICCCI.2017.8117720.
    14. Vital-Soto, A., Azab, A., & Baki, M. F. (2020). Mathematical modeling and a hybridized bacterial foraging optimization algorithm for the flexible job-shop scheduling problem with sequencing flexibility. Journal of Manufacturing Systems, 54: 74-93. https://doi.org/10.1016/j.jmsy.2019.12.003.
    15. Bayat Movahed, S. (2014). Linear programming assisted genetic algorithm for solving a comprehensive job shop lot streaming problem (Doctoral dissertation, University of Guelph).

  • Downloads