icp

Heuristic for solving the ingot cutting problem

Основа

@article{zhang2016priority,
  title={A priority heuristic for the guillotine rectangular packing problem},
  author={Zhang, Defu and Shi, Leyuan and Leung, Stephen CH and Wu, Tao},
  journal={Information Processing Letters},
  volume={116},
  number={1},
  pages={15--21},
  year={2016},
  publisher={Elsevier}
}

Coming soon

Эвристика максимального прироста полезной площади

Maximum increment heuristic или MI heuristic

Эвристика выполняется пошагово. На каждом шаге осуществляется попытка создать лучшее приращение к уже существующему размещению. Приращение образуется объемлющим прямоугольником текущего размещения и очередным неразмещенным прямоугольником. Всего может быть 4 варианта приращения для одного неразмещенного элемента. Один образуются сочетаниями горизонтального и вертикального положения самого элемента и двумя возможными позициями: верхним левым и нижним правым углами объемлющего прямоугольника. Пустое пространство заполняется неразмещенными элементами с помощью приоритетной эвристики PH. В результате выбирается лучшее приращение. Выполнение алгоритма продолжается пока есть неразмещенные прямоугольники.

У алгоритма есть настраиваемый параметр: аргумент сортировки. Всего возможно 4 варианта сортировки прямоугольников:

• по длине
• по ширине
• по диагонали
• по площади

Наборы данных

Для тестирования алгоритма использовались тестовые наборы данных:

• zdf
• instance

Coming soon

Результаты

• Эвристика максимального приращения (MI)

Coming soon

Использование

Coming soon