A new MCTS-based algorithm for multi-objective flexible job shop scheduling problem

Jen Jai Chou; Chao Chin Liang; Hung Chun Wu; I-Chen Wu; Tung Ying Wu

doi:10.1109/TAAI.2015.7407061

A new MCTS-based algorithm for multi-objective flexible job shop scheduling problem

Jen Jai Chou, Chao Chin Liang, Hung Chun Wu, I-Chen Wu, Tung Ying Wu

Institute of Multimedia Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

2 Scopus citations

Abstract

Multi-objective flexible job-shop scheduling problem (MO-FJSP) is very important in both fields of production management and combinatorial optimization. Wu et al. proposed a Monte-Carlo Tree Search (MCTS) to solve MO-FJSP and successfully improved the performance of MCTS to find 17 Pareto solutions: 4 of Kacem 4×5, 3 of 10×7, 4 of 8×8, 4 of 10×10, and 2 of 15×10. This paper proposes a new MCTS-based algorithm for MO-FJSP problem by modifying their algorithm. Our experimental results show that our new algorithm significantly outperforms their algorithm for large problems, especially for Kacem 15×10. This shows that the new algorithm tends to have better potential of solving harder MO-FJSP problems.

Original language	English
Title of host publication	TAAI 2015 - 2015 Conference on Technologies and Applications of Artificial Intelligence
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	136-141
Number of pages	6
ISBN (Electronic)	9781467396066
DOIs	https://doi.org/10.1109/TAAI.2015.7407061
State	Published - 12 Feb 2016
Event	Conference on Technologies and Applications of Artificial Intelligence, TAAI 2015 - Tainan, Taiwan Duration: 20 Nov 2015 → 22 Nov 2015

Publication series

Name	TAAI 2015 - 2015 Conference on Technologies and Applications of Artificial Intelligence

Conference

Conference	Conference on Technologies and Applications of Artificial Intelligence, TAAI 2015
Country	Taiwan
City	Tainan
Period	20/11/15 → 22/11/15

Keywords

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

Access to Document

10.1109/TAAI.2015.7407061

Link to publication in Scopus

Fingerprint Dive into the research topics of 'A new MCTS-based algorithm for multi-objective flexible job shop scheduling problem'. Together they form a unique fingerprint.

Cite this

Chou, J. J., Liang, C. C., Wu, H. C., Wu, I-C., & Wu, T. Y. (2016). A new MCTS-based algorithm for multi-objective flexible job shop scheduling problem. In TAAI 2015 - 2015 Conference on Technologies and Applications of Artificial Intelligence (pp. 136-141). [7407061] (TAAI 2015 - 2015 Conference on Technologies and Applications of Artificial Intelligence). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/TAAI.2015.7407061

Chou, Jen Jai ; Liang, Chao Chin ; Wu, Hung Chun ; Wu, I-Chen ; Wu, Tung Ying. / A new MCTS-based algorithm for multi-objective flexible job shop scheduling problem. TAAI 2015 - 2015 Conference on Technologies and Applications of Artificial Intelligence. Institute of Electrical and Electronics Engineers Inc., 2016. pp. 136-141 (TAAI 2015 - 2015 Conference on Technologies and Applications of Artificial Intelligence).

@inproceedings{c8ed6ef2b5834ce6b7139ceafb9c6b7c,

title = "A new MCTS-based algorithm for multi-objective flexible job shop scheduling problem",

abstract = "Multi-objective flexible job-shop scheduling problem (MO-FJSP) is very important in both fields of production management and combinatorial optimization. Wu et al. proposed a Monte-Carlo Tree Search (MCTS) to solve MO-FJSP and successfully improved the performance of MCTS to find 17 Pareto solutions: 4 of Kacem 4×5, 3 of 10×7, 4 of 8×8, 4 of 10×10, and 2 of 15×10. This paper proposes a new MCTS-based algorithm for MO-FJSP problem by modifying their algorithm. Our experimental results show that our new algorithm significantly outperforms their algorithm for large problems, especially for Kacem 15×10. This shows that the new algorithm tends to have better potential of solving harder MO-FJSP problems.",

keywords = "Evolutionary Algorithm, Monte-Carlo Tree Search, Multi-Objective Flexible Job Shop Scheduling Problem, Rapid Action Value Estimates",

author = "Chou, {Jen Jai} and Liang, {Chao Chin} and Wu, {Hung Chun} and I-Chen Wu and Wu, {Tung Ying}",

year = "2016",

month = feb,

day = "12",

doi = "10.1109/TAAI.2015.7407061",

language = "English",

series = "TAAI 2015 - 2015 Conference on Technologies and Applications of Artificial Intelligence",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "136--141",

booktitle = "TAAI 2015 - 2015 Conference on Technologies and Applications of Artificial Intelligence",

note = "null ; Conference date: 20-11-2015 Through 22-11-2015",

}

