{"id":219839,"date":"2026-01-15T14:59:29","date_gmt":"2026-01-15T12:59:29","guid":{"rendered":"https:\/\/azbuki.bg\/?p=219839"},"modified":"2026-01-15T14:59:29","modified_gmt":"2026-01-15T12:59:29","slug":"solving-the-job-shop-scheduling-problem-different-techniques-and-programming-languages","status":"publish","type":"post","link":"https:\/\/azbuki.bg\/en\/uncategorized\/solving-the-job-shop-scheduling-problem-different-techniques-and-programming-languages\/","title":{"rendered":"Solving the Job Shop Scheduling Problem – Different Techniques and Programming Languages"},"content":{"rendered":"

Sofoklis Christoforidis<\/strong><\/p>\n

Efstathios Titopoulos<\/strong><\/p>\n

Democritus University <\/em>of Thrace (Greece)<\/em><\/p>\n

Boryana Mihaylova<\/strong><\/p>\n

Technical University of Sofia (Bulgaria)<\/em><\/p>\n

Eleni Kromitoglou<\/strong><\/p>\n

Stergios Intzes<\/strong><\/p>\n

Democritus University <\/em>of Thrace (Greece)<\/em><\/p>\n

https:\/\/doi.org\/10.53656\/voc25-3-4-12<\/a><\/p>\n

Abstract. <\/strong>The Job Shop Scheduling Problem (JSSP) is a long-standing combinatorial optimization problem studied since the 1960s. JSSP is NP-complete, meaning solutions exist but cannot be guaranteed within polynomial time for general instances. In this paper we aim to compare some algorithms and techniques that have been proposed by various researchers. We also present the execution of these algorithms using two programming languages, python and C#.<\/p>\n

Keywords: <\/em>Genetic Algorithm, Metaheuristics, Constraint Programming<\/p>\n

 <\/p>\n

    \n
  1. Introduction<\/strong><\/li>\n<\/ol>\n

    JSSP is also one of the most challenging problems that researchers have been trying to solve since the 1960s. Simply put, we can specify the problem as a scheduling problem with a finite set of tasks, J = {1, 2,\u2026., n} to schedule on a finite set of machine collections, M = {1, 2,\u2026., m} with each task having a distinct completion time T = {1,2, \u2026, n}.<\/p>\n

    Of course, we should clarify that there are various constraints such as an operation should be processed only after all previous operations related to this object have been completed and the resource constraint should be applied which states that each task should be processed on the machine exactly once. The completion time of a task consisting of many tasks is defined from the processing of the first task to the completion of the processing of the last task. It should be clarified that the tasks should not be interrupted, and this time is known as the make-span of the schedule. This is the time that must be minimized. JSSP is such a complex combinatorial problem that for an optimal solution in a reasonable time it is done using heuristic techniques.<\/p>\n

    We make a bibliographic survey of the different methods that have been applied to find a solution to the problem in the following paper. By applying methods that develop algorithms based on GA, we show applications that have been developed with the python programming language.<\/p>\n

     <\/p>\n

      \n
    1. The Main Methods for JSSP<\/strong><\/li>\n<\/ol>\n

      The main methods for JSSP are:<\/p>\n

        \n
      1. Exact \/ Mathematical Programming Approaches<\/li>\n<\/ol>\n

        \u2013 Branch and Bound, Branch and Cut<\/p>\n

        \u2013 Integer Linear Programming (ILP), Constraint Programming (CP)<\/p>\n

          \n
        1. Dispatching Rules & Priority Heuristics<\/li>\n<\/ol>\n

          \u2013 Simple rules like SPT (Shortest Processing Time), LPT, EDD, etc.<\/p>\n

          \u2013 Composite dispatching rules<\/p>\n

            \n
          1. Metaheuristics<\/li>\n<\/ol>\n

            \u2013 Genetic Algorithms (GA), Simulated Annealing (SA), Tabu Search (TS), Ant Colony Optimization (ACO), Particle Swarm Optimization (PSO)<\/p>\n

              \n
            1. Hybrid & Memetic Algorithms<\/li>\n<\/ol>\n

              \u2013 Combinations of GA + Local Search, TS + SA, etc.<\/p>\n

                \n
              1. Constraint-Based & AI \/ Learning Approaches<\/li>\n<\/ol>\n

                \u2013 Constraint Programming (CP), Reinforcement Learning (RL), Neural Networks (NNs), Deep Learning<\/p>\n

                  \n
                1. Decomposition & Relaxation Methods<\/li>\n<\/ol>\n

                  \u2013 Lagrangian Relaxation, Benders Decomposition, Dantzig-Wolfe<\/p>\n

                  Summary Table 1 for the most citation paper for the above methods.<\/p>\n

                  The new literature review for the methods \/ algorithms which use for the solved the JSSP:<\/p>\n

                  Exact and constraint programming<\/p>\n

                  \u2013 CP\/OR integration:<\/strong> (Infantes et al., 2024b, 2024a)<\/p>\n

                  \u2013 CP for dynamic dispatch:<\/strong> (C. Zhang et al., 2020)<\/p>\n

                  \u2013 Survey:<\/strong> (Cebi et al., 2020a)<\/p>\n

                  \u2013 Constraint\/AI synthesis (chapter):<\/strong> (Infantes et al., 2024a)<\/p>\n

                  \u00a0<\/strong><\/p>\n

                  Table <\/strong>1<\/strong>.<\/strong> Most citation paper for the methods how to solve the JSSP.<\/p>\n\n\n\n\n\n\n\n\n\n\n
                  Method Family<\/strong><\/td>\nMost Cited Works<\/strong><\/td>\n<\/tr>\n<\/thead>\n
                  Exact \/ ILP \/ CP<\/td>\n(Applegate & Cook, 1991), (Brucker et al., 1994),<\/td>\n<\/tr>\n
                  Dispatching Rules<\/td>\n(Blackstone et al., 1982) (Panwalkar & Iskander, 1977) (Haupt, 1989)<\/td>\n<\/tr>\n
                  Metaheuristics<\/td>\n(Glover, 1989) (Nowicki & Smutnicki, 1996) (Ghedjati, 1999) (Dorigo & Gambardella, 1997)<\/td>\n<\/tr>\n
                  Hybrid \/ Memetic<\/td>\n(C. Y. Zhang et al., 2008) (Pezzella et al., 2008) (Louren\u00e7o, 1995)<\/td>\n<\/tr>\n
                  Constraint & AI<\/td>\n(Fromherz, 2001) (Baptiste et al., 2001) (Jain & Meeran, 1999) (Mnih et al., 2015)<\/td>\n<\/tr>\n
                  Decomposition<\/td>\n(Fisher, 1981) (Hooker, 2012)<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

                   <\/p>\n

                  There have been new developments aimed at augmenting classical constraint programming (CP) and integer programming methods with machine learning techniques for handling uncertainty. Infantes et al. (2024) presented a deep reinforcement learning (DRL) framework that is complemented with graph neural networks (GNNs) for producing robust schedules with uncertain task durations. This study is notable for a move away from classical methods to robust optimization, in which uncertainty is specifically defined and addressed.<\/p>\n

                  Dispatching rules and rule learning:<\/p>\n

                  \u2013 Learned PDRs:<\/strong> (C. Zhang et al., 2020)<\/p>\n

                  \u2013 ANN with dispatching rules:<\/strong> (Sim et al., 2020)<\/p>\n

                  \u2013 Real-time rule selection:<\/strong> (Zhao et al., 2023)<\/p>\n

                  \u2013 Systematic review of intelligent scheduling (includes rule learning):<\/strong> (Momenikorbekandi & Kalganova, 2025) (Rihane et al., 2025a)<\/p>\n

                  Classical priority dispatching rules (PDRs) like shortest processing time or most work remaining have been applied for many years to scheduling in real-time. But 2020 and afterwards consider adaptive and learned dispatching policies as key. Earlier work by Zhang and Dietterich on a paradigm of reinforcement learning has been generalized in the latest studies (2020\u20132023) to learn neural agents that adaptively choose dispatching rules and beat static heuristics in dynamic shop-floor settings. They show increasing importance of data-driven heuristics in overcoming the dichotomy between handcrafted policies and adaptive scheduling.<\/p>\n

                  Metaheuristics:<\/p>\n

                  \u2013 Hybrid evolutionary switching (DE\/PSO + TS):<\/strong> (Nadia, 2023)<\/p>\n

                  \u2013 Comprehensive metaheuristic study:<\/strong> (Benni et al., 2024)<\/p>\n

                  \u2013 AI for Flexible JSSP (metaheuristics + learning):<\/strong> (Nadia, 2023)<\/p>\n

                  \u2013 Intelligent scheduling review (metaheuristics emphasis):<\/strong> (Momenikorbekandi & Kalganova, 2025)<\/p>\n

                  Metaheuristics continue to dominate the applied JSSP literature, with hybrid evolutionary and swarm-based algorithms being particularly influential. For example, hybrid differential evolution and particle swarm optimization methods with embedded tabu search (2022) have shown strong performance on benchmark instances. Similarly, multi-objective metaheuristics developed after 2020 address not only makes pan but also tardiness and energy efficiency, reflecting the multi-criteria nature of modern manufacturing systems.<\/p>\n

                  Hybrid and memetic algorithms:<\/p>\n

                  \u2013 Switching strategy-based hybrid EAs (DE+PSO+TS):<\/strong> (Mahmud et al., 2022)<\/p>\n

                  \u2013 AI for FJSSP (hybrid schemes):<\/strong> (Nadia, 2023)<\/p>\n

                  \u2013 Intelligent scheduling systematic review (hybrid focus):<\/strong> (Momenikorbekandi & Kalganova, 2025)<\/p>\n

                  \u2013 Comprehensive metaheuristic study (hybrid comparisons):<\/strong> (Benni et al., 2024)<\/p>\n

                  The drift toward hybridization can also be found in new work that marries global search with local fine-tuning(Rego & Duarte, 2009). laid the groundwork for tabu search\/simulated annealing hybrids, and recent works (2021\u20132023) build on this by integrating deep learning modules with evolutionary structures. The resulting hybrids combine the pattern recognition ability of neural models with metaheuristics’ power to explore, achieving top-performing outcomes on adaptive JSSP variants.<\/p>\n

                  Learning-based approaches (RL\/GNN\/transformers):<\/p>\n

                  \u2013 DRL+GNN for uncertainty:<\/strong> (Infantes et al., 2024a) (Infantes et al., 2024b)<\/p>\n

                  \u2013 PDR via DRL:<\/strong> (C. Zhang et al., 2020)<\/p>\n

                  \u2013 Behavioral cloning \/ attention models for JSSP (2023 chapters referenced in<\/strong>\u2013 CPAIOR context):<\/strong>(Infantes et al., 2024b)<\/p>\n

                  \u2013 Review of learning-based methods: (Rihane et al., 2025a) (Rihane et al., 2025b)<\/p>\n

                  Perhaps the most transformative development since 2020 is the application of deep reinforcement learning and graph neural networks. (Infantes et al., 2024a) demonstrated that DRL agents can generalize across problem instances, learning scheduling policies that adapt to uncertainty. Other works (2021\u20132023) have explored curriculum learning, attention-based models, and imitation learning for dispatching, signalling a paradigm shift toward end-to-end learning systems that bypass handcrafted heuristics altogether.<\/p>\n

                  Decomposition and relaxation:<\/p>\n

                  \u2013 Uncertainty-aware schedules (robust angle; integrates with decomposition ideas):<\/strong> (Infantes et al., 2024b) (Infantes et al., 2024c)<\/p>\n

                  \u2013 Recent reviews touching Lagrangian\/Benders in JSSP contexts:<\/strong> (Cebi et al., 2020b)<\/p>\n

                  \u2013 Intelligent scheduling review (2025) with relaxation mentions in industrial settings:<\/strong> (Momenikorbekandi & Kalganova, 2025)<\/p>\n

                  \u2013 Metaheuristic\u2013relaxation hybrids surveyed:<\/strong> (Benni et al., 2024)<\/p>\n

                  The algorithm performed very well, outperforming many previous methods in the reduction of make-span.<\/p>\n

                  This is a hybrid algorithm that utilizes a global search with genetic crossover and mutation operators under a CA-like neighborhood. The above operators primarily fine-tune the order of the operations. Hill-climbing performs a local search to assign the best machine to each critical operation. This GA-RRHC aspect makes the formulation compatible with FJSSP instances possessing a lot of flexibility.<\/p>\n

                  CA-like neighborhood facilitates concurrent execution of genetic operations, thereby advancing enhanced exploration capability for the GA-RRHC. The hill-climbing yields comparable iteration numbers with other algorithms and is also straightforward to implement, with a moderate level of complexity. A common data set suite containing four files that represent a compendium of 101 various problems was adopted in the numerical experiments involving the GA-RRHC. The outcomes register enhanced effectiveness relative to contemporary comparison algorithms, primarily for higher flexibility scenarios.<\/p>\n

                  GA-RRHC presents a new way of achieving neighborhoods like that found in cultural algorithms that concurrently employ exploration and exploitation methods in dealing with different task scheduling problems like flow shops, job shop, and open shop cases.<\/p>\n

                  Future work can be the idea of using a different kind of exploitation approach such as simulated annealing, so that the local search can become less intensive. Other types of scaling algorithms can also be attempted for enhancing the sequences of the operations for solving instances of FJSSP with low flexibility, with further extension of such a methodology for optimization problems with multiple objectives.<\/p>\n

                   <\/p>\n

                    \n
                  1. Solving Job-Shop Scheduling Problems by Genetic Algorithm<\/strong><\/li>\n<\/ol>\n

                    Genetic Algorithm (GA)-based approach<\/strong> to solving the Job-Shop Scheduling Problem (JSP)<\/strong>, which is known for its complexity due to large combinatorial search spaces and precedence constraints between machines. Traditional methods like branch-and-bound<\/strong> struggle with scalability, making GA a promising alternative.<\/p>\n