Para iniciar esta Tesis Doctoral se buscó un problema de producción sencillo pero de amplia aplicación práctica que permitiera adaptarlo para llegar a problemas más generales y de más amplia aplicación. Por este motivo, nos centramos en las máquinas paralelas, y dentro de ellas, en las no relacionadas dado que son una generalización de los casos de máquinas idénticas y de las uniformemente relacionadas. Escogimos el objetivo de minimizar el tiempo máximo de finalización o Cm ax, uno de los más comunes de la literatura. Este problema tiene la facultad de que, a pesar de su carácter teórico, tiene una amplia aplicación práctica, como el caso de secuenciar las tareas de los hornos de cocción cerámicos. Por otra parte se quería ampliar el problema para el caso en que no se usaran todas las máquinas o no se hicieran todos los trabajos necesariamente. Las metas perseguidas son el presentar unos algoritmos sencillos y potentes para la resolución del problema R//Cm ax, capaces de constituirse en el estado del arte. Dado que los modernos ordenadores montan casi en su totalidad varios núcleos en su CPU y los algoritmos se van adaptando a este hecho, también se ha buscado realizar una adaptación de los algoritmos para su uso en paralelo. Finalmente, se pone como meta el encontrar métodos eficaces y sencillos para la resolución de problemas de este tipo en donde no se emplearan todas las máquinas o no se realizaran todos los trabajos. En la presente Tesis Doctoral se realizó un amplio estudio de la literatura existente respecto al problema de máquinas paralelas no relacionadas y se extrajo el estado del arte, así como un estudio del posible tipo de instancias a emplear, dado que no existía una grupo de instancias tipo para este problema. Se presentan cuatro algoritmos iniciales sencillos que mejoran los resultados del estado del arte en algunos casos y dan mejores resultados de media en el conjunto total de instancias tratadas. / Fanjul Peyró, L. (2011). Nuevos algoritmos para el problema de secuenciación en máquinas paralelas no relacionadas y generalizaciones [Tesis doctoral no publicada]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/9312 / Palancia

In den vergangenen Jahrzehnten rückte das häufige Auftreten von multiplen Polylogarithmen und multiplen Zeta-Werten, in Feynman-Diagramm Rechnungen niedriger Ordnung, verstärkt in den wissenschaftlichen Fokus. Hierbei offenbarte sich eine Verbindung zu den mathematischen Theorien der Perioden und der iterierten Integrale von Chen. Eine ähnliche Allgegenwärtigkeit von multiplen Zeta-Werten wurde jüngst auch in der α'-Entwicklung von Genus-Null Stringtheorie Amplituden beobachtet. Davon inspiriert befasst sich diese Arbeit mit der Systematik der iterierten Integralen in den Streuamplituden der offenen Stringtheorie. Unser Fokus liegt insbesondere auf der Genus-Eins Amplitude, welche sich vollständig durch iterierte Integrale, die bezüglich einer punktierten elliptischen Kurve definiert sind, ausdrücken lässt. Wir führen den Begriff der getwisteten elliptischen multiplen Zeta-Werte ein. Dieser Begriff beschreibt eine Klasse von iterierten Integralen, die auf einer elliptischen Kurve definiert sind, bei welcher ein rationales Gitter entfernt wurde. Anschließend zeigen wir, dass die Entwicklung eines jeden getwisteten elliptischen multiplen Zeta-Wertes, bezüglich des modularen Parameters τ, durch ein Anfangswertproblem beschrieben wird. Weiterhin präsentieren wir ein Argument dafür, dass sich im Limes τ→i∞ jeder getwistete elliptische multiple Zeta-Wert durch zyklotomische multiple Zeta-Werte ausdrücken lässt. Schließlich beschreiben wir wie sich Genus-Eins Amplituden in offener Stringtheorie mithilfe von getwisteten elliptischen multiplen Zeta-Werten ausdrücken lassen und illustrieren dies für die Vier-Punkt Amplitude. Hierbei zeigt es sich, dass bis zu dritter Ordnung in α' alle Beiträge durch die Unterklasse der elliptischen multiplen Zeta-Werte ausgedrückt werden können, was wiederum äquivalent zu der Abwesenheit unphysikalischer Pole in Gliozzi-Scherk-Olive projizierter Superstringtheorie ist. / Over the last few decades the prevalence of multiple polylogarithms and multiple zeta values in low order Feynman diagram computations of quantum field theory has received increased attention, revealing a link to the mathematical theories of Chen’s iterated integrals and periods. More recently, a similar ubiquity of multiple zeta values was observed in the α'-expansion of genus-zero string theory amplitudes. Inspired by these developments, this work is concerned with the systematic appearance of iterated integrals in scattering amplitudes of open superstring theory. In particular, the focus will be on studying the genus-one amplitude, which requires the notion of iterated integrals defined on punctured elliptic curves. We introduce the notion of twisted elliptic multiple zeta values that are defined as a class of iterated integrals naturally associated to an elliptic curve with a rational lattice removed. Subsequently, we establish an initial value problem that determines the expansions of twisted elliptic multiple zeta values in terms of the modular parameter τ of the elliptic curve. Any twisted elliptic multiple zeta value degenerates to cyclotomic multiple zeta values at the cusp τ → i∞, with the corresponding limit serving as the initial condition of the initial value problem. Finally, we describe how to express genus-one open-string amplitudes in terms of twisted elliptic multiple zeta values and study the four-point genus-one open-string amplitude as an example. For this example we find that up to third order in α' all possible contributions in fact belong to the subclass formed by elliptic multiple zeta values, which is equivalent to the absence of unphysical poles in Gliozzi-Scherk-Olive projected superstring theory.

