Lagrangian relaxation approach for solving optimal firing sequence problems by decomposition of timed Petri Nets

Tatsushi Nishi; Kenichi Shimatani; Masahiro Inuiguchi

doi:10.1109/SICE.2008.4654914

Lagrangian relaxation approach for solving optimal firing sequence problems by decomposition of timed Petri Nets

Tatsushi Nishi, Kenichi Shimatani, Masahiro Inuiguchi

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

1 Citation (Scopus)

Abstract

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.

Original language	English
Title of host publication	Proceedings of SICE Annual Conference 2008 - International Conference on Instrumentation, Control and Information Technology
Pages	1585-1590
Number of pages	6
DOIs	https://doi.org/10.1109/SICE.2008.4654914
Publication status	Published - 2008
Externally published	Yes
Event	SICE Annual Conference 2008 - International Conference on Instrumentation, Control and Information Technology - Tokyo, Japan Duration: Aug 20 2008 → Aug 22 2008

Publication series

Name	Proceedings of the SICE Annual Conference

Other

Other	SICE Annual Conference 2008 - International Conference on Instrumentation, Control and Information Technology
Country/Territory	Japan
City	Tokyo
Period	8/20/08 → 8/22/08

Keywords

Computational complexity
Decomposition
Petri Nets
Transition firing sequence problem

ASJC Scopus subject areas

Control and Systems Engineering
Computer Science Applications
Electrical and Electronic Engineering

Access to Document

10.1109/SICE.2008.4654914

Cite this

Nishi, T., Shimatani, K., & Inuiguchi, M. (2008). Lagrangian relaxation approach for solving optimal firing sequence problems by decomposition of timed Petri Nets. In Proceedings of SICE Annual Conference 2008 - International Conference on Instrumentation, Control and Information Technology (pp. 1585-1590). [4654914] (Proceedings of the SICE Annual Conference). https://doi.org/10.1109/SICE.2008.4654914

Lagrangian relaxation approach for solving optimal firing sequence problems by decomposition of timed Petri Nets. / Nishi, Tatsushi; Shimatani, Kenichi; Inuiguchi, Masahiro.
Proceedings of SICE Annual Conference 2008 - International Conference on Instrumentation, Control and Information Technology. 2008. p. 1585-1590 4654914 (Proceedings of the SICE Annual Conference).

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

Nishi, T, Shimatani, K & Inuiguchi, M 2008, Lagrangian relaxation approach for solving optimal firing sequence problems by decomposition of timed Petri Nets. in Proceedings of SICE Annual Conference 2008 - International Conference on Instrumentation, Control and Information Technology., 4654914, Proceedings of the SICE Annual Conference, pp. 1585-1590, SICE Annual Conference 2008 - International Conference on Instrumentation, Control and Information Technology, Tokyo, Japan, 8/20/08. https://doi.org/10.1109/SICE.2008.4654914

Nishi T, Shimatani K, Inuiguchi M. Lagrangian relaxation approach for solving optimal firing sequence problems by decomposition of timed Petri Nets. In Proceedings of SICE Annual Conference 2008 - International Conference on Instrumentation, Control and Information Technology. 2008. p. 1585-1590. 4654914. (Proceedings of the SICE Annual Conference). doi: 10.1109/SICE.2008.4654914

@inproceedings{7d403007fdc54c6a9d427b130e2cd1c0,

title = "Lagrangian relaxation approach for solving optimal firing sequence problems by decomposition of timed Petri Nets",

abstract = "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.",

keywords = "Computational complexity, Decomposition, Petri Nets, Transition firing sequence problem",

author = "Tatsushi Nishi and Kenichi Shimatani and Masahiro Inuiguchi",

year = "2008",

doi = "10.1109/SICE.2008.4654914",

language = "English",

isbn = "9784907764296",

series = "Proceedings of the SICE Annual Conference",

pages = "1585--1590",

booktitle = "Proceedings of SICE Annual Conference 2008 - International Conference on Instrumentation, Control and Information Technology",

note = "SICE Annual Conference 2008 - International Conference on Instrumentation, Control and Information Technology ; Conference date: 20-08-2008 Through 22-08-2008",

}

TY - GEN

T1 - Lagrangian relaxation approach for solving optimal firing sequence problems by decomposition of timed Petri Nets

AU - Nishi, Tatsushi

AU - Shimatani, Kenichi

AU - Inuiguchi, Masahiro

PY - 2008

Y1 - 2008

N2 - 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.

AB - 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.

KW - Computational complexity

KW - Decomposition

KW - Petri Nets

KW - Transition firing sequence problem

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

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

U2 - 10.1109/SICE.2008.4654914

DO - 10.1109/SICE.2008.4654914

M3 - Conference contribution

AN - SCOPUS:56749184244

SN - 9784907764296

T3 - Proceedings of the SICE Annual Conference

SP - 1585

EP - 1590

BT - Proceedings of SICE Annual Conference 2008 - International Conference on Instrumentation, Control and Information Technology

T2 - SICE Annual Conference 2008 - International Conference on Instrumentation, Control and Information Technology

Y2 - 20 August 2008 through 22 August 2008

ER -

Lagrangian relaxation approach for solving optimal firing sequence problems by decomposition of timed Petri Nets

Abstract

Publication series

Other

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this