TY - GEN
T1 - Lagrangian relaxation technique for solving scheduling 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 Lagrangian relaxation technique for solving scheduling problems by decomposition of timed Petri nets. The scheduling problem is represented by the transition firing sequence problem to minimize a given objective function. The timed Petri net is decomposed into several subnets so that the subproblem for each subnet can be easily solved by a shortest path algorithm. The optimality of solution can be evaluated by the duality gap derived by Lagrangian relaxation method. The performance of the proposed method is compared with the conventional optimization algorithm with penalty function method. The results show that the duality gap within 1.5% can be derived for AGVs routing problems. The effectiveness of the proposed method is demonstrated by comparing the performance between the conventional method.
AB - In this paper, we propose Lagrangian relaxation technique for solving scheduling problems by decomposition of timed Petri nets. The scheduling problem is represented by the transition firing sequence problem to minimize a given objective function. The timed Petri net is decomposed into several subnets so that the subproblem for each subnet can be easily solved by a shortest path algorithm. The optimality of solution can be evaluated by the duality gap derived by Lagrangian relaxation method. The performance of the proposed method is compared with the conventional optimization algorithm with penalty function method. The results show that the duality gap within 1.5% can be derived for AGVs routing problems. The effectiveness of the proposed method is demonstrated by comparing the performance between the conventional method.
KW - Dependable manufacturing systems control
KW - Discrete event systems in manufacturing
KW - Job and activity scheduling
UR - http://www.scopus.com/inward/record.url?scp=79961017780&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=79961017780&partnerID=8YFLogxK
U2 - 10.3182/20080706-5-KR-1001.2316
DO - 10.3182/20080706-5-KR-1001.2316
M3 - Conference contribution
AN - SCOPUS:79961017780
SN - 9783902661005
T3 - IFAC Proceedings Volumes (IFAC-PapersOnline)
BT - Proceedings of the 17th World Congress, International Federation of Automatic Control, IFAC
T2 - 17th World Congress, International Federation of Automatic Control, IFAC
Y2 - 6 July 2008 through 11 July 2008
ER -