An Improved Computational Algorithm for Job Shop Scheduling Problems

  • Authors

    • Anishabun Khyllemkharai Research Scholar, Department of Mathematics & Statistics, Sam Higginbottom University of Agriculture, Technology and Sciences ‎‎(SHUATS), Prayagraj, Uttar Pradesh
    • Roselin Antony Professor, Department of Mathematics & Statistics, Sam Higginbottom University of Agriculture, Technology and Sciences (SHUATS), ‎Prayagraj, Uttar Pradesh
    https://doi.org/10.14419/s6trda64
  • Idle Time; Johnson's Algorithm; Makespan; Metaheuristics; Scheduling; Sequencing

  • Abstract

    Scheduling problems, a core area in operations research and computer science, involve optimizing the allocation of resources over time to ‎complete a set of tasks or jobs, often subject to various constraints. These problems arise in diverse real-world scenarios, from manufacturing-‎ing and project management to resource allocation in computing systems. The core objective is to find the best schedule that minimizes or ‎maximizes a specific performance measure, such as makespan (total time to complete all tasks), total completion time, or total tardi-‎ness. Formalization of scheduling problems is very often mathematically and directly bound to a solving method. It allows one to use the ‎properties of the problem to face the complexity of its resolution. The present work deals with sequencing problems for ‘n’ jobs on two ‎machines and ‘n’ jobs on m machines. A new metaheuristic algorithm is provided for obtaining an optimal sequence, for determining the ‎minimum duration of the makespan, and also for finding the minimum idle time of the given machines‎.

  • References

    1. Li, W., Yang, Y., Xiao, M., Chen, X., Sterna, M., & Błażewicz, J. (2025). “Scheduling with a discounted profit criterion on identical machines.”, Discrete Applied Mathematics, Vol. 367, PP. 195–209. https://doi.org/10.1016/j.dam.2025.02.015.
    2. Agnetis, A., Billaut, J.-C., Pinedo, M. L., & Shabtay, D. (2025). “Fifty Years of Research in Scheduling — Theory and Applications.” European Journal of Operational Research, Vol. 327(2), PP. 367–393. https://doi.org/10.1016/j.ejor.2025.01.034.
    3. Wang, J. B., Sun, Z. W., and Gao, M. (2025): “Research on single-machine scheduling with due-window assignment and resource allocation under total resource consumption cost is bounded.”; Journal of Applied Mathematics and Computing, https://doi.org/10.1007/s12190-025-02599-6.
    4. Khyllemkharai, A. and Antony, R. (2025): “New Optimal Algorithms for solving Scheduling problems”, M.Sc. Dissertation, Department of Math-ematics and Statistics, Sam Higginbottom University of Agriculture, Technology and Sciences (SHUATS), Prayagraj, India
    5. Antony, R. (2025): “Heuristic and Metaheuristic Algorithms for solving Scheduling Problems.”; International Journal of Innovative Research and Technology, Vol. 12, Issue 3, ISSN: 2349-6002
    6. Maurya, I. and Antony, R. (2024): “New methods for solving sequencing problems.”, M.Sc. Dissertation, Department of Mathematics and Statis-tics, Sam Higginbottom University of Agriculture, Technology and Sciences (SHUATS), Prayagraj, India
    7. Wu, G. and Zhu, H, (2024): “Single-Machine Rescheduling with Rejection and an Operator No-Availability Period.”; Mathematics, Vol. 12(23), PP. 3678, https://doi.org/10.3390/math12233678.
    8. Marko Ɖurasević, M. and Domagoj Jakobovic, D. (2022): “Heuristic and metaheuristic methods for the parallel unrelated machines scheduling problem: a survey.”; Artificial Intelligence Review, Vol. 56(3), https://doi.org/10.1007/s10462-022-10247-9.
    9. Van, B. K. and Hop, N. V. (2021): “Genetic algorithm with initial sequence for parallel machines scheduling with sequence dependent setup times based on earliness- tardiness.”; Journal of Industrial and Production Engineering, Vol. 38(1), PP. 18-28, https://doi.org/10.1080/21681015.2020.1829111.
    10. Srikant, G., Irfan, A. and Ahmed, A. (2016): “A New algorithm for solving job shop sequencing problem.”; International Journal of Computer Sci-ence Engineering (IJCSE), Vol. 5(2), PP. 93-100
    11. Zhang, R., Song, S. and Chen, A. (2013): “A hybrid artificial bee colony algorithm for the job shop scheduling problem.”; International Journal of Production Economics, Vol. 141(1), PP. 167–178, https://doi.org/10.1016/j.ijpe.2012.03.035.
    12. Maggu, A. (2002): “On two machines production scheduling problem to minimize total expected time of jobs or to minimize total expected idle time of machines.”; PAMS, Vol. LV(1-2), PP. 65-67
    13. Daniels, R. L., Hua, S. Y. and Webster, S. T. (1999): “Heuristics for parallel-machine flexible-resource scheduling problems with unspecified job assignment.”; Computers & Operations Research, Vol. 26(2), PP. 143-155, https://doi.org/10.1016/S0305-0548(98)00054-9.
    14. Guinet, A. (1991): “Textile Production Systems: A Succession of Non-Identical Parallel Processor Shops.”; Journal of the Operational Research Society, Vol. 42(8), PP. 655-671, https://doi.org/10.1057/jors.1991.132.
    15. Chang, Y. L., Sullivan, R. S., Bagchi, U. and Wilson, J. R. (1985): “Experimental investigation of real-time scheduling in flexible manufacturing systems.”; Annals of Operations Research, Vol. 3(7), PP. 355-377, https://doi.org/10.1007/BF02023749.
    16. Vickson, R. (1980): “Two Single Machine Sequencing Problems Involving Controllable Job Processing Times.”; IIE Transactions, Vol. 12(3), PP. 258-262, https://doi.org/10.1080/05695558008974515 .
    17. Baker, K. R. and Martin, J. B. (1974): “An Experimental Comparison of Solution Algorithms for the Single-Machine Tardiness Problem.”; Naval Research Logistics Quarterly, Vol. 21(1), PP. 187 – 199, https://doi.org/10.1002/nav.3800210114.
    18. Wagner, H. M. (1959): “An Integer Linear-Programming Model for Machine Scheduling.”; Naval Research Logistics Quarterly, Vol. 6(2), PP. 131 – 140, https://doi.org/10.1002/nav.3800060205.
    19. Johnson, S.M. (1954): “Optimal two stage and three stage production schedules with setup times included.”; Naval Research Logistics Quarterly, Vol. 1(1), PP. 61-68. https://doi.org/10.1002/nav.3800010110.

  • Downloads

  • How to Cite

    Khyllemkharai , A. ., & Antony , R. . (2025). An Improved Computational Algorithm for Job Shop Scheduling Problems. International Journal of Advanced Mathematical Sciences, 11(2), 83-91. https://doi.org/10.14419/s6trda64