Chou, JJ, Liang, CC, Wu, HC, Wu, I-C & Wu, TY 2016, A new MCTS-based algorithm for multi-objective flexible job shop scheduling problem. in TAAI 2015 - 2015 Conference on Technologies and Applications of Artificial Intelligence., 7407061, TAAI 2015 - 2015 Conference on Technologies and Applications of Artificial Intelligence, Institute of Electrical and Electronics Engineers Inc., pp. 136-141, Conference on Technologies and Applications of Artificial Intelligence, TAAI 2015, Tainan, Taiwan, 20/11/15. https://doi.org/10.1109/TAAI.2015.7407061

A new MCTS-based algorithm for multi-objective flexible job shop scheduling problem. / Chou, Jen Jai; Liang, Chao Chin; Wu, Hung Chun; Wu, I-Chen; Wu, Tung Ying.

TAAI 2015 - 2015 Conference on Technologies and Applications of Artificial Intelligence. Institute of Electrical and Electronics Engineers Inc., 2016. p. 136-141 7407061 (TAAI 2015 - 2015 Conference on Technologies and Applications of Artificial Intelligence).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - A new MCTS-based algorithm for multi-objective flexible job shop scheduling problem

AU - Chou, Jen Jai

AU - Liang, Chao Chin

AU - Wu, Hung Chun

AU - Wu, I-Chen

AU - Wu, Tung Ying

PY - 2016/2/12

Y1 - 2016/2/12

N2 - Multi-objective flexible job-shop scheduling problem (MO-FJSP) is very important in both fields of production management and combinatorial optimization. Wu et al. proposed a Monte-Carlo Tree Search (MCTS) to solve MO-FJSP and successfully improved the performance of MCTS to find 17 Pareto solutions: 4 of Kacem 4×5, 3 of 10×7, 4 of 8×8, 4 of 10×10, and 2 of 15×10. This paper proposes a new MCTS-based algorithm for MO-FJSP problem by modifying their algorithm. Our experimental results show that our new algorithm significantly outperforms their algorithm for large problems, especially for Kacem 15×10. This shows that the new algorithm tends to have better potential of solving harder MO-FJSP problems.

AB - Multi-objective flexible job-shop scheduling problem (MO-FJSP) is very important in both fields of production management and combinatorial optimization. Wu et al. proposed a Monte-Carlo Tree Search (MCTS) to solve MO-FJSP and successfully improved the performance of MCTS to find 17 Pareto solutions: 4 of Kacem 4×5, 3 of 10×7, 4 of 8×8, 4 of 10×10, and 2 of 15×10. This paper proposes a new MCTS-based algorithm for MO-FJSP problem by modifying their algorithm. Our experimental results show that our new algorithm significantly outperforms their algorithm for large problems, especially for Kacem 15×10. This shows that the new algorithm tends to have better potential of solving harder MO-FJSP problems.

KW - Evolutionary Algorithm

KW - Monte-Carlo Tree Search

KW - Multi-Objective Flexible Job Shop Scheduling Problem

KW - Rapid Action Value Estimates

UR - http://www.scopus.com/inward/record.url?scp=84964237889&partnerID=8YFLogxK

U2 - 10.1109/TAAI.2015.7407061

DO - 10.1109/TAAI.2015.7407061

M3 - Conference contribution

AN - SCOPUS:84964237889

T3 - TAAI 2015 - 2015 Conference on Technologies and Applications of Artificial Intelligence

SP - 136

EP - 141

BT - TAAI 2015 - 2015 Conference on Technologies and Applications of Artificial Intelligence

PB - Institute of Electrical and Electronics Engineers Inc.

Y2 - 20 November 2015 through 22 November 2015

ER -

Chou JJ, Liang CC, Wu HC, Wu I-C, Wu TY. A new MCTS-based algorithm for multi-objective flexible job shop scheduling problem. In TAAI 2015 - 2015 Conference on Technologies and Applications of Artificial Intelligence. Institute of Electrical and Electronics Engineers Inc. 2016. p. 136-141. 7407061. (TAAI 2015 - 2015 Conference on Technologies and Applications of Artificial Intelligence). https://doi.org/10.1109/TAAI.2015.7407061