Improvement of job shop scheduling method based on mathematical optimization and machine learning (2024)

research-article

Authors: Eiji Morinaga, Xuetian Tang, Koji Iwamura, and Naoki Hirabayashi

Volume 232, Issue C

Pages 871 - 879

Published: 02 July 2024 Publication History

  • 0citation
  • 0
  • Downloads

Metrics

Total Citations0Total Downloads0

Last 12 Months0

Last 6 weeks0

  • Get Citation Alerts

    New Citation Alert added!

    This alert has been successfully added and will be sent to:

    You will be notified whenever a record that you have chosen has been cited.

    To manage your alert preferences, click on the button below.

    Manage my Alerts

    New Citation Alert!

    Please log in to your account

      • View Options
      • References
      • Media
      • Tables
      • Share

    Abstract

    This research is concerned with finding the optimal solution of a job shop scheduling problem (JSSP) in a shorter time. As a result of recent trends such as Industry 4.0, machine learning has received a lot of attention, and job shop scheduling methods using machine learning techniques have been developed. We have focused on hybridization of machine learning and mathematical optimization. A JSSP can be formulated as a 0-1 mixed integer programming, and it is expected that the optimal solution can be obtained in a shorter time by providing a good initial solution for the optimization algorithm by means of a learner constructed with data of scheduling performed previously. In our method based on this idea, the processing times of all operations are used as input features to predict a good value of each binary variable which represents the precedence relationship between two operations processed on the same machine. However, the information about the operations which are not related to the intended two operations may work as noise in learning and prediction. In this paper, two limitation methods of input features are proposed. In one of the methods, the processing times of only the operations processed on the same machine that the intended operations are processed are input to the learner. In the other methods, the processing times of those operations and their pre/post operations are input. Numerical experiments showed that these methods are effective at least from the point of view of efficient construction of a learner, because the number of nodes in the input and hidden layers can be reduced. From the aspect of better learning and prediction, both of the methods worked well, that is, they could find the optimal solution in a shorter time than the previous method in the cases where the previous method could not achieve good prediction and took a relatively long solution time. However, in the cases where the previous method could solve the problem in a relatively short time, the limitation methods could not predict a good initial solution and took a relatively long solution time. Between the results of the two limitation methods, there were no difference. These results imply that the processing times of the pre/post operations do not strongly affect performance on learning and prediction and that it is important to analyze what makes a difference between the two cases and utilize the proposed methods in the former case.

    References

    [1]

    H. Greenberg, Harold, A Branch-Bound Solution to the General Scheduling Problem, Operations Research 16 (2) (1968) 353–361.

    [2]

    Ching-Jong Liao, Chii-Tsuen You, An improved formulation for the job-shop scheduling problem, Journal of the Operational Research Society 43 (11) (1992) 1047–1054.

    [3]

    Chao-Hsien Pan, A study of integer programming formulations for scheduling problems, International Journal of Systems Science 28 (1) (1997) 33–41.

    [4]

    Miloš. Šeda, Mathematical models of flow shop and job shop scheduling problems, International Journal of Physical and Mathematical Sciences 1 (7) (2007) 307–312.

    [5]

    Wen-Yang Ku, J.Christopher Beck, Mixed integer programming models for job shop scheduling: A computational analysis, Computers & Operations Research 73 (2016) 165–173.

    [6]

    Rei. Hino, Mathematical Optimization Models for Job-Shop Scheduling Problem, Systems, Control and Information 61 (1) (2017) 14–19. In Japanese.

    [7]

    John H. Blackstone, Don T. Phillips, Gary L. Hogg, A state-of-the-art survey of dispatching rules for manufacturing job shop operations, International Journal of Production Research 20 (1) (1982) 27–45.

    [8]

    Oliver Holthaus, Chandrasekharan. Rajendran, Efficient dispatching rules for scheduling in a job shop, International Journal of Production Economics 48 (1) (1997) 87–105.

    [9]

    Veronique Sels, Nele Gheysen, Mario. Vanhoucke, A comparison of priority rules for the job shop scheduling problem under different flow time- and tardiness-related objective functions, International Journal of Production Research 50 (15) (2012) 4255–4270.

    [10]

    Federico Della Croce, Roberto Tadei, Giuseppe Volta, A genetic algorithm for the job shop problem, Computers & Operations Research 22 (1) (1995) 15–24.

    [11]

    Runwei Cheng, Mitsuo Gen, Yasuhiro. Tsujimura, A tutorial survey of job-shop scheduling problems using genetic algorithms—I. representation, Computers & Industrial Engineering 30 (4) (1996) 983–997.

    [12]

    Runwei Cheng, Mitsuo Gen, Yasuhiro. Tsujimura, A tutorial survey of job-shop scheduling problems using genetic algorithms, part II. hybrid genetic search strategies, Computers & Industrial Engineering 36 (2) (1999) 343–364.

    [13]

    Peter J.M. van Laarhoven, Emile H.L. Aarts, Jan Karel Lenstra, Job shop scheduling by simulated annealing, Operations Research 40 (1) (1992) 113–125.

    [14]

    Kenta Teramoto, Eiji Morinaga, Hidefumi Wakamatsu, Eiji Arai, A Neighborhood Limitation Method for Job-Shop Scheduling Based on Simulated Annealing, Transactions of the Institute of Systems, Control and Information Engineers 33 (6) (2020) 171–181.

    [15]

    Hasan, S. M. Kamrul, Sarker, Ruhul, Essam, Daryl, and Cornforth, David. (2009) “A genetic algorithm with priority rules for solving job-shop scheduling problems.” in Chiong, Raymond and Dhakal, Sandeep (eds.) Natural Intelligence for Scheduling, Planning and Packing Problems. Studies in Computational Intelligence, vol. 250. pp. 55–88. Springer, Berlin, Heidelberg.

    [16]

    Mitsunobu Yoda, Toru Eguchi, Takeshi Murayama, Job shop scheduling for meeting due dates and minimizing overtime using genetic algorithm incorporating new priority rules, Journal of Advanced Mechanical Design, Systems, and Manufacturing 8 (5) (2014) JAMDSM0071.

    [17]

    Shady, Salama, Kaihara, Toshiya, Fujii, Nobutada, and Kokuryo, Daisuke. (2021) “A new representation and adaptive feature selection for evolving compact dispatching rules for dynamic job shop scheduling with genetic programming.” in Dolgui, Alexandre, Bernard, Alain, Lemoine, David, von Cieminski, Gregor and Romero, David (eds.) Advances in Production Management Systems. Artificial Intelligence for Sustainable and Resilient Production Systems. APMS 2021. IFIP Advances in Information and Communication Technology, vol. 632. pp. 646–654. Springer, Cham.

    [18]

    Maniezzo, Vittorio, Stützle, Thomas, Voß, Stefan. (eds.) (2010) Matheuristics—Hybridizing metaheuristics and mathematical programming. Springer US.

    [19]

    Eduardo Guzman, Beatriz Andres, Raul. Poler, Matheuristic Algorithm for Job-Shop Scheduling Problem Using a Disjunctive Mathematical Model, Computers 11 (1) (2022) 1.

    [20]

    Klaus-Dieter Thoben, Stefan Wiesner, Thorsten Wuest, Industrie 4.0” and Smart Manufacturing — A Review of Research Issues and Application Examples, International Journal of Automation Technology 11 (1) (2017) 4–16.

    [21]

    László Monostori, Botond Kádár, Thomas Bauernhansl, Shinsuke Kondoh, Soundar Kumara, Gunther Reinhart, Olaf Sauer, Günther Schuh, Wilfried Sihn, Kanji Ueda, Cyber-physical systems in manufacturing, CIRP Annals 65 (2) (2016) 621–641.

    [22]

    Anant Singh Jain, Meeran Sheik, Job-shop scheduling using neural networks, International Journal of Production Research 36 (5) (1998) 1249–1272.

    [23]

    Gary R. Weckman, Chandrasekhar V. Ganduri, David A Koonce, A neural network job-shop scheduler, Journal of Intelligent Manufacturing 19 (2) (2008) 191–201.

    [24]

    B. Giffler, G.L. Thompson, Algorithms for Solving Production-Scheduling Problems, Operations Research 8 (4) (1960) 487–503.

    [25]

    Zelin Zang, Wanliang Wang, Yuhang Song, Linyan Lu, Weikun Li, Yule Wang, Yanwei Zhao, Hybrid Deep Neural Network Scheduler for Job-Shop Problem Based on Convolution Two-Dimensional Transformation, Computational Intelligence and Neuroscience (2019).

    [26]

    Paolo Priore, Alberto Gómez, Raúl Pino, Rafael Rosillo, Dynamic scheduling of manufacturing systems using machine learning: An updated review, Artificial Intelligence for Engineering Design, Analysis and Manufacturing 28 (1) (2014) 83–97.

    [27]

    Zhang Cong, Song Wen, Cao Zhiguang, Zhang Jie, Tan Puay Siew, Xu Chi, Learning to dispatch for job shop scheduling via deep reinforcement learning, in: Proceedings of the 34th International Conference on Neural Information Processing Systems, 2020, pp. 1621–1632.

    [28]

    Toru Eguchi, Eitetsu Hayashi, Takeshi Murayama, Learning priority rule using neural network for job shop scheduling with regard to weighted tardiness, in: Proceedings of the 10th International Conference on Leading Edge Manufacturing in 21st Century, 2021, p. 175.

    [29]

    Eiji Morinaga, Naoki Otsuka, Hidefumi Wakamatsu, Xuetian Tang, Koji Iwamura, Naoki Hirabayashi, A basic study on data-driven job shop scheduling, in: Proceedings of the International Conference on Design and Concurrent Engineering 2021 & Manufacturing Systems Conference 2021, 2021, p. 46.

    [30]

    Eiji Morinaga, Xuetian Tang, Koji Iwamura, Naoki Hirabayashi, An improved method of job shop scheduling using machine learning and mathematical optimization, Procedia Computer Science 217 (2022) 1479–1489.

    [31]

    Fisher, H., and Thompson, G. L. (1963) “Probabilistic learning combinations of local job-shop scheduling rules.” in Muth, J. F. and Thompson, G. L. (eds.) Industrial Scheduling, 225–251. Prentice-Hall.

    Recommendations

    • An improved method of job shop scheduling using machine learning and mathematical optimization

      Abstract

      This research is concerned with finding the optimal solution of a job shop scheduling problem (JSSP) in as short time as possible. A JSSP can be formulated as a 0-1 mixed integer programming (0-1 MIP), and it is expected that the optimal schedule ...

      Read More

    • Heuristic Optimization for Dual-resource Constrained Job Shop Scheduling

      CAR '09: Proceedings of the 2009 International Asia Conference on Informatics in Control, Automation and Robotics

      In the study of job shop scheduling problem in mass injection molding processing enterprises, the practical job shop scheduling environment cannot be mirrored in the traditional study only considering machine resources. A dual-resource (machines and ...

      Read More

    • A GEP-based reactive scheduling policies constructing approach for dynamic flexible job shop scheduling problem with job release dates

      Flexible job shop scheduling problem (FJSSP) is generalization of job shop scheduling problem (JSSP), in which an operation may be processed on more than one machine each of which has the same function. Most previous researches on FJSSP assumed that all ...

      Read More

    Comments

    Information & Contributors

    Information

    Published In

    Improvement of job shop scheduling method based on mathematical optimization and machine learning (5)

    Procedia Computer Science Volume 232, Issue C

    2024

    3296 pages

    ISSN:1877-0509

    EISSN:1877-0509

    Issue’s Table of Contents

    Copyright © 2024.

    Publisher

    Elsevier Science Publishers B. V.

    Netherlands

    Publication History

    Published: 02 July 2024

    Author Tags

    1. Data-driven job shop scheduling
    2. 0-1 mixed integer programming
    3. Multilayer neural network
    4. Input feature
    5. Solution time

    Qualifiers

    • Research-article

    Contributors

    Improvement of job shop scheduling method based on mathematical optimization and machine learning (6)

    Other Metrics

    View Article Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Total Citations

    • Total Downloads

    • Downloads (Last 12 months)0
    • Downloads (Last 6 weeks)0

    Other Metrics

    View Author Metrics

    Citations

    View Options

    View options

    Get Access

    Login options

    Check if you have access through your login credentials or your institution to get full access on this article.

    Sign in

    Full Access

    Get this Publication

    Media

    Figures

    Other

    Tables

    Improvement of job shop scheduling method based on mathematical optimization and machine learning (2024)
    Top Articles
    Latest Posts
    Article information

    Author: Fr. Dewey Fisher

    Last Updated:

    Views: 5669

    Rating: 4.1 / 5 (62 voted)

    Reviews: 93% of readers found this page helpful

    Author information

    Name: Fr. Dewey Fisher

    Birthday: 1993-03-26

    Address: 917 Hyun Views, Rogahnmouth, KY 91013-8827

    Phone: +5938540192553

    Job: Administration Developer

    Hobby: Embroidery, Horseback riding, Juggling, Urban exploration, Skiing, Cycling, Handball

    Introduction: My name is Fr. Dewey Fisher, I am a powerful, open, faithful, combative, spotless, faithful, fair person who loves writing and wants to share my knowledge and understanding with you.