Lagrangian Relaxation Approach for Solving Optimal Firing Sequence Problems by Decomposition of Timed Petri Nets

被引：0

作者：

Nishi, Tatsushi ^{[1
]}

Shimatani, Kenichi ^{[1
]}

Inuiguchi, Masahiro ^{[1
]}

机构：

[1] Osaka Univ, Toyonaka, Osaka 5608531, Japan

来源：

2008 PROCEEDINGS OF SICE ANNUAL CONFERENCE, VOLS 1-7 | 2008年

关键词：

Petri Nets; decomposition; transition firing sequence problem; computational complexity;

D O I：

暂无

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

In this paper, we propose a Lagrangian decomposition and coordination method for solving scheduling problems by the decomposition of timed Petri Nets. The timed Petri Net is decomposed into several subnets so that the subproblem for each subnet can be easily solved. The state space analysis is utilized to determine the decomposition strategy for timed Petri Nets. The Lagrangian decomposition and coordination technique is developed to evaluate the optimality of solution. The proposed method is applied to AGV routing problems and flowshop scheduling problems. The effectiveness of the proposed method is demonstrated by comparing the performance with the conventional method.

引用

页码：1526 / 1531

页数：6