A modified network simplex algorithm for solving the minimum distribution cost problem

Shiou Jie Lin, I-Lin Wang

Research output: Contribution to conferencePaper

Abstract

To model the distillation or decomposition of products in some manufacturing processes, a minimum distribution cost problem (MDCP) on a specialized manufacturing network flow model has been investigated. In a MDCP, a specialized node called D-node is used to model a distillation process which only connects with a single incoming arc and several outgoing arcs. The flows entering a D-node have to be distributed according to a pre-specified ratio associated with each of its outgoing arc. Such a proportional relationship between the arc flows associated with each D-node complicates the problem and makes the MDCP harder than conventional min-cost network flow problem. A network simplex algorithm for uncapacitated MDCP has been outlined in literature, but its detailed graphical procedures such as initial basic feasible solution computation, dual variables updates, and flow pivoting operations have not yet been given. In this paper, we resolve these issues and propose a modified network simplex algorithm including detailed graphical operations in each elementary procedure. Our method can not only deal with capacitated MDCP, but also offer more theoretical insights in the basis and properties of MDCP.

Original languageEnglish
Pages92-103
Number of pages12
Publication statusPublished - 2006 Dec 1
Event36th International Conference on Computers and Industrial Engineering, ICC and IE 2006 - Taipei, Taiwan
Duration: 2006 Jun 202006 Jun 23

Other

Other36th International Conference on Computers and Industrial Engineering, ICC and IE 2006
CountryTaiwan
CityTaipei
Period06-06-2006-06-23

    Fingerprint

All Science Journal Classification (ASJC) codes

  • Industrial and Manufacturing Engineering

Cite this

Lin, S. J., & Wang, I-L. (2006). A modified network simplex algorithm for solving the minimum distribution cost problem. 92-103. Paper presented at 36th International Conference on Computers and Industrial Engineering, ICC and IE 2006, Taipei, Taiwan.