Multi-objective flexible job shop scheduling problem based on monte-carlo tree search

Tung Ying Wu, I-Chen Wu, Chao Chin Liang

    Research output: Contribution to conferencePaperpeer-review

    9 Scopus citations

    Abstract

    Flexible job-shop scheduling problem (FJSP) is very important in both fields of production management and combinatorial optimization. This paper focuses on the multiobjective flexible job shop scheduling problem (MO-FJSP) with three objectives which minimizing make span, total workload and maximal workload, respectively, with Pareto manner. In addition, Monte-Carlo Tree Search (MCTS) is successful in computer Go and many other games. Hence, solving FJSP by MCTS is a new attempt. In this paper, we propose an MCTS algorithm for FJSP, by incorporating Variable Neighborhood Descent Algorithm and other techniques like Rapid Action Value Estimates Heuristic and Transposition Table. Our algorithm finds Pareto solutions of the benchmark problems proposed by Kacem et al. within 116 seconds: 4 solutions in 4×5, 3 in 10×7, 4 in 8×8, 4 in 10×10 and 2 in 15×10. These solutions are the same as the best found to date. Although one article claimed to have an extra 8×8 solution, that article did not find some of the above solutions.

    Original languageEnglish
    Pages73-78
    Number of pages6
    DOIs
    StatePublished - 1 Jan 2013
    Event2013 Conference on Technologies and Applications of Artificial Intelligence, TAAI 2013 - Taipei, Taiwan
    Duration: 6 Dec 20138 Dec 2013

    Conference

    Conference2013 Conference on Technologies and Applications of Artificial Intelligence, TAAI 2013
    Country/TerritoryTaiwan
    CityTaipei
    Period6/12/138/12/13

    Keywords

    • Evolutionary Algorithm
    • Monte-Carlo Tree Search
    • Multi-Objective Flexible Job Shop Scheduling Problem
    • Rapid Action Value Estimates
    • Variable Neighborhood Descent Algorithm

    Fingerprint

    Dive into the research topics of 'Multi-objective flexible job shop scheduling problem based on monte-carlo tree search'. Together they form a unique fingerprint.

    Cite this