본문 바로가기
  • Home

Maximum Profit Priority Goods First Loading Algorithm for Barge Loading Problem

  • Journal of The Korea Society of Computer and Information
  • Abbr : JKSCI
  • 2014, 19(10), pp.169-173
  • Publisher : The Korean Society Of Computer And Information
  • Research Area : Engineering > Computer Science

Sang-Un, Lee 1

1강릉원주대학교

Accredited

ABSTRACT

Nobody has yet been able to determine the optimal solution conclusively whether NP-completeproblems are in fact solvable in polynomial time. Guéret et al. tries to obtain the optimal solution usinglinear programming with O(m⁴) time complexity for barge loading problem a kind of bin packing problemthat is classified as nondeterministic polynomial time (NP)-complete problem. On the other hand, this papersuggests the loading rule of profit priority rank algorithm with O(mlogm) time complexity. This paperdecides the profit priority rank firstly. Then, we obtain the initial loading result using the rule of loadingthe good has profit priority order. Finally, we balance the loading and capability of barge swap the goodsof unloading in previously loading in case of under loading. As a result of experiments, this algorithmreduces the O(m⁴) of linear programming to O(mlogm) time complexity for NP-complete barge loading problem.

Citation status

* References for papers published after 2022 are currently being built.