Home > Explore Content > All Issues > Article View
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 : Computer Science
2014, 19(10), pp.169-173
Publisher : The Korean Society Of Computer And Information
Research Area : Computer Science
-
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(ｍ⁴) 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(ｍlogｍ) 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(ｍ⁴) of linear programming to O(ｍlogｍ) time complexity for NP-complete barge loading problem.
171 Viewed
Print this page
Download PDF