梯子型走行経路を用いたAGVシステムにおけるデッドロック回復問題の計算複雑さ
小泉 賢司, 増山 繁
pp. 91-104
DOI:
10.5687/iscie.23.91抄録
This paper proposes the minimum time deadlock recovery problem in the AGV system with the ladder guidepath layout(DRPL, for short) and analyzes its computational complexity. In order to analyze the computational complexity, this paper introduces the decision problem version of DRPL to ask whether all deadlocks in the AGV system are recoverable within predetermined time, and NP-hardness in a special case of the problem is proved. Moreover, the condition by which the problem becomes NP-hard when the AGV system has a ladder guidepath layout is clarified, and we propose a polynomial time algorithm that solves the optimization problem version of this problem whenever the problem in the ladder guidepath layout is not NP-hard.