Search

Job shop je sustav koji se sastoji od poslova koji se određenim redoslijedom izvode na različitim strojevima. U industriji se za ovakve probleme mogu koristiti različiti algoritmi raspoređivanja zadataka na strojeve temeljeni na različitim kriterijima. Svrha ovog rada je testirati Google-ov alat OR-Tools i heuristički algoritam za rješavanje n/m problema koji koristi MWKR kao pravilo prioriteta na skupu job-shop problema i usporediti njihovu učinkovitost. Kao skup podataka za testiranje korišteno je 50 primjera Taillardovog skupa podataka. OR-Tools je nad istim skupom pokrenut dva puta s različitim vremenskim ograničenjima njegovog rada. Prvi put je bio ograničen na 1 min, a drugi put na 2 min. Heuristički algoritam nema vremenskog ograničenja. Parametri učinkovitosti na temelju kojih su rađene usporedbe su vrijeme potrebno za izvođenje svih zadataka (engl. makespan), iskoristivost strojeva i vrijeme izvođenja algoritma. Za dobivena vremena izvođenja svih zadataka izračunato je odstupanje od najbolje poznatih vremena izvođenja. Na korištenim podacima dobiveno je da je odstupanje ukupnog vremena izvođenja zadataka koje daje OR-Tools unutar intervala [0%, 10%]. Odstupanje vremena izvođenja koje daje heuristički algoritam nalazi se unutar intervala [10%, 35%]. OR-Tools je u 2 minute pronašao rješenje s boljim vremenu nego u 1 minuti. Iskoristivost u rasporedu koju je dao OR-Tools je u prosjeku oko 10% veće od one u rasporedu koji je dao heuristički algoritam. Ovi rezultati impliciraju da je OR-Tools bolji odabir ako je cilj nalaženje manjeg makespana ili dobivanja veće iskoristivosti. Međutim, ako je važnija brzina izvođenja algoritma, onda je heuristički algoritam vjerojatno bolji odabir. A job shop system consists of jobs that are performed on different machines in a certain order. In industry, different scheduling algorithms based on different criteria can be used for such problems. The purpose of this paper is to test Google’s OR-Tools tool and a heuristic algorithm for solving n/m problems that uses MWKR as a priority rule on a set of job-shop problems and compare their effectiveness. 50 examples from Eric Taillard's dataset were used for analysis. OR-Tools was run twice, each time with a different time limit. The first time it was limited to 1 min and the second time to 2 min. The heuristic algorithm was run without a time limit. The efficiency parameters used for comparison are makespan (time required to perform all tasks), efficiency of machines and execution time of the algorithm. For each achieved makespan a deviation from best known makespan was calculated. On the used dataset, the deviation for makespan achieved by OR-Tools was inside the interval [0%, 10%]. Deviation for makespan achieved by heuristic algorithm was inside the interval [10%, 35%]. OR-Tools found a solution with better makespan in 2 minutes than in 1 minute. The efficiency of machines in the layout provided by OR-Tools is on average about 10% higher than that in the layout provided by the heuristic algorithm. These results imply that OR-Tools is a better choice if the goal is to find a smaller makespan or get higher resource utilization. However, if the execution speed of the algorithm is more important, then the heuristic algorithm is probably a better choice.

