diplomsko delo
Nace Sever (Author), Matjaž Konvalinka (Mentor), Tea Tušar (Co-mentor)

Abstract

Časovno razporejanje terenskega dela je optimizacijski problem, pri katerem želimo poiskati čim boljšo razporeditev nalog za delavca. Želimo, da razpored ne krši nobene omejitve in optimizira dane kriterije. Problem formalno definiramo in zapišemo v obliki mešanega celoštevilskega linearnega programa. Rešujemo ga z uporabo knjižnic OR-Tools in SCIP. Ugotovimo, da za probleme z več kot petimi nalogami algoritem ne deluje dovolj hitro, oziroma pri dani časovni omejitvi ne deluje dovolj dobro. Zato predlagamo poenostavitev problema, ki dovolj zmanjša časovno zahtevnost, da so hitro rešljivi tudi problemi z več kot petimi nalogami.

Keywords

mešano celoštevilsko linearno programiranje;problem razporejanja;interdisciplinarni študij;univerzitetni študij;diplomske naloge;

Data

Language: Slovenian
Year of publishing:
Typology: 2.11 - Undergraduate Thesis
Organization: UL FRI - Faculty of Computer and Information Science
Publisher: [N. Sever]
UDC: 519.852(043.2)
COBISS: 124273155 Link will open in a new window
Views: 299
Downloads: 58
Average score: 0 (0 votes)
Metadata: JSON JSON-RDF JSON-LD TURTLE N-TRIPLES XML RDFA MICRODATA DC-XML DC-RDF RDF

Other data

Secondary language: English
Secondary title: Fieldwork scheduling with mixed-integer linear programming
Secondary abstract: Fieldwork scheduling is an optimization problem where we want to find the best assignment of tasks to the worker. We want to find a schedule that doesn't violate constraints and optimizes the criteria. We formally define and formulate the problem in the form of a mixed-integer linear program and solve it using the OR-Tools and SCIP libraries. We find that for problems with more than five tasks, the algorithm does not work fast enough, or rather, it does not work well enough with the given time limit. Because of that we propose a simplification of the problem, which reduces the time complexity enough so that also problems with more than five tasks can be solved quickly.
Secondary keywords: mixed-integer linear programming;scheduling problem;computer science;computer and information science;computer science and mathematics;interdisciplinary studies;diploma;Linearno programiranje;Računalništvo;Univerzitetna in visokošolska dela;
Type (COBISS): Bachelor thesis/paper
Study programme: 1000407
Embargo end date (OpenAIRE): 1970-01-01
Thesis comment: Univ. v Ljubljani, Fak. za računalništvo in informatiko
Pages: 51 str.
ID: 16469451