Consensus-based Approach to Distributed Scheduling Problem

Miyamoto Toshiyuki, Umeda Toyohiro, Takai Shigemasa

doi:10.5687/iscie.34.58

Bibliographic Information

Other Title

分散スケジューリング問題に対する合意に基づく解法
ブンサンスケジューリングモンダイニタイスルゴウイニモトズクカイホウ

Search this article

Abstract

<p>In recent years, the development of optimization methods in multi-agent systems has been remarkable. The scheduling problems belong to NP-hard and are not easily solved in a large-scale system. The distributed scheduling method is expected as one of the methods for large-scale systems. In this paper, as the first step of the research, we propose to apply the alternating direction method of multipliers for the consensus problem to the distributed scheduling problem and show that the job shop scheduling problem (JSP) can be formulated by the proposed method. In distributed optimization, the optimization of sub-problems is repeated until the convergence condition is satisfied, but since the scheduling problem is a nonconvex optimization problem, the convergence by the proposed method is not guaranteed. In some cases, a large number of iterations may be required to satisfy the convergence condition. In this paper, we propose two schemes to obtain a feasible solution within a smaller number of iterations. Then, the method is evaluated by computer experiments using benchmark instances of JSP.</p>

Journal

Transactions of the Institute of Systems, Control and Information Engineers

Transactions of the Institute of Systems, Control and Information Engineers 34 (2), 58-67, 2021-02-15

THE INSTITUTE OF SYSTEMS, CONTROL AND INFORMATION ENGINEERS (ISCIE)

Keywords

Details 詳細情報について

Export