Scheduling Parallel Batching Machines problem and Lockmaster's problem

Ivanišević, Stefan (author), Robič, Borut (mentor)

Waterway transport plays an important role in the transport of goods in the world. Ships and different vessels travelling through the inland waterways can shorten their trip and have faster and safer delivery of their goods and services. Inland waterways also connect major cities and industrial zones and compared to other modes of transport, which are often confronted with congestion and capacity problems, inland waterway transport is characterized by its reliability, energy efficiency and major capacity for increased exploitation. Our work consists of creating the optimal schedule that allows ships to have faster and easier pass through waterways. We address two problems, the Scheduling Parallel Batching Machines problem and Lockmaster's problem, both scheduling problems and both on the subject of creating an optimal schedule for the ships passing through the waterways. We created currently the only open-source implementation of those problems, with the interactive visualisation of the results.

• Language: English
• Keywords: Algorithms, Complexity, Scheduling Problems, Batching Problems, Flow shop, Scheduling Parallel Batching Machines problem, Locmkaster's problem
• Work type: Master's thesis/paper
• Typology: 2.09 - Master's Thesis
• Organization: FRI - Faculty of Computer and Information Science
• Year: 2021
• PID: 20.500.12556/RUL-128318
• COBISS.SI-ID: 72241155
• Publication date in RUL: 08.07.2021

Secondary language

• Language: Slovenian
• Title: Problem razvrščanja vzporednih skupin strojev in problem zapornic

Abstract

Vodni promet ima pomembno vlogo pri prevozu blaga po svetu. Ladje in različna plovila, ki potujejo po celinskih plovnih poteh, lahko skrajšajo svoje potovanje in imajo hitrejšo in varnejšo dostavo blaga in storitev. Celinske plovne poti povezujejo tudi večja mesta in industrijske cone, v primerjavi z drugimi načini prevoza, ki se pogosto srečujejo s prezasedenostjo in težavami z zmogljivostmi, pa je za celinske plovne poti značilna zanesljivost, energetska učinkovitost in velika zmogljivost za večje izkoriščanje. Naše delo je sestavljeno iz ustvarjanja optimalnega razvrščanja, ki ladjam omogoča hitrejši in lažji prehod po vodnih poteh. Obravnavamo dva problema, problem Razvrščanja Vzporednih Skupin Strojev in problem Zapornic. Oba sta problema razvrščanja in oba se nanašata na oblikovanje optimalnega urnika za ladje ki prečkajo plovne poti. Ustvarili smo trenutno edino open-source rešitev teh problemov z interaktivno vizualizacijo rezultatov.

• Keywords: algoritmi, kompleksnost, problemi razvrščanja, problemi skupin, krožilna trgovina, problem razvrščanja vzporednih skupin strojev, zaporničarjev problem