|
ИСТИНА |
Войти в систему Регистрация |
ИСТИНА ИНХС РАН |
||
Constructing an instance of the cutting stock problem of minimum size which does not possess the integer round-up propertyстатья
Статья опубликована в журнале из списка RSCI Web of Science
Статья опубликована в журнале из перечня ВАК- Авторы: Ripatti A.V., Kartak V.M.
- Журнал: Дискретный анализ и исследование операций
- Том: 27
- Номер: 1
- Год издания: 2020
- Издательство: Изд-во Ин-та математики
- Местоположение издательства: Новосибирск
- Первая страница: 127
- Последняя страница: 140
- DOI: 10.33048/daio.2020.27.665
- Аннотация: Рассматривается известная одномерная задача раскроя с целью найти целочисленные примеры с минимальным размером материала L, для которых не выполняется свойство округления вверх. Разрывом целочисленности называется разница между точным решением примера задачи раскроя и решением её линейной релаксации, и пример задачи раскроя обладает свойством округления вверх, если его разрыв целочисленности меньше 1. Предлагается новый метод поиска всех примеров с максимальным разрывом целочисленности для фиксированных значений L, длин заготовок и оптимального целочисленного решения. Данный метод позволяет вычислительно доказать, что все примеры с L ≤ 15 обладают свойством округления вверх. Также приведены несколько примеров c L = 16, не обладающих таким свойством, что даёт улучшение ранее известного результата L = 18. Табл. 2, библиогр. 14.
- Добавил в систему: Картак Вадим Михайлович