ISSN 2071-8594

Russian academy of sciences

Editor-in-Chief

Gennady Osipov

E. M. Furems Approximate Solution Scheme for Inverse Bin-Packing Problem Subject to Decision Making Preferences

Abstract.

The problem of packing maximal number of items in the given set of equal capacity bins while taking into account DM’s preferences is under consideration. The solution of this problem must satisfy to the following conditions: (1) the total weight of items in each been is not greater than its capacity, and (2) for each unpacked item there is none packed items less preferable for DM instead of which it may be packed without violation the capacity constraint. The approximate solution scheme for this problem based on modified First Fit Decreasing algorithm is proposed.

Keywords.

Inverse bin-packing problem, preferences, approximate solution scheme.

PP. 112-121.

DOI 10.14357/20718594180321

References

1. Coffman E.G., Jr., Leung J.Y.-T., Ting D. 1978. Bin Packing: Maximizing the Number of Pieces Packed //Acta Infomat., vol. 9, 263-271.
2. Coffman, Jr, E. G., & Leung, J. Y. 1979. Combinatorial analysis of an efficient algorithm for processor and storage allocation. SIAM Journal on Computing, 8(2), 202-217.
3. Wäscher, G., Hausner, H., Schumann, H. 2007. An improved typology of cutting and packing problems. EJOR. 183 (3), 1109–1130.
4. Furems E.M. 1986. Modeli upakovki v mnogocriterial’nyh zadachah prinyatia reshenii pri ogranichennyh resursah [Bin Packing Models in Multicriteria Decision Making Problems with Limited Resources]. Preprint VNIISI, M., P. 45.
5. Furems, E.M., Obratnaya zadacha upakovli pri nalichii kachestvennyh kriteriev [Inverse bin packing problem with multiple qualitative criteria]. Iskusstvennyi Intellekt i Prinyatie Reshenii [Artificial Intelligence and Decision Making], 2016, No.3, pp. 31-43.
6. E.M. Furems. 2017. The Inverse Bin Packing Problem Subject to Qualitative Criteria// Scientific and Technical Information Processing, Vol. 44, No. 6, pp. 440–450.
7. Graham, R. L., Lawler, E. L., Lenstra, J. K., & Kan, A. R. 1979. Optimization and approximation in deterministic sequencing and scheduling: a survey. Annals of discrete mathematics, 5, 287-326.
8. Garey, M. R., Graham, R. L., & Johnson, D. S. 1978. Performance guarantees for scheduling algorithms. Operations research, 26(1), 3-21.
9. Dell'Amico, M., Díaz, J. C. D., & Iori, M. 2012. The bin packing problem with precedence constraints. Operations Research, 60(6), 1491-1504.
10. Karp R.M. 1972. Reducibility among combinatorial problems, in Complexity of Computer Computations (R.E. Miller and J.M. Thatcher, eds.), 85–103, Plenum Press.
11. Garey, M. R., & Johnson, D. S. 2002. Computers and intractability, Vol. 29. New York: wh freeman.
12. Levin M.Sh. 2017. Upakovka v konteinery (perspectivnye modeli i primery) [Bin packing (prospective models and examples)]. Informatzionnye process [Информационные процессы], vol 17, No. 1, pp. 43–60
13. Levin M.Sh. 2018. Bin packing (promising models and examples). J. of Communications Technology and Electronics, 63(6), 655-666.
14. Ilya V. Ashikhmin , E.M. Furems 2017. Dvuhetapnaya procedura uporyadocheniya ob’ektov po mnogim kritriyam [Two-Stage Procedure for Items’ Ordering upon Multiple Criteria] // Iskusstvennyi Intellekt i Prinyatie Reshenii [Artificial Intelligence and Decision Making], Искусственный интеллект и принятие решений», No. 3, pp. 58-68.
15. von Winterfeldt D. 1980. Structuring Decision Problems for Decision Analysis // ActaPsychologica, vol. 45, 71-93.
16. Furems E.M. Structurizatzia zadach klassifikatzii osnovannyh na znaniah [Structuring of knowledge-based classification problems// Iskusstvennyi Intellekt i Prinyatie Reshenii [Artificial Intelligence and Decision Making], 2007, no. 3, pp. 7-17
17. Furems Eugenia M. 2011. Domain Structuring For Knowledge-Based Multiattribute Classification (A Verbal Decision Analysis Approach) // TOP, Springer Berlin / Heidelberg, 19, pp. 402–420.
18. Furems, E.M., 2012. Mnogocriterial’naya poryadkovaya klassificatzia na osnove metoda STEPCLASS [STEPCLASS-based approach to multicriteria sorting]// Iskusstvennyi Intellekt i Prinyatie Reshenii [Artificial Intelligence and Decision Making], No.4, pp. 95-100.
19. Furems E. M. 2015 Stepclass_Based Approach to Multicriteria Sorting // Scientific and Technical Information Processing, Vol. 42, No. 6, pp. 481–489.
20. Ashikhmin, I.V., Productzionnye pravila I predpochtenya [Production rules and preferences]. Trudy Tretyey
Mezhdunarodnoy konferentzyi ‘Sistemnyi Analiz i Informatzionnye Tehnologii’ (SAIT – 2009) [Proceedingth of the 3rd International Conference ‘System Analysis and Information Technology’ (SAIT 2009)]. M, 2009, pp. 247-251
21. Ashikhmin I., Furems E. 2005. UniComBOS—Intelligent Decision Support System for multi-criteria comparison and choice //Journal of Multi-Criteria Decision Analysis. V. 13. No. 2-3, pp. 147-157.
22. Furems E.M., Larichev O.I., Roizenson G.V., Lotov A.V., Miettinen K. 2003. Human behavior in a multi-criteria choice problem with individual tasks of different difficulties // International Journal of Information Technology & Decision Making, Vol.2, No. 1, pp. 29-40.