Sustavi za rad u stvarnom vremenu moraju osim logičke ispravnosti zadovoljiti i zadana vremenska ograničenja. Za jednostavne sustave može se koristiti upravljačka petlja ili upravljanje zasnovano na događajima (pomoću prekida). Kod složenijih sustava praktičnije je koristiti operacijski sustav za rad u stvarnom vremenu. Takvi operacijski sustavi nude više različitih algoritama raspoređivanja zadataka koji mogu pomoći da sustav što efikasnije obavlja poslove na vrijeme. Raspoređivanje može biti prekidivo, pri čemu zadatak u izvođenju može biti prekinut od strane drugog zadatka, ili neprekidivo, pri čemu zadatak koji se izvodi ne može biti prekinut već mora biti obavljen do kraja. Također algoritme raspoređivanja možemo podijeliti na statičke (raspoređivanje na temelju unaprijed zadanih parametara) i dinamičke (sustav tijekom rada mijenja parametre raspoređivanja). Neki od najčešće korištenih algoritama raspoređivanja su: FCFS (raspoređivanje po redu prispijeća), RR (kružno raspoređivanje podjelom vremena), prioritetno raspoređivanje, te EDF (raspoređivanje po vremenu krajnjeg završetka). In addition to logical correctness, real-time systems must also meet the set time limits. For simple systems, a control loop or event-based control (using interrupts) can be used. For more complex systems, it is more convenient to use the real-time operating system. Real-time operating systems offer a number of different task scheduling algorithms that can help the system perform tasks on time as efficiently as possible. Task scheduling can be preemptive, whereby a task in progress can be interrupted by another task, or cooperative, whereby the task being performed cannot be interrupted but must be completed. Also, scheduling algorithms can be divided into static (scheduling based on predefined parameters) and dynamic (the system changes scheduling parameters during operation). Some of the most commonly used scheduling algorithms are: FCFS (First Come First Serve), RR (Round Robin), priority scheduling, and EDF (Earliest Deadline First).

Ovaj rad pokriva problem implementacije algoritma raspoređivača u jednom kompleksnom operacijskom sustavu za rad u stvarnom vremenu, kao što je FreeRTOS. Cilj je bio što efikasnije i što sažetije implementirati algoritam sporadičnog raspoređivača direktno u samu jezgru FreeRTOS sustava. U radu se nalazi i opis nekih vrsta različitih raspoređivača, sam sporadični raspoređivač koji je glavna tema ovog rada, kao i opis Arduino sklopovlja na kojemu se izvodi programski kod pokriven ovim radom, te način i opis raspoređivanja zadataka u trenutno dostupnom FreeRTOS sustavu. Opisane su neke od funkcionalnosti FreeRTOS sustava, kao i načini i kratke upute za njegovo korištenje. This thesis covers a problem of implementing an scheduling algorithm in one of the most complex, yet free RTOS systems, called FreeRTOS. The goal was the most efficient and the simplest implementation of sporadic scheduler in the FreeRTOS kernel. Thesis covers a short introduction to task schedulers in general, short summary of Arduino platform, and usage of FreeRTOS kernel from the user perspective.

Ovaj rad opisuje implementaciju raspoređivanja poslova unutar jezgre Linuxa s fokusom na raspoređivač nekritičnih poslova CFS. U sklopu rada implementiran je jednostavniji raspoređivač baziran na redovima zadataka prisutnim u raspoređivaču MuQSS. Uravnoteživanje opterećenja bazirano je na algoritmu prisutnom u FreeBSD jezgri. Raspoređivač je implementiran u obliku raspoređivačkog razreda i dodan u jezgru uz ostale razrede. Performanse novog raspoređivača i CFS-a testirane su i uspoređene korištenjem standardnih alata za ocjenjivanje raspoređivača. This work describes the implementation of task scheduling algorithms in the Linux kerne with focus on CFS. As part of this work a simpler scheduler is implemented. This scheduler is based on task queues found in MuQSS. Load balancing algorithm is based on FreeBSD kernel. This simple scheduler is implemented as a scheduling class and added alongside existing classes. The throughput and wakeup latencies of both the new scheduler and CFS were tested and compared using standard scheduler benchmarks.

Za heterogeni sustav koji se sastoji od jednog mobilnog robota i tri bespilotne letjelice projektirano je rješenje za planiranje i koordinaciju misije izgradnje zida predefinirane strukture. Zid se sastoji od cigli različitih veličina i oblika od kojih je neke potrebno prenijeti s više robota istovremeno. Problem izgradnje zida strukturiran je TÆMS jezikom, a planiranje i koordinacija heterogenog sustava temelji se na generičkom pristupu po uzoru na GPGP model. Zadaci se raspoređuju pomoću genetskog algoritma koji nastoji optimizirati ukupnu kvalitetu, trajanje i trošak misije. Razvijeno rješenje validirano je u realističnom simulacijskom okruženju Gazebo. A solution for planning and coordinating the mission of constructing a wall with predefined structure is designed for a heterogeneous system consisting of one mobile robot and three unmanned aerial vehicles. The wall consists of bricks of various weights and sizes, some of which need to be transported with multiple robots at the same time. Wall construction problem is structured using TÆMS language and planning and coordination of the heterogeneous system is implemented with a generic approach based on GPGP model. Tasks are scheduled using a genetic algorithm that seeks to optimize the overall quality, duration and cost of the mission. The developed solution is validated in the realistic Gazebo simulation environment.

Operacijski sustav za ugradbene sustave za rad u stvarnom vremenu s mješovitom razinom kritičnosti razvijen u ovom završnom radu je namijenjen za Cortex-R platformu. Cortex-R platforma je namijenjena za stroge sustave za rad u stvarnom vremenu i sustave s različitom razinom kritičnosti. Implementiran je OPA algoritam za statičku dodjelu prioriteta skupu zadataka s različitom razinom kritičnosti. Implementiran je statički pristup raspoređivanju zadataka SMC i adaptivni pristup raspoređivanju zadataka AMCrtb. Razvijeni operacijski sustav podržava upravljanje prekidima, memorijom i vremenom. Sustav je razvijen za ARM procesorsku arhitekturu. Sustav je testiran na TMS570LC43x pločici. In this thesis real-time operating system for mixed criticality was developed for Cortex-R target platform. Cortex-R platform is intended for hard RTOS and mixed criticality systems. In this assignment OPA algorithm was implemented for static priority assignment for set of tasks with mixed criticality. Static task scheduling approach (SMC) was implemented, as well as the adaptive approach (AMCrtb). Operating system that was developed supports interrupt handling, memory management and time management. System was developed for ARM architecture and was tested on TMS570LC43x board.

Rad opisuje sustave za rad u stvarnom vremenu te svojstva takvih sustava, različite načine raspoređivanja zadataka u takvim sustavima te način na koji se ostvaruje višedretvenost. Opisuje se i dvorazinski raspoređivač koji je nastao kao rezultat ovoga rada. Raspoređivač koristi dvije razine raspoređivanja, jednu za zadatke sa strogim krajnjim rokovima i drugu za zadatke s blažim krajnjim rokovima. Još se opisuju prednosti i nedostatci dvorazinskog raspoređivača u odnosu na vremenski raspoređivač koji se koristi u jednom sustavu za rad u stvarnom vremenu te moguća poboljšanja dvorazinskog raspoređivača. The paper describes real-time systems and the properties of such systems, different ways of scheduling tasks in such systems, and the way of achieving multitasking in the real-time system. It also describes the two-level scheduler that is the result of this paper. The two-level scheduler uses two levels of scheduling, one level for tasks with hard deadlines, and the other level for tasks with soft deadlines. The advantages and disadvantages of the two-level scheduler when compared to the time triggered scheduler which is used in one hard real time system and possible improvements of the two-level scheduler.

Pronalaženje metoda za ostvarivanje koherentnog, robusnog i prilagodljivog ponašanja skupina autonomnih robota je jedan od najvećih problema s područja robotike. U ovom radu koristi se generički pristup po uzoru na GPGP model koji omogućava uspješnu kordinaciju heterogenog sustava robota neovisno o domeni problema koji se rješava. Hijerarhijski prikaz problema jezikom T\AE MS pruža bogatu definiciju strukture zadataka te podržava definiranje složenih međuovisnosti zadataka. Proces planiranja misije pojedinih agenata ostvaren je raspoređivanjem zadataka na temelju kriterija (DTC) koji definiraju način određivanja kvalitete rasporeda i usmjeravaju postupak planiranja prema boljim rješenjima. Kako bi agenti djelovali udruženo u svrhu ispunjenja zajedničke misije, realiziran je skup posebnih koordinacijskih mehanizama. Finding methods for achieving coherent, robust and adaptive behavior of a group of autonomous robots is one of the greatest problems in the field of robotics. This thesis employs a generic approach inspired by GPGP model that allows for successful coordination of heterogeneous robot systems regardless of the domain of the problem being solved. Hierarchical problem representation using T\AE MS framework provides rich definition of task structure and supports specification of complex task interdependence. DTC scheduler used for creating agent's local schedule copes with high-order complexity while custom tailoring a way to achieve mission goal to fit a particular client's criteria. In order to accomplish coordinated agent behavior, a special set of coordination mechanisms was developed.