Cjelobrojno programiranje pri nekim problemima raspoređivanja

magistarski rad

• Autor: Krešimir Križanović
• Mentor: Vedran Mornar (mentor)
• Član povjerenstva: Damir Kalpić (predsjednik povjerenstva)
• Član povjerenstva: Vedran Mornar (član povjerenstva)
• Član povjerenstva: Luka Neralić (član povjerenstva)
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Fakultet elektrotehnike i računarstva; (Zavod za primijenjenu matematiku); Zagreb
• Datum i država obrane: 2019, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: TEHNIČKE ZNANOSTI; Računarstvo
• Univerzalna decimalna klasifikacija (UDC): 004 - Računalna znanost i tehnologija. Računalstvo. Obrada podataka

Sažetak

Problemi raspoređivanja javljaju se u organizaciji poslovanja u različitim poslovnim okruženjima. Jedna od metoda za rješavanje takvih problema jest cjelobrojno programiranje, tj. linearno programiranje kod kojeg se zahtijeva da su varijable cjelobrojne ili čak binarne. Web-servisi su opće prihvaćena tehnologija koja omogućava komunikaciju između različitih sustava. U organizaciji rada i nastave na Fakultetu elektrotehnike i računarstva mogu se uočiti razni problemi raspoređivanja. Razmatrani su problemi: raspoređivanje izbornih predmeta po semestrima, raspoređivanje ispita unutar ispitnog roka te raspored sati. Prilikom rješavanja problema raspoređivanja korišteno je cjelobrojno programiranje i metoda grananja i ograđivanja. Koristeći javno dostupan alat lpsolve i programski jezik C# izgrađen je web-servis za rješavanje problema mješovitog cjelobrojnog programiranja. Također koristeći programski jezik C#, izgrađene su klijentske aplikacije za rješavanje svakog od problema. Podaci bitni za postavljanje problema dohvaćani su iz različitih baza podataka (ACCESS, SQL SERVER, IBM INFORMIX). Na temelju tih podataka postavljeni su problemi koje se onda pokušalo riješiti upotrebom izgrađenog web-servisa. Tijekom rješavanja problema ispitan je utjecaj raznih parametara na brzinu i mogućnost pronalaženja rješenja. Na temelju uspješnosti rješavanja analizirana je složenost pojedinih problema te prikladnost metode cjelobrojnog programiranja za njihovo rješavanje.

Sažetak (engleski)

Scheduling problems regularly occur in managing everyday activities in different companies. One of the methods used to solve such problems is Integer programming, or Linear programming where all or some of the variables are integer or even binary. Web services are a widely used technology that allows communication between different systems. There are many scheduling problems in managing students’ and teachers’ activities on Faculty of Electrical Engineering and Computing. Researched problems are: scheduling elective courses, scheduling exams within an exam term and students’ daily schedule. While solving those scheduling problems, Integer programming and Branch & Bound methods were applied. Using publicly available tool lpsolve and C# programming language, a web service for solving Mixed Integer Programming problems was created. Also using C# programming language, a client application was created to solve each of the problems. Data necessary for setting each problem up was obtained from different databases (ACCESS, SQL SERVER and IBM Informix). Using that data, the problems were set, and were attempted to be solved using before mentioned web service. During the process of solving the problems, the influence of various parameters on the speed and feasibility of the solutions was examined. Based on the success of the solving process, complexity of each problem as well as suitability of integer programming for solving it was researched.

• Ključne riječi: Linearno programiranje; cjelobrojno programiranje; binarno programiranje; simpleksna metoda; raspoređivanje; raspored sati; branch & bound; web-servis
• Ključne riječi (engleski): Linear programming; integer programming; binary programming; simplex; scheduling; timetable; branch & bound; web service
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:168:913806
• Studijski program: Naziv: Računarstvo; Vrsta studija: sveučilišni; Stupanj studija: poslijediplomski znanstveni (magistarski); Akademski / stručni naziv: magistar inženjer računarstva (mag. ing. comp.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Zatvoreni pristup
• Datum i vrijeme pohrane: 2019-07-17 11:10:32