Primjena heurističkih algoritama u vremenskom raspoređivanju poslova

master's thesis

• Title (english): Application of Heuristic Algorithms for Job Scheduling
• Author: Andrea Omićević
• Mentor: Tomislav Burić (mentor)
• Committee member: Tomislav Burić (predsjednik povjerenstva)
• Committee member: Josipa Pina Milišić (član povjerenstva)
• Committee member: Mario Krnić (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2021-07-06, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing

Abstract

U ovom radu objašnjeni su osnovni elementi i različite vrste problema raspoređivanja. Problemi raspoređivanja spadaju u skupinu NP-teških problema, stoga se za složenije probleme koriste različite heurističke metode. Detaljno je opisan problem obrade tijeka za koji su implementirane sljedeće heurističke metode: Johnsonovo pravilo, Palmerov algoritam, CDS algoritam, NEH algoritam i genetski algoritam.
Svaki algoritam je prezentiran na konkretnom primjeru. Za instance problema različitih veličina broja poslova i strojeva provedena je analiza i usporedba rezultata.

Abstract (english)

This paper explains the basic elements and different types of scheduling problems. The scheduling problems belong to a set of NP-hard problem group, so different heuristic methods are used to solve the problem.
The flowshop problem is described in detail and the following heuristic methods are used: Johnson’s rule, Palmer's algorithm, CDS algorithm, NEH algorithm and genetic algorithm.
Each algorithm is presented on a concrete example. Analysis and comparison of results are presented for multiple different configurations of the problem including various numbers of both jobs and machines.

• Keywords: raspoređivanje; heurističke metode; obrada tijeka; Johnsonovo pravilo; Palmerov algoritam; CDS algoritam; NEH algoritam; genetski algoritam
• Keywords (english): scheduling; heuristic methods; flowshop; Johnson’s rule; Palmer’s algorithm; CDS algorithm; NEH algorithm; genetic algorithm
• Language: croatian
• URN:NBN: urn:nbn:hr:168:878589
• 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: 2023-01-13 15:44:45