No description available.

Philosophiae Doctor - PhD / In this thesis, we describe linear codes over prime fields obtained from incidence designs of iterated line graphs of complete graphs Li(Kn) where i = 1,2. In the binary case, results are extended to codes from neighbourhood designs of the line graphs Li+l(Kn) using certain elementary relations. Codes from incidence designs of complete graphs, Kn' and neighbourhood designs of their line graphs, £1(Kn) (the so-called triangular graphs), have been considered elsewhere by others. We consider codes from incidence designs of Ll(Kn) and L2(Kn), and neighbourhood designs of L2(Kn) and L3(Kn). In each case, the basic parameters of the codes are determined. Further, we introduce a family of vertex-transitive graphs Rn that are embeddable into the strong product Ll(Kn) ~ K2' of triangular graphs and K2' a class that at first sight may seem unnatural but, on closer look, is a repository of graphs rich with combinatorial structures. For instance, unlike most regular graphs considered here and elsewhere that only come with incidence and neighbourhood designs, Rn also has what we have termed as 6-cycle designs. These are designs in which the point set contains vertices of the graph and every block contains vertices of a 6-cycle in the graph. Also, binary codes from incidence matrices of these graphs have other minimum words in addition to incidence vectors of the blocks. In addition, these graphs have induced subgraphs isomorphic to the family Hn of complete porcupines (see Definition 4.11). We describe codes from incidence matrices of Rn and Hn and determine their parameters. The discussion is concluded with a look at complements of Rn and Hn, respectively denoted by Rn and Hn. Among others, the complements rn are contained in the union of the categorical product Ll(Kn) x Kn' and the categorical product £1(Kn) x Kn (where £1(Kn) is the complement of the iii triangular graph £1(Kn)). As with the other graphs, we have also considered codes from the span of incidence matrices of Rn and Hn and determined some of their properties. In each case, automorphisms of the graphs, designs and codes have been determined. For the codes from incidence designs of triangular graphs, embeddings of Ll(Kn) x K2 and complements of complete porcupines, we have exhibited permutation decoding sets (PD-sets) for correcting up to terrors where t is the full error-correcting capacity of the codes. For the remaining codes, we have only been able to determine PD-sets for which it is possible to correct a fraction of t-errors (partial permutation decoding). For these codes, we have also determined the number of errors that can be corrected by permutation decoding in the worst-case.

In dieser Arbeit werden Zufallsfeld-Ising-Modelle mit einem eingefrorenen dichotomen symmetrischen Zufallsfeld für den eindimensionalen Fall und das Bethe-Gitter untersucht. Dabei wird die kanonische Zustandssumme zu der eines einzelnen Spins in einem effektiven Feld umformuliert. Im ersten Teil der Arbeit werden das mulktifraktale Spektrum dieses effektiven Feldes untersucht, Übergänge im Spektrum erklärt und Ungleichungen zwischen lokalen und globalen Dimensionsbegriffen bewiesen, die eine weitgehend vollständige Charakterisierung des multifraktalen Spektrums durch eine Reihe von Schranken erlauben. Ein weiterer Teil der Arbeit beschäftigt sich mit einer ähnlichen Charakterisierung des Maßes der lokalen Magnetisierung, das aus dem Maß des effektiven Feldes durch Faltung hervorgeht. In diesem Zusammenhang wird die Faltung von Multifraktalen in einem allgemeineren Rahmen behandelt und Zusammenhänge zwischen den multifraktalen Eigenschaften der Faltung und denen der gefalteten Maße bewiesen. Im dritten Teil der Dissertation wird der Phasenübergang von Ferro- zu Paramagnetismus im Modell auf dem Bethe Gitter untersucht. Neben verbesserten exakten Schranken für die Eindeutigkeit des paramagnetischen Zustands werden im wesentlichen drei Kriterien für die tatsächliche Lage des Übergangs angegeben und numerisch ausgewertet. Die multifraktalen Eigenschaften des effektiven Felds im Modell auf dem Bethe-Gitter schließlich erweisen sich als trivial, da die interessanten Dimensionen nicht existieren. / In this work random field Ising models with quenched dichotomous symmetric random field are considered for the one-dimensional case and on the Bethe lattice. To this end the canonical partition function is reformulated to the partition function of one spin in an effective field. In the first part of the work the multifractal spectrum of this effective field is investigated, transitions in the spectrum are explained and inequalities between local and global generalized fractal dimensions are proven which allow to characterize the multifractal spectrum bei various bounds. A further part of the work is dedicated to the characterization of the measure of the local magnetization which is obtained by convolution of the measure of the effective field with itself. In this context the convolution of multifractals is investigated in a more general setup and relations between the multifractal properties of the convolution and the multifractal properties of the convoluted measures are proven. The phase transition from ferro- to paramagnetismus for the model on the Bethe lattice is investigated in the third part of the thesis. Apart from improved exact bounds for the uniqueness of the paramagnetic state essentially three criteria for the transition are developped and numerically evaluated to determine the transition line. The multifractal properties of the effective field for the model on the Bethe lattice finally turn out to be trivial because the interesting dimensions do not exist.

No description available.

No description available.

The unimodality of a function seems a simple concept. But in the Euclidean space R^m, m=3,4,..., it is not easy to define. We have an easy tool to find the minimum point of a unimodal function. The goal of this project is to formalize and support distinctive strategies that typically guarantee convergence. Support is given both by analytic arguments and simulation study. Application is envisioned in low-dimensional but non-trivial problems. The convergence of the proposed iterated grid search algorithm is presented along with the results of particular application studies. It has been recognized that the derivative methods, such as the Newton-type method, are not entirely satisfactory, so a variety of other tools are being considered as alternatives. Many other tools have been rejected because of apparent manipulative difficulties. But in our current research, we focus on the simple algorithm and the guaranteed convergence for unimodal function to avoid the possible chaotic behavior of the function. Furthermore, in case the loss function to be optimized is not unimodal, we suggest a weaker condition: almost (noisy) unimodality, under which the iterated grid search finds an estimated optimum point. / Ph. D.

O ambiente de produção abordado neste trabalho é o Job Shop Flexível (JSF), uma generalização do Job Shop (JS). O problema de programação de tarefas, ou jobs, no ambiente JS é classificado por Garey; Johnson e Sethi (1976) como NP-Difícil e o JSF é, no mínimo, tão difícil quanto o JS. O JSF é composto por um conjunto de jobs, cada qual constituído por operações. Cada operação deve ser processada individualmente, sem interrupção, em uma única máquina de um subconjunto de máquinas habilitadas. O principal critério de desempenho considerado é a minimização dos atrasos dos jobs. São apresentados modelos de Programação Linear Inteira Mista (PLIM) para minimizar o atraso total e o instante de término da última operação, o makespan. São propostas novas regras de prioridade dos jobs, além de adaptações de regras da literatura. Tais regras são utilizadas por heurísticas construtivas e são aliadas a estratégias cujo objetivo é explorar características específicas do JSF. Visando aprimorar as soluções inicialmente obtidas, são propostas buscas locais e outros mecanismos de melhoria utilizados no desenvolvimento de três meta-heurísticas de diferentes categorias. Essas meta-heurísticas são: Iterated Local Search (ILS), classificada como meta-heurística de trajetória; Greedy Randomized Adaptive Search (GRASP), meta-heurística construtiva; e Artificial Bee Colony (ABC), meta-heurística populacional recentemente proposta. Esses métodos foram selecionados por alcançarem bons resultados para diversos problemas de otimização da literatura. São realizados experimentos computacionais com 600 instâncias do JSF, permitindo comparações entre os métodos de resolução. Os resultados mostram que explorar as características do problema permite que uma das regras de prioridade propostas supere a melhor regra da literatura em 81% das instâncias. As meta-heurísticas ILS, GRASP e ABC chegam a conseguir mais de 31% de melhoria sobre as soluções iniciais e a obter atrasos, em média, somente 2,24% superiores aos das soluções ótimas. Também são propostas modificações nas meta-heurísticas que permitem obter melhorias ainda mais expressivas sem aumento do tempo de execução. Adicionalmente é estudada uma versão do JSF com operações de Montagem e Desmontagem (JSFMD) e os experimentos realizados com um conjunto de 150 instâncias também indicam o bom desempenho dos métodos desenvolvidos. / The production environment addressed herein is the Flexible Job Shop (FJS), a generalization of the Job Shop (JS). In the JS environment, the jobs scheduling problem is classified by Garey; Johnson and Sethi (1976) as NP-Hard and the FJS is at least as difficult as the JS. FJS is composed of a set of jobs, each consisting of operations. Each operation must be processed individually, without interruption, in a single machine of a subset of enabled machines. The main performance criterion is minimizing the jobs tardiness. Mixed Integer Linear Programming (MILP) models are presented. These models minimize the total tardiness and the completion time of the last operation, makespan. New priority rules of jobs are proposed, as well as adaptations of rules from the literature. These rules are used by constructive heuristics and are combined with strategies aimed at exploiting specific characteristics of FSJ. In order to improve the solutions initially obtained, local searches and other improvement mechanisms are proposed and used in the development of metaheuristics of three different categories. These metaheuristics are: Iterated Local Search (ILS), classified as trajectory metaheuristic; Greedy Randomized Adaptive Search (GRASP), constructive metaheuristic, and Artificial Bee Colony (ABC), recently proposed population metaheuristic. These methods were selected owing to their good results for various optimization problems in the literature. Computational experiments using 600 FJS instances are carried out to allow comparisons between the resolution methods. The results show that exploiting the characteristics of the problem allows one of the proposed priority rules to exceed the best literature rule in about 81% of instances. Metaheuristics ILS, GRASP and ABC achieve more than 31% improvement over the initial solutions and obtain an average tardiness only 2.24% higher than the optimal solutions. Modifications in metaheuristics are proposed to obtain even more significant improvements without increased execution time. Additionally, a version called Disassembly and Assembly FSJ (DAFJS) is studied and the experiments performed with a set of 150 instances also indicate good performance of the methods developed.

O ambiente de produção abordado neste trabalho é o Job Shop Flexível (JSF), uma generalização do Job Shop (JS). O problema de programação de tarefas, ou jobs, no ambiente JS é classificado por Garey; Johnson e Sethi (1976) como NP-Difícil e o JSF é, no mínimo, tão difícil quanto o JS. O JSF é composto por um conjunto de jobs, cada qual constituído por operações. Cada operação deve ser processada individualmente, sem interrupção, em uma única máquina de um subconjunto de máquinas habilitadas. O principal critério de desempenho considerado é a minimização dos atrasos dos jobs. São apresentados modelos de Programação Linear Inteira Mista (PLIM) para minimizar o atraso total e o instante de término da última operação, o makespan. São propostas novas regras de prioridade dos jobs, além de adaptações de regras da literatura. Tais regras são utilizadas por heurísticas construtivas e são aliadas a estratégias cujo objetivo é explorar características específicas do JSF. Visando aprimorar as soluções inicialmente obtidas, são propostas buscas locais e outros mecanismos de melhoria utilizados no desenvolvimento de três meta-heurísticas de diferentes categorias. Essas meta-heurísticas são: Iterated Local Search (ILS), classificada como meta-heurística de trajetória; Greedy Randomized Adaptive Search (GRASP), meta-heurística construtiva; e Artificial Bee Colony (ABC), meta-heurística populacional recentemente proposta. Esses métodos foram selecionados por alcançarem bons resultados para diversos problemas de otimização da literatura. São realizados experimentos computacionais com 600 instâncias do JSF, permitindo comparações entre os métodos de resolução. Os resultados mostram que explorar as características do problema permite que uma das regras de prioridade propostas supere a melhor regra da literatura em 81% das instâncias. As meta-heurísticas ILS, GRASP e ABC chegam a conseguir mais de 31% de melhoria sobre as soluções iniciais e a obter atrasos, em média, somente 2,24% superiores aos das soluções ótimas. Também são propostas modificações nas meta-heurísticas que permitem obter melhorias ainda mais expressivas sem aumento do tempo de execução. Adicionalmente é estudada uma versão do JSF com operações de Montagem e Desmontagem (JSFMD) e os experimentos realizados com um conjunto de 150 instâncias também indicam o bom desempenho dos métodos desenvolvidos. / The production environment addressed herein is the Flexible Job Shop (FJS), a generalization of the Job Shop (JS). In the JS environment, the jobs scheduling problem is classified by Garey; Johnson and Sethi (1976) as NP-Hard and the FJS is at least as difficult as the JS. FJS is composed of a set of jobs, each consisting of operations. Each operation must be processed individually, without interruption, in a single machine of a subset of enabled machines. The main performance criterion is minimizing the jobs tardiness. Mixed Integer Linear Programming (MILP) models are presented. These models minimize the total tardiness and the completion time of the last operation, makespan. New priority rules of jobs are proposed, as well as adaptations of rules from the literature. These rules are used by constructive heuristics and are combined with strategies aimed at exploiting specific characteristics of FSJ. In order to improve the solutions initially obtained, local searches and other improvement mechanisms are proposed and used in the development of metaheuristics of three different categories. These metaheuristics are: Iterated Local Search (ILS), classified as trajectory metaheuristic; Greedy Randomized Adaptive Search (GRASP), constructive metaheuristic, and Artificial Bee Colony (ABC), recently proposed population metaheuristic. These methods were selected owing to their good results for various optimization problems in the literature. Computational experiments using 600 FJS instances are carried out to allow comparisons between the resolution methods. The results show that exploiting the characteristics of the problem allows one of the proposed priority rules to exceed the best literature rule in about 81% of instances. Metaheuristics ILS, GRASP and ABC achieve more than 31% improvement over the initial solutions and obtain an average tardiness only 2.24% higher than the optimal solutions. Modifications in metaheuristics are proposed to obtain even more significant improvements without increased execution time. Additionally, a version called Disassembly and Assembly FSJ (DAFJS) is studied and the experiments performed with a set of 150 instances also indicate good performance of the methods developed.