Cjelobrojno programiranje pri nekim problemima raspoređivanja

scientific master's theses

• Author: Krešimir Križanović
• Mentor: Vedran Mornar (mentor)
• Committee member: Damir Kalpić (predsjednik povjerenstva)
• Committee member: Vedran Mornar (član povjerenstva)
• Committee member: Luka Neralić (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; (Department of Applied Mathematics); Zagreb
• Defense date and country: 2019, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing
• Universal decimal classification (UDC): 004 - Computer science and technology. Computing. Data processing

Abstract

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.

Abstract (english)

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.

• Keywords: Linearno programiranje; cjelobrojno programiranje; binarno programiranje; simpleksna metoda; raspoređivanje; raspored sati; branch & bound; web-servis
• Keywords (english): Linear programming; integer programming; binary programming; simplex; scheduling; timetable; branch & bound; web service
• Language: croatian
• URN:NBN: urn:nbn:hr:168:913806
• Study programme: Title: Postgraduate master programe in computing; Study programme type: university; Study level: postgraduate; Academic / professional title: magistar inženjer računarstva (magistar inženjer računarstva)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Closed access
• Created on: 2019-07-17 11:10:32