VESTNIK
Bashkirskogo universiteta

RUSSIAN
ISSN 1998-4812

Archive | Volume 18, 2013, No. 1.

PARALLEL APPROACH FOR SOLVING ONE-DIMENSIONAL CONTINUOUS BIN PACKING PROBLEM (1BCPP) USING CUDA TECHNOLOGY

Vestnik Bashkirskogo Universiteta. 2013. Vol. 18. No. 1. Pp. 11-14.
Kartak V. M.
Ufa State Aviation Technical University
12 K. Marx Street, 450000 Ufa, Republic of Bashkorotostan, Russia.
Email: kvmail@mail.ru
Ripatti A. V.
Ufa State Aviation Technical University
12 K. Marx Street, 450000 Ufa, Republic of Bashkorotostan, Russia.
Email: ripatti@inbox.ru

Abstract

The one-dimensional continuous bin packing problem (1BCPP) is considered in the article. A parallel algorithm that solves the problem using the branch-and-bound method is proposed. In the main thread on every step the algorithm builds up a partial solution moving down to searching a tree of all solutions. Some cuts are used here to reduce the search space. On some fixed deep of recursion the algorithm stores the current patrial solution and backtracks. All stored partial solutions are processed in a parallel inside multiple additional threads. The algorithm is suitable to launch on the graphic video cards that support a CUDA technology. The computational study shows the efficiency of the bounds and good performance of the parallel algorithm. Numerical results are presented.

Keywords

  • • GPGPU
  • • CUDA

References

  1. Martello S., Monachi M., Vigo D. An exact approach to the strip-packing problem // INFORMS Journal on Computing. 2003. №15(3). P. 310–319.
  2. Месягутов М. А. Задача двумерной ортогональной упаковки: поиск нижней границы на базе решения одномерной продолженной упаковки // Информационные технологии. 2010. №6. С. 13–23.
  3. Картак В. М., Месягутов М. А., Мухачева Э. А., Филиппова А. С. Локальный поиск ортогональных упаковок с использованием нижних границ // Автоматика и телемеханика. 2009. №6. С. 167–180.
  4. Месягутов М. А. Методы принятия оптимальных решений на основе анализа эффективности значений функции цели в задачах прямоугольной упаковки: Автореф. дис. канд. физ.-мат. наук. Уфа, 2010. 19 с.
  5. Hartmarm S. Project Scheduling under limited resources. Models, methods and applications. Berlin: Springer, 1999.
  6. Мухачева Э. А., Мухачева А. С. Задача прямоугольной упаковки: методы локального поиска оптимума на базе блочных структур // Автоматика и телемеханика. 2004. №2. С. 10–15.