|
|
Fixed interval scheduling problems - stochastic extensions, formulations and algortihms
Leder, Ondřej ; Branda, Martin (advisor) ; Kopa, Miloš (referee)
Fixed interval scheduling problems have wide range of practical use in production planning, transportation, in hospitals or in schools when planning timetables. When solving these problems we often encounter requirement of integrality of solutions. Ignoring this condition is often not possible. In this thesis we propose some formulations of scheduling problems and their stochastic extensions. We also propone a new formulation of stochastic FIS problem, for which integrality of solution is byproduct of its definition. We present Gâteaux derivative and its relationship to stability of optimal value function of stochastic optimization problems under the influence of contamination. We propose a new theorem on the stability of such functions for fixed interval scheduling problems.
|
|
|
Fixed interval scheduling problems - stochastic extensions, formulations and algortihms
Leder, Ondřej ; Branda, Martin (advisor) ; Kopa, Miloš (referee)
Fixed interval scheduling problems have wide range of practical use in production planning, transportation, in hospitals or in schools when planning timetables. When solving these problems we often encounter requirement of integrality of solutions. Ignoring this condition is often not possible. In this thesis we propose some formulations of scheduling problems and their stochastic extensions. We also propone a new formulation of stochastic FIS problem, for which integrality of solution is byproduct of its definition. We present Gâteaux derivative and its relationship to stability of optimal value function of stochastic optimization problems under the influence of contamination. We propose a new theorem on the stability of such functions for fixed interval scheduling problems.
|
|
|
Schedule analysis
Novák, Ladislav ; Barták, Roman (advisor) ; Duša, Vladimír (referee)
Goal of this work was to engage in formal analysis of schedules, i.e. identifying weak spots and consequently design method to correct those weak points. Moreover this thesis addresses method, how from constructed corrections take appropriate set, called portfolio. Resulting software prototype called an Analyzer is integrated into FlowOpt project, which represents complex solution from modeling workflows, creation of schedules to displaying schedules using Gantt diagrams. Analyzer was developed mainly as a prototype application, which illustrates formal process of analysis. Powered by TCPDF (www.tcpdf.org)
|
|
|
Combination of Evolutionary Algorithms and Constraint Programming for Scheduling
Štola, Miroslav ; Pilát, Martin (advisor) ; Klíma, Martin (referee)
Scheduling problems and constraint satisfaction problems are generally known to be extremely hard. This thesis proposes a new evolutionary al- gorithm approach to solve a constrained-based scheduling problem. In this approach, variable orderings are evolved. The variable ordering serves as a parameter for the constraint solver. Its purpose is to determine the order in which variables are labelled by the solver. Hence the evolving individuals may be encoded as permutations. Therefore, our approach can be applied to a wider range of constraint satisfaction problems. Methods for generating the initial population of individuals based on the analysis of the precedence constraints graph are proposed. New genetic operators are presented and successfully applied. Our approach succeeded in finding a range of diverse schedules with the optimal makespan. Furthermore, multi-objective opti- mization was successfully attempted with the NSGA-II. 1
|
|
|
Planning operations of space probes
Kolombo, Martin ; Barták, Roman (advisor) ; Toropila, Daniel (referee)
The thesis addresses a complicated real-world scheduling problem from the space operations environment. The Mars Express Orbiter scheduling problem was first presented as a challenge by the European Space Agency. The thesis compares two different solutions. The first solution is an ad-hoc scheduler that is based on scheduling actions into a set of time windows and heavily utilizes local search techniques. The second solution models the problem as a constraint satisfaction problem (CSP) and uses the SICStus Prolog constraint programming solver to find a solution. Both schedulers are experimentally evaluated and the results are compared. Both approaches were able to provide a working solution. The conclusion however states that the more generic CSP based approach was capable of producing higher quality schedules even without a complicated heuristic. It however to compute the schedule for a small subset of inputs. On the other hand, the ad-hoc scheduler was capable of solving larger inputs but the produced solutions are not as good.
|
|
|
Integrating Planning and Scheduling
Dvořák, Filip ; Barták, Roman (advisor) ; Smith, David E. (referee) ; Hanzálek, Zdeněk (referee)
The main topic of the work is the design and development of a plan-space planning system FAPE that integrates explicit time reasoning, resource reasoning with discrete resources and reservoirs and hierarchical decompositions. FAPE is the first planning system that accepts the language ANML, supporting most of its major features. We investigate different aspects of the integration, also proposing a new problem reformulation technique for the state-variable representation and discovering a transition of performance between sparse and minimal temporal networks. We further extend FAPE with acting capabilities and evaluate the runtime properties and benefits of its expressiveness. Finally, we present FAPE as a planning and acting system in real world experiments, where FAPE operates a PR2 robot. Powered by TCPDF (www.tcpdf.org)
|
|
|
Integrating Planning and Scheduling
Dvořák, Filip
Title: Integrating Planning and Scheduling Author: Mgr. Filip Dvořák Department: Department of Theoretical Computer Science and Mathematical Logic Supervisor: prof. RNDr. Roman Barták, Ph.D., KTIML MFF UK Abstract: The main topic of the work is the design and development of a plan- space planning system FAPE that integrates explicit time reasoning, resource reasoning with discrete resources and reservoirs and hierarchical decompositions. FAPE is the first planning system that accepts the language ANML, supporting most of its major features. We investigate different aspects of the integration, also proposing a new problem reformulation technique for the state-variable represen- tation and discovering a transition of performance between sparse and minimal temporal networks. We further extend FAPE with acting capabilities and evalu- ate the runtime properties and benefits of its expressiveness. Finally, we present FAPE as a planning and acting system in real world experiments, where FAPE operates a PR2 robot. Keywords: planning, scheduling, temporal constraints, HTN, robotics
|
|
|
Dynamic Scheduling
Vlk, Marek ; Barták, Roman (advisor) ; Duša, Vladimír (referee)
One of the problems of real-life production scheduling is dynamics of manufacturing environments with new production demands and breaking machines during the schedule execution. Simple rescheduling from scratch in response to unexpected events occurring on the shop floor may require excessive computation time. Moreover, the recovered schedule may be prohibitively deviated from the ongoing schedule. This thesis reviews existing approaches in the field of dynamic scheduling and proposes techniques how to modify a schedule to accommodate disturbances such as resource failure, hot order arrival or order cancellation. The importance is put on the speed of suggested procedures as well as on a minimum modification from the original schedule. The scheduling model is motivated by the FlowOpt project, which is based on the Temporal Networks with Alternatives. The algorithms are written in the C# language.
|
|
|
Personal Timetabling
Doležal, Lukáš ; Barták, Roman (advisor) ; Duša, Vladimír (referee)
Despite all the advancements in Artificial Intelligence, we still do not have a broadly available application for automated scheduling of personal activities. The main difficulty in creating such an application is satisfying user's diverse expectations about time organization. In this study we focused on creating a tool that can help users with organizing their time. We designed a model for describing personal activities with user preferences. We formulated scheduling of personal activities as an optimization problem for which we designed and implemented a solving algorithm, aiming to schedule activities with precision of seconds. We created a prototype of web-calendar application powered by this model and an algorithm which we designed with the focus on ability to clearly display user's time and easily insert activities for automated scheduling. The web application is backed by RESTful API which enables implementing application on various platforms. Powered by TCPDF (www.tcpdf.org)
|
|
|
Optimization of Production Processes
Halas, David ; Dvořák, Jiří (referee) ; Popela, Pavel (advisor)
This thesis deals with modelling diffenrent types of production lines. Modeling is done by the mathematical programming and simulation methods. Optimization related computations are mostly implemented in program GAMS. Simulation is realized by using program Matlab/SimEvents. The results are presented by the Gantt diagrams.
|
guest ::
