Modeliranje in reševanje problema pakiranja vijakov za toplotno obdelavo

KIROVSKA, ILINA (author), Čibej, Uroš (mentor)

Problemi pakiranja se pogosto uporabljajo v računalništvu, zaradi tega obstaja veliko načinov, na katerih jih je mogoče rešiti. Diplomska naloga se ukvarja z zelo specifičnim problemom pakiranja. Za toplotno obdelavo želimo optimalno spakirati določeno število mrež vijakov z uporabo natančnega števila škatel. Problem smo formalno zapisali dvonivojsko, kot problem pakiranja košev in problem več nahrbtnikov. Za njegovo reševanje sta uporabljena dva reševalnika OR-Toolsa. Prvi reševalnik je namenjen reševanju problema pakiranja košev, drugi reševanju problema več nahrbtnikov. Rezultate obeh reševalnikov smo glede časa izvajanja in števila optimalnih rešitev primerjali med seboj.

• Language: Slovenian
• Keywords: algoritem, problem pakiranja košev, problem več nahrbtnikov, reševalnik
• Work type: Bachelor thesis/paper
• Typology: 2.11 - Undergraduate Thesis
• Organization: FRI - Faculty of Computer and Information Science
• Year: 2022
• PID: 20.500.12556/RUL-139809
• COBISS.SI-ID: 121845251
• Publication date in RUL: 07.09.2022

Secondary language

• Language: English
• Title: Modelling and solving the problem of screw-packing for heat treatment

Abstract

Packing problems have many applications in computer science. For this reason, there are numerous ways in which they can be solved. This thesis concerns a very specific packing problem. We want to optimally pack several screw grids into a finite number of boxes. Firstly, the problem was written as a multiple knapsack problem and as a bin packing problem. Secondly, we used two OR-Tools solvers to solve it. One is designed for solving multiple knapsack problems and the other is for solving bin packing problems. Lastly, we compared the results in terms of their execution time and the number of optimal solutions.

• Keywords: algorithm, bin packing problem, multiple knapsack problem, solver