基于增广森林结构的一般网络最小费用问题瓶颈分析

CIESC Journal

• RESEARCH PAPERS • 上一篇下一篇

基于增广森林结构的一般网络最小费用问题瓶颈分析

江永亨; 王军; 金以慧

Department of Automation, Tsinghua University, Beijing 100084, China

收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2003-02-28 发布日期:2003-02-28
通讯作者: 江永亨

Bottleneck Analysis of the Minimum Cost Problem for the Generalized Network Based on
Augmented Forest Structure

JIANG Yongheng; WANG Jun; JIN Yihui

Department of Automation, Tsinghua University, Beijing 100084, China

Received:1900-01-01 Revised:1900-01-01 Online:2003-02-28 Published:2003-02-28
Contact: JIANG Yongheng

摘要/Abstract

摘要： The bottleneck analysis of the minimum cost problem for the generalized network (MCPGN) is
dis-cussed. The analysis is based on the network simplex algorithm, which gains negative
cost graphs by constructingaugmented forest structure, then augments flows on the negative
cost graphs until the optimal revolution is gained.Bottleneck structure is presented after
analyzing the augmented forest structure. The negative cost augmentedgraphs are constructed
with the bottleneck structure. The arcs that block the negative cost augmented graph arethe
elements of the bottleneck. The bottleneck analysis for the generalized circulation
problem, the minimum circu-lation problem and the circulation problem are discussed
respectively as the basal problems, then that for MCPGNis achieved. An example is presented
at the end.

关键词: bottleneck;augmented forest;minimum cost problem

Abstract: The bottleneck analysis of the minimum cost problem for the generalized network (MCPGN) is
dis-cussed. The analysis is based on the network simplex algorithm, which gains negative
cost graphs by constructingaugmented forest structure, then augments flows on the negative
cost graphs until the optimal revolution is gained.Bottleneck structure is presented after
analyzing the augmented forest structure. The negative cost augmentedgraphs are constructed
with the bottleneck structure. The arcs that block the negative cost augmented graph arethe
elements of the bottleneck. The bottleneck analysis for the generalized circulation
problem, the minimum circu-lation problem and the circulation problem are discussed
respectively as the basal problems, then that for MCPGNis achieved. An example is presented
at the end.

Key words: bottleneck, augmented forest, minimum cost problem

江永亨, 王军, 金以慧. 基于增广森林结构的一般网络最小费用问题瓶颈分析[J]. CIESC Journal.

JIANG Yongheng, WANG Jun, JIN Yihui. Bottleneck Analysis of the Minimum Cost Problem for the Generalized Network Based on
Augmented Forest Structure[J]. .

参考文献

[1] Esogbue, B.R., Nabeshima, A.O., "Mathematical aspectsof scheduling and applications",
Pergamon Press, Oxford,UK (1988).
[2] Reklaitis, G.V., "Review of scheduling of process opera tions’’, AIChE Symp. Seris.,
78, 119-132 (1982).
[3] Wang, J. "Process bottleneck analysis and production scheduling of process industry",
Ph. D. Thesis, Tsinghua University, Beijing (1998). (in Chinese)
[4] Aneja, Y.P., Punnen, A.P., "Multiple bottleneck assignment problem", Eur. J. Oper.
Res., 112, 167-173 (1999).
[5] Sokkalingam, P.T., Aneja, Y.P., "Lexicographic bottleneck combinatorial problems",
Oper. Res. Lett., 23, 27-33 (1998).
[6] Pezzella, F., Merelli, E., "A tabu search method guided byshifting bottleneck for the
job shop scheduling problem",Eur. J. Oper. Res., 120, 297-310 (2000).
[7] Croce, F.D., Paschos, V.T., Tsoukias, A., "An improved general procedure for
lexicographic bottleneck problems", Oper. Res. Lett., 24, 187-194 (1999).
[8] Sokkalingam, P.T., Aneja, Y.P., "Lexicographic bottleneck combinatorial problems",
Oper. Res. Lett., 23, 27-33 (1998).
[9] Katagiri, H., Ishii, H., "Chance constrained bottleneck spanning tree problem with
fuzzy random edge costs", J. Oper. Res. Soc. Japan, 43 (1), 128-137 (2000).
[10] Arnott, R., Palma, A,, Lindsey, R., "Information and time of-usage decisions in the
bottleneck model with stochastic capacity and demand", Eur. Econom. Rev., 43, 525-548
(1999).
[11] Jiang, Y.H., Jin, Y.H., "The process bottleneck analysis based on optimal spanning
tree structure", J. Automation, (Supp. B), 71-75 (2000). (in Chinese)
[12] Jiang, Y.H., Jin, Y.H., "Process bottleneck analysis of the generalized circulation
problem", Theo. Practice System Eng., 22, 46-50 (2002). (in Chinese)
[13] Jiang, Y.H., Jin, Y.H., "Process bottleneck analysis of circulation problem", Computer
Integrated Manufacturing System, 8 (4), 279-283 (2002). (in Chinese)
[14] Wang, J., Jin, Y.H., "Production scheduling problem in continuous process",
Proceedings of the Second Chinese World Congress on Intelligent Control and Intelligent
Automation, Xi’an, 1099-1104 (1997).
[15] Ahuja, R.K., Magnanti, T.L., Orlin, J.B., "Network flows: theory, algorithms, and
applications", Englewood Cliffs, N.J., Prentice Hall (1993).

基于增广森林结构的一般网络最小费用问题瓶颈分析

Bottleneck Analysis of the Minimum Cost Problem for the Generalized Network Based on
Augmented Forest Structure

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 0

编辑推荐

Metrics

本文评价

基于增广森林结构的一般网络最小费用问题瓶颈分析

Bottleneck Analysis of the Minimum Cost Problem for the Generalized Network Based on Augmented Forest Structure

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 0

编辑推荐

Metrics

本文评价

Bottleneck Analysis of the Minimum Cost Problem for the Generalized Network Based on
Augmented Forest Structure