본문 바로가기
  • Home

Maximum Sugar Loss Lot First Production Algorithm for Cane Sugar Production Problem

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

Sang-Un, Lee 1

1강릉원주대학교

Accredited

ABSTRACT

Guéret et al. tries to obtain the solution using linear programming with O(m⁴)time complexity for canesugar production problem a kind of bin packing problem that is classified as NP-complete problem. On theother hand, this paper suggests the maximum loss of lot first production greedy rule algorithm with O(mlog m) polynomial time complexity underlying assumption of the polynomial time rule to find thesolution is exist. The proposed algorithm sorts the lots of sugar loss slope into descending order. Then,we select the lots for each slot production capacity only, and swap the exhausted life span of lots forlastly selected lots. As a result of experiments, this algorithm reduces the O(m⁴) of linear programmingto O(mlog m) time complexity. Also, this algorithm better result than linear programming.

Citation status

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