|
|
Online Bin Stretching: Algorithms and Computer Lower Bounds
Böhm, Martin ; Sgall, Jiří (advisor) ; Durr, Christoph (referee) ; Kellerer, Hans (referee)
Online Bin Stretching: Algorithms and Computer Lower Bounds Author: Martin Böhm Abstract: We investigate a problem in semi-online algorithm design, called Online Bin Stretching. The problem can be understood as an online repacking problem: the goal of the algorithm is to repack items of various sizes into m containers of identical size R > 1. The input items arrive one by one and the algorithm must assign an item to a container before the next item arrives. A specialty of this problem is that there is a specific guarantee made to the algorithm: the algorithm learns at the start of the input that there exists a packing of all input items into m containers of capacity 1. Our goal is to design algorithms for this problem which successfully pack the entire incoming sequence one by one while requiring the lowest container capacity R possible. In this thesis, we show several new results about Online Bin Stretching: First, we design an algorithm that is able to pack the entire input into m containers of capacity 1.5 regardless of what the vale of m will be. Second, we show a specialized algorithm for the setting of just 3 containers; this algorithm is able to pack into 3 bins of capacity 1.375. Finally, we design and implement an involved search algorithm which is able to find lower bounds for Online Bin...
|
|
|
Online scheduling of multiprocessor jobs with preemption
Šimsa, Štěpán ; Sgall, Jiří (advisor) ; Kolman, Petr (referee)
Abstract. The thesis is devoted to the problem of online preemptive scheduling of mul- tiprocessor jobs. It gives a summary of previous work on this problem. For some special variants of the problem, especially if we restrict the sizes of jobs to one and two, new results are given, both in the terms of lower bounds and in the terms of competitive al- gorithms. A previously published lower bound is showed to be computed incorrectly and it is replaced by a correct lower bound in this thesis. An algorithm is presented for the special case of four processors and sizes of jobs one and two that is conjectured to achieve the best possible competitive ratio.
|
|
|
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.
|
guest ::
