Original title: Volitelné aktivity v rozvrhování
Translated title: Optional Activities in Scheduling
Authors: Vlk, Marek ; Barták, Roman (advisor) ; Oddi, Angelo (referee) ; Tomášková, Hana (referee)
Document type: Doctoral theses
Year: 2021
Language: eng
Abstract: [eng] [cze]
Scheduling allocates scarce resources to activities such that certain constraints are satisfied and specific objectives are optimized. The activities to be executed are com- monly known or determined a priori in the planning stage. To improve the flexibility of scheduling systems, the concept of optional activities was invented. Optional activities are those activities whose presence in the resulting schedule is to be decided. Rather than determining which activities need to be executed and scheduling them in two consecu- tive phases, flexibility and efficiency can be improved significantly when both activity selection and time allocation are integrated within the same solver. Such an approach was implemented in a few Constraint Programming solvers and manifested great perfor- mance on multiple scheduling problems. In this thesis, we apply the concept of optional activities to scheduling problems that do not seem to involve optional activities, such as the production scheduling problem with sequence-dependent non-overlapping setups, but also on problems beyond the scheduling domain, such as the multi-agent path finding problem and its extension with weighted and capacitated arcs. 1 Rozvrhování přiděluje omezené zdroje na aktivity tak, aby byly splněny určité pod- mínky a optimalizovány konkrétní cíle. Aktivity, které mají být provedeny, jsou obvykle známé nebo jsou určeny předem ve fázi plánování. Pro zlepšení pružnosti rozvrhovacích systémů byl vyvinut koncept volitelných aktivit. Volitelné aktivity jsou ty aktivity, o je- jichž výskytu ve výsledném rozvrhu se má rozhodnout. Spíše než určovat, které aktivity je třeba vykonat, a rozvrhovat je, ve dvou po sobě jdoucích fázích, lze pružnost a účinnost významně zlepšit, pokud je výběr aktivit i přidělení času integrován do stejného řešiče. Takový přístup byl implementován u několika řešičů programování s omezujícími pod- mínkami a projevil se skvělým výkonem na řadě rozvrhovacích problémů. V této práci aplikujeme koncept volitelných aktivit na problémy rozvrhování, které na první pohled nezahrnují volitelné aktivity, jako je problém rozvrhování výroby s nepřekrývajícími se seřízeními závislými na sekvenci vykonávaných úloh, ale také na problémy mimo doménu rozvrhování, jako je problém hledání cest více agentů a jeho rozšíření zahrnující hrany s různými vahami a kapacitami. 1
Keywords: Constraint Programming|Multi-agent Path Finding|Non-overlapping Setups Scheduling|Joint Routing and Scheduling; Programování s omezujícími podmínkami|hledání cest více agentů|rozvrhování nepřekrývajících se seřízení|společné směrování a rozvrhování

Institution: Charles University Faculties (theses) (web)
Document availability information: Available in the Charles University Digital Repository.
Original record: http://hdl.handle.net/20.500.11956/152448

Permalink: http://www.nusl.cz/ntk/nusl-453691


The record appears in these collections:
Universities and colleges > Public universities > Charles University > Charles University Faculties (theses)
Academic theses (ETDs) > Doctoral theses