Raspoređivanje poslova na nesrodnim strojevima po grupama

master's thesis

• Title (english): Batch scheduling for unrelated machines
• Author: Dominik Sebešić
• Mentor: Domagoj Jakobović (mentor)
• Committee member: Domagoj Jakobović (predsjednik povjerenstva)
• Committee member: Nikolina Frid (član povjerenstva)
• Committee member: Marin Golub (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2024-07-10, Croatia

Abstract

Predstavljen je problem minimizacije trenutka završetka obrade sustava s neidentičnim poslovima različitih veličina te dinamičkih vremena dolaska u sustav. Pošto je pokazano da je problem NP-težak, za rješavanje problema uvedene su heuristike i metode za grupiranje poslova u grupe, sortiranje poslova, sortiranje grupa na strojevima, raspoređivanje poslova na strojeve te raspoređivanje grupa na strojeve. Definirano je 6 heuristika i 4 evolucijska algoritma koji svaki koristi poseban tip enkodacije kromosoma. Determinističke heuristike smo podijelili u 2 kategorije. Prva kategorija grupira poslove u grupe, te zatim raspoređuje grupe po strojevima, dok druga kategorija raspoređuje poslove po strojevima i zatim grupira poslove posebno za svaki stroj. Evolucijske algoritme smo podijelili na način na koji enkodiraju kromosome. Tri algoritma koriste enkodacije s kojom se koriste uobičajeni operatori križanja i mutacije, dok zadnja vrsta enkodacije ima specifično definirane operatore mutiranja kojim se dobivaju efekti široke pretrage prostora rješenja ali i efekt unapređenja postojećih rješenja. Uvedena je mjera RPD koja definira uspješnost pojedinog algoritma s usporedbom na optimalno rješenje. Implementiran je paket metoda u programskom jeziku Python, te su heuristike i evolucijski algoritmi testirani na primjerima problema s različitim parametrima i početnim konfiguracijama. Rezultati su predstavljeni na način kojim se uspoređuju deterministički pristupi s evolucijskim algoritmima.

Abstract (english)

The problem of minimizing the makespan of a system with non-identical jobs of different sizes and dynamic arrival times is presented. Since the problem was shown to be NP-hard, heuristics and methods for batching jobs into batches, sorting jobs, sorting batches on machines, assigning jobs to machines, and assigning groups to machines were introduced to solve the problem. 6 heuristics and 4 evolutionary algorithms are defined, each using a special type of chromosome encoding. Deterministic heuristics are divided into 2 categories. The first category groups jobs into batches and then distributes the batches to the machines, while the second category distributes jobs to the machines and then batches the jobs separately for each machine. Evolutionary algorithms are divided according to the way they encode chromosomes. Three algorithms use encoding with which the usual crossover and mutation operators are used, while the last type of encoding has specifically defined mutation operators that obtain the effects of a wide search of the solution space, but also the effect of improving existing solutions. The RPD measure was also introduced, which defines the success of an individual algorithm with a comparison to the optimal solution. A package of methods in the Python programming language was implemented, and heuristics and evolutionary algorithms were tested on examples of problems with different parameters and initial configurations. The results are presented in a way that compares deterministic approaches with evolutionary algorithms.

• Keywords: heuristike raspoređivanje poslova; heuristike grupiranje poslova; nesrodni strojevi; paralelni strojevi; evolucijski algoritam; minimizacija dobrote sustava
• Keywords (english): job scheduling heuristics; job grouping heuristics; unrelated machines; parallel machines; genetic algorithm; minimization of makespan
• Language: croatian
• URN:NBN: urn:nbn:hr:168:823914
• Study programme: Title: Computing; Study programme type: university; Study level: graduate; Academic / professional title: magistar/magistra inženjer/inženjerka računarstva (magistar/magistra inženjer/inženjerka računarstva)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Closed access
• Created on: 2024-10-12 22:05:00