Raspoređivanje zadataka u proizvodnim sustavima

undergraduate thesis

• Title (english): Scheduling of tasks in production systems
• Author: Matej Petrović
• Mentor: Tamara Petrović (mentor)
• Committee member: Tamara Petrović (član povjerenstva)
• Committee member: Ana Milas (član povjerenstva)
• Committee member: Marijana Peti (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2022-07-15, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing

Abstract

Job shop je sustav koji se sastoji od poslova koji se određenim redoslijedom izvode na različitim strojevima. U industriji se za ovakve probleme mogu koristiti različiti algoritmi raspoređivanja zadataka na strojeve temeljeni na različitim kriterijima. Svrha ovog rada je testirati Google-ov alat OR-Tools i heuristički algoritam za rješavanje n/m problema koji koristi MWKR kao pravilo prioriteta na skupu job-shop problema i usporediti njihovu učinkovitost. Kao skup podataka za testiranje korišteno je 50 primjera Taillardovog skupa podataka. OR-Tools je nad istim skupom pokrenut dva puta s različitim vremenskim ograničenjima njegovog rada. Prvi put je bio ograničen na 1 min, a drugi put na 2 min. Heuristički algoritam nema vremenskog ograničenja. Parametri učinkovitosti na temelju kojih su rađene usporedbe su vrijeme potrebno za izvođenje svih zadataka (engl. makespan), iskoristivost strojeva i vrijeme izvođenja algoritma. Za dobivena vremena izvođenja svih zadataka izračunato je odstupanje od najbolje poznatih vremena izvođenja. Na korištenim podacima dobiveno je da je odstupanje ukupnog vremena izvođenja zadataka koje daje OR-Tools unutar intervala [0%, 10%]. Odstupanje vremena izvođenja koje daje heuristički algoritam nalazi se unutar intervala [10%, 35%]. OR-Tools je u 2 minute pronašao rješenje s boljim vremenu nego u 1 minuti. Iskoristivost u rasporedu koju je dao OR-Tools je u prosjeku oko 10% veće od one u rasporedu koji je dao heuristički algoritam. Ovi rezultati impliciraju da je OR-Tools bolji odabir ako je cilj nalaženje manjeg makespana ili dobivanja veće iskoristivosti. Međutim, ako je važnija brzina izvođenja algoritma, onda je heuristički algoritam vjerojatno bolji odabir.

Abstract (english)

A job shop system consists of jobs that are performed on different machines in a certain order. In industry, different scheduling algorithms based on different criteria can be used for such problems. The purpose of this paper is to test Google’s OR-Tools tool and a heuristic algorithm for solving n/m problems that uses MWKR as a priority rule on a set of job-shop problems and compare their effectiveness. 50 examples from Eric Taillard's dataset were used for analysis. OR-Tools was run twice, each time with a different time limit. The first time it was limited to 1 min and the second time to 2 min. The heuristic algorithm was run without a time limit. The efficiency parameters used for comparison are makespan (time required to perform all tasks), efficiency of machines and execution time of the algorithm. For each achieved makespan a deviation from best known makespan was calculated. On the used dataset, the deviation for makespan achieved by OR-Tools was inside the interval [0%, 10%]. Deviation for makespan achieved by heuristic algorithm was inside the interval [10%, 35%]. OR-Tools found a solution with better makespan in 2 minutes than in 1 minute. The efficiency of machines in the layout provided by OR-Tools is on average about 10% higher than that in the layout provided by the heuristic algorithm. These results imply that OR-Tools is a better choice if the goal is to find a smaller makespan or get higher resource utilization. However, if the execution speed of the algorithm is more important, then the heuristic algorithm is probably a better choice.

• Keywords: raspoređivanje zadataka; job-shop; heuristika; OR-Tools
• Keywords (english): task scheduling; job-shop; heuristics; OR-Tools
• Language: croatian
• URN:NBN: urn:nbn:hr:168:176454
• Study programme: Title: Computing; Study programme type: university; Study level: undergraduate; Academic / professional title: sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva (sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Closed access
• Created on: 2023-01-15 11:03:35