Worker’s knowledge evaluation with single-player Monte Carlo tree search for a practical reentrant scheduling problem

This paper shows the application results of single-player Monte Carlo tree search (SP-MCTS), an alternative of MCTS, for a practical reentrant scheduling problem addressed by our previous works. Especially in this paper, worker’s IF-THEN knowledge evaluation method with SP-MCTS is proposed. SP-MCTS is thought to be a meta-heuristic algorithm for NP-completeness problems, because SP-MCTS is applicable for any types of problems, where the problem’s state changes determinately in each discrete time. Therefore, SP-MCTS might be useful for not only perfect-information one-player games, but also other problems, as long as search spaces are describable as a tree structure, and the solution is stoppable with the termination determinably. The authors have considered that SP-MCTS is useful for obtaining/evaluating knowledge. This paper first describes the basic idea of SP-MCTS, and second shows the detail of the scheduling problem, including formulation. After, this paper examines the availability of SP-MCTS for a practical problem. Especially, the potentiality of SP-MCTS for knowledge evaluation is discussed from the experimental results.