Home
>
Explore Content
>
All Issues
>
Article View
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 : Computer Science
2014, 19(12), pp.171-175
Publisher : The Korean Society Of Computer And Information
Research Area : Computer Science
-
Guéret et al. tries to obtain the solution using linear programming with O(ｍ⁴)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(ｍlog ｍ) 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(ｍ⁴) of linear programmingto O(ｍlog ｍ) time complexity. Also, this algorithm better result than linear programming.
145
Viewed
Print this page
Download PDF