Heuristic algorithms with rounded weights for a combinatorial food packing problem
In this paper, a lexicographic bi-criteria food packing problem arising in actual packaging equipments is considered. Given a set I = {i | i = 1,2,...,n} of current n items (for example, n green peppers) with their weights wi and priorities pi, the problem asks to find a subset I′ (⊆ I) so that the...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
The Japan Society of Mechanical Engineers
2017-01-01
|
| Series: | Journal of Advanced Mechanical Design, Systems, and Manufacturing |
| Subjects: | |
| Online Access: | https://www.jstage.jst.go.jp/article/jamdsm/11/1/11_2017jamdsm0003/_pdf/-char/en |
| _version_ | 1818531830810279936 |
|---|---|
| author | Yoshiyuki KARUNO Ryo SAITO |
| author_facet | Yoshiyuki KARUNO Ryo SAITO |
| author_sort | Yoshiyuki KARUNO |
| collection | DOAJ |
| description | In this paper, a lexicographic bi-criteria food packing problem arising in actual packaging equipments is considered. Given a set I = {i | i = 1,2,...,n} of current n items (for example, n green peppers) with their weights wi and priorities pi, the problem asks to find a subset I′ (⊆ I) so that the total weight ∑i∈I′ wi is no less than a given positive t which denotes a target weight for each package, and it is minimized as the primary objective, and further the total priority ∑i∈I′ pi is maximized as the second objective. The problem has been known to be NP-hard, while it can be solved exactly in O(nt) time if all the input data are integral. In this paper, for a given real ε > 0, an O(n2/ε) time heuristic algorithm with rounded weights is proposed such that the heuristic total weight is at most (1 + ε) times the optimal total weight. Numerical experiments are also conducted to compare the proposed and known heuristic algorithms with rounded weights, and the results are reported. |
| first_indexed | 2024-12-11T17:37:35Z |
| format | Article |
| id | doaj.art-65f8e30973b34635b907a565ca205d68 |
| institution | Directory Open Access Journal |
| issn | 1881-3054 |
| language | English |
| last_indexed | 2024-12-11T17:37:35Z |
| publishDate | 2017-01-01 |
| publisher | The Japan Society of Mechanical Engineers |
| record_format | Article |
| series | Journal of Advanced Mechanical Design, Systems, and Manufacturing |
| spelling | doaj.art-65f8e30973b34635b907a565ca205d682022-12-22T00:56:37ZengThe Japan Society of Mechanical EngineersJournal of Advanced Mechanical Design, Systems, and Manufacturing1881-30542017-01-01111JAMDSM0003JAMDSM000310.1299/jamdsm.2017jamdsm0003jamdsmHeuristic algorithms with rounded weights for a combinatorial food packing problemYoshiyuki KARUNO0Ryo SAITO1Faculty of Mechanical Engineering, Kyoto Institute of TechnologyUndergraduate School of Science and Technology, Kyoto Institute of TechnologyIn this paper, a lexicographic bi-criteria food packing problem arising in actual packaging equipments is considered. Given a set I = {i | i = 1,2,...,n} of current n items (for example, n green peppers) with their weights wi and priorities pi, the problem asks to find a subset I′ (⊆ I) so that the total weight ∑i∈I′ wi is no less than a given positive t which denotes a target weight for each package, and it is minimized as the primary objective, and further the total priority ∑i∈I′ pi is maximized as the second objective. The problem has been known to be NP-hard, while it can be solved exactly in O(nt) time if all the input data are integral. In this paper, for a given real ε > 0, an O(n2/ε) time heuristic algorithm with rounded weights is proposed such that the heuristic total weight is at most (1 + ε) times the optimal total weight. Numerical experiments are also conducted to compare the proposed and known heuristic algorithms with rounded weights, and the results are reported.https://www.jstage.jst.go.jp/article/jamdsm/11/1/11_2017jamdsm0003/_pdf/-char/enengineering optimizationfood packaging operationdynamic programmingheuristic algorithmsrounding |
| spellingShingle | Yoshiyuki KARUNO Ryo SAITO Heuristic algorithms with rounded weights for a combinatorial food packing problem Journal of Advanced Mechanical Design, Systems, and Manufacturing engineering optimization food packaging operation dynamic programming heuristic algorithms rounding |
| title | Heuristic algorithms with rounded weights for a combinatorial food packing problem |
| title_full | Heuristic algorithms with rounded weights for a combinatorial food packing problem |
| title_fullStr | Heuristic algorithms with rounded weights for a combinatorial food packing problem |
| title_full_unstemmed | Heuristic algorithms with rounded weights for a combinatorial food packing problem |
| title_short | Heuristic algorithms with rounded weights for a combinatorial food packing problem |
| title_sort | heuristic algorithms with rounded weights for a combinatorial food packing problem |
| topic | engineering optimization food packaging operation dynamic programming heuristic algorithms rounding |
| url | https://www.jstage.jst.go.jp/article/jamdsm/11/1/11_2017jamdsm0003/_pdf/-char/en |
| work_keys_str_mv | AT yoshiyukikaruno heuristicalgorithmswithroundedweightsforacombinatorialfoodpackingproblem AT ryosaito heuristicalgorithmswithroundedweightsforacombinatorialfoodpackingproblem |