ISSN 2071-8594

Российская академия наук

Главный редактор

Г.С. Осипов

Е.М. Фуремс "Приближенное решение обратной задачи об упаковке в контейнеры с учетом предпочтений лица, принимающего решения"

Аннотация.

Рассматривается задача упаковки максимального числа объектов, оцененных по многим качественным критериям и упорядоченных в соответствии с предпочтениями лица, принимающего решения (ЛПР), в заданное число контейнеров одинаковой грузоподъемности. При этом суммарный вес объектов в каждом контейнере не должен превышать его грузоподъемность, и для каждого неупакованного объекта не должно быть упакованных объектов, менее предпочтительных для ЛПР, вместо которых такой объект можно упаковать без нарушения ограничения на грузоподъемность. Предлагается схема приближенного решения этой задачи на основе модифицированного алгоритма «в первый подходящий с убыванием».

Ключевые слова:

обратная задача об упаковке в контейнеры, предпочтения, приближенная схема решения.

Стр. 112-121.

DOI 10.14357/20718594180321

Литература

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. Фуремс Е.М.. Модели упаковки в многокритериальных задачах принятия решений при ограниченных ресурсах. Препринт ВНИИСИ. 1986. С. 45.
5. Фуремс Е.М. Обратная задача об упаковке в контейнеры при наличии качественных критериев // Искусственный интеллект и принятие решений. 2016. № 3, C. 31-43.
6. Furems E.M. 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. Левин Марк Ш. Упаковка в контейнеры (перспективные модели и примеры). Информационные процессы, 2017. Том 17, № 1, с. 43–60
13. Levin M.Sh. 2018. Bin packing (promising models and examples). J. of Communications Technology and Electronics, 63(6), 655-666.
14. Ашихмин И.В., Фуремс Е.М. Двухэтапная процедура упорядочения объектов по многим критериям // Искусственный интеллект и принятие решений. 2017. № 3, с. 58-68.
15. von Winterfeldt D. 1980. Structuring Decision Problems for Decision Analysis // ActaPsychologica, vol. 45, 71-93.
16. Фуремс Е.М. Структуризация задач классификации, основанных на знаниях //Информационные технологии и вычислительные системы. 2007. № 3, с.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. Фуремс Е.М. Многокритериальная порядковая классификация на основе метода STEPCLASS //Искусственный интеллект и принятие решений. 2012. № 4, с. 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. Ашихмин И. В. Продукционные правила и предпочтения/ Третья Международная конференция «Системный анализ и информационные технологии» САИТ – 2009: Труды конференции. М., 2009. с. 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.