Realization of an Optimal Schedule for the Two-machine Flow-Shop with Interval Job Processing Times

Non-preemptive two-machine flow-shop scheduling problem with uncertain processing times of n jobs is studied. In an uncertain version of a scheduling problem, there may not exist a unique schedule that remains optimal for all possible realizations of the job processing times. We find necessary and sufficient conditions (Theorem 1) when there exists a dominant permutation that is optimal for all possible realizations of the job processing times. Our computational studies show the percentage of the problems solvable under these conditions for the cases of randomly generated instances with n ≤ 100 . We also show how to use additional information about the processing times of the completed jobs during optimal realization of a schedule (Theorems 2 – 4). Computational studies for randomly generated instances with n ≤ 50 show the percentage of the two- machine flow-shop scheduling problems solvable under the sufficient conditions given in Theorems 2 – 4.

Finding the Relationship between a Search Algorithm and a Class of Functions on Discrete Space by Exhaustive Search

* The work is supported by RFBR, grant 04-01-00858-a.

Fractional Powers of Almost Non-Negative Operators

Mathematics Subject Classification: Primary 47A60, 47D06.

Lie Groups as Four-Dimensional Special Complex Manifolds with Norden Metric

Марта Теофилова - Конструиран е пример на четиримерно специално комплексно многообразие с норденова метрика и постоянна холоморфна секционна кривина чрез двупара-метрично семейство от разрешими алгебри на Ли. Изследвани са кривинните свойства на полученото многообразие. Дадени са необходими и достатъчни усло-вия за разглежданото многообразие да бъде изотропно келерово.

Finite Groups as the Union of Proper Subgroups

2000 Mathematics Subject Classification: 20D60,20E15.

Cascade artificial neural networks technique for solving ellipsometry problems

Ellipsometry is a well known optical technique used for the characterization of reflective surfaces in study and films between two media. It is based on measuring the change in the state of polarization that occurs as a beam of polarized light is reflected from or transmitted through the film. Measuring this change can be used to calculate parameters of a single layer film such as the thickness and the refractive index. However, extracting these parameters of interest requires significant numerical processing due to the noninvertible equations. Typically, this is done using least squares solving methods which are slow and adversely affected by local minima in the solvable surface. This thesis describes the development and implementation of a new technique using only Artificial Neural Networks (ANN) to calculate thin film parameters. The new method offers a speed in the orders of magnitude faster than preceding methods and convergence to local minima is completely eliminated.

Mean field evolution in an open quantum system

In this thesis, we consider N quantum particles coupled to collective thermal quantum environments. The coupling is energy conserving and scaled in the mean field way. There is no direct interaction between the particles, they only interact via the common reservoir. It is well known that an initially disentangled state of the N particles will remain disentangled at times in the limit N -> [infinity]. In this thesis, we evaluate the η-body reduced density matrix (tracing over the reservoirs and the N - η remaining particles). We identify the main disentangled part of the reduced density matrix and obtain the first order correction term in 1/N. We show that this correction term is entangled. We also estimate the speed of convergence of the reduced density matrix as N -> [infinity]. Our model is exactly solvable and it is not based on numerical approximation.

Estimating quantum chromatic numbers

We develop further the new versions of quantum chromatic numbers of graphs introduced by the first and fourth authors. We prove that the problem of computation of the commuting quantum chromatic number of a graph is solvable by an SDP algorithm and describe an hierarchy of variants of the commuting quantum chromatic number which converge to it. We introduce the tracial rank of a graph, a parameter that gives a lower bound for the commuting quantum chromatic number and parallels the projective rank, and prove that it is multiplicative. We describe the tracial rank, the projective rank and the fractional chromatic numbers in a unified manner that clarifies their connection with the commuting quantum chromatic number, the quantum chromatic number and the classical chromatic number, respectively. Finally, we present a new SDP algorithm that yields a parameter larger than the Lovász number and is yet a lower bound for the tracial rank of the graph. We determine the precise value of the tracial rank of an odd cycle.

Algorithmique et complexité des systèmes à compteurs

Réalisé en cotutelle avec l'École normale supérieure de Cachan – Université Paris-Saclay

Mikroyrityksen ja tilitoimiston välisten prosessien kehittäminen sähköistämisen avulla

Tämä tutkielma käsittelee mikroyrityksen ja tilitoimiston välistä yhteistyötä sekä sen edistämistä sähköistämisen keinoin. Aihetta käsitellään ulkoistamisen näkökulmasta, jolloin taloushallinnon prosessit käsittävät tilitoimiston ja yrityksen välisen tiedonvaihdon ja yhteistyön. Tutkielmassa käsitellään taloushallinnon roolia ja prosesseja sekä taloushallinnon ulkoistamisen teoreettisia lähtökohtia. Tämän jälkeen syvennytään taloushallinnon sähköistämiseen sekä sen etuihin ja haittoihin. Aiheita pyritään käsittelemään sekä yleisellä tasolla että mikroyritysten näkökulmasta. Tutkielman tavoitteena on teorian ja empiirisen tutkimuksen avulla selvittää, millaisia sähköisiä keinoja valitun kohdeyrityksen ja tilitoimiston yhteistyön kehittämiseen on tarjolla ja kuinka nämä keinot edistäisivät osapuolten välistä yhteistyötä. Työssä käytetty tutkimusmenetelmä on kvalitatiivinen ja tutkittavaa ilmiötä on tarkasteltu tapaustutkimuksen keinoin. Tutkimusaineisto kerättiin kohdeyrityksen omistajayrittäjältä keskusteluin sekä kohdeyrityksen käyttämälle tilitoimistolle sähköpostitse lähetetyllä kyselyllä. Tutkielmassa päädyttiin siihen, että sähköisistä menetelmistä on saatu apua esimerkiksi kuittikirjanpidossa. Käytössä olevien sähköisten palveluiden määrää sen sijaan voitaisiin vähentää ainakin poistamalla yksi laskujenhallintaohjelma käytöstä. Tämä edistäisi tositteiden kulkua yritykseltä kirjanpitäjälle ja samalla päästäisiin eroon myös yhdestä käyttöominaisuuksiltaan kehnosta laskujenhallintajärjestelmästä. Toisaalta todettiin, että ydinongelmat eivät loppujen lopuksi liity heikkoon teknologiaan vaan ihmisten välisiin suhteisiin eivätkä nämä ongelmat ole ratkaistavissa teknologian keinoin.

Exact Solution of Bayes and Minimax Change-Detection Problems

The challenge of detecting a change in the distribution of data is a sequential decision problem that is relevant to many engineering solutions, including quality control and machine and process monitoring. This dissertation develops techniques for exact solution of change-detection problems with discrete time and discrete observations. Change-detection problems are classified as Bayes or minimax based on the availability of information on the change-time distribution. A Bayes optimal solution uses prior information about the distribution of the change time to minimize the expected cost, whereas a minimax optimal solution minimizes the cost under the worst-case change-time distribution. Both types of problems are addressed. The most important result of the dissertation is the development of a polynomial-time algorithm for the solution of important classes of Markov Bayes change-detection problems. Existing techniques for epsilon-exact solution of partially observable Markov decision processes have complexity exponential in the number of observation symbols. A new algorithm, called constellation induction, exploits the concavity and Lipschitz continuity of the value function, and has complexity polynomial in the number of observation symbols. It is shown that change-detection problems with a geometric change-time distribution and identically- and independently-distributed observations before and after the change are solvable in polynomial time. Also, change-detection problems on hidden Markov models with a fixed number of recurrent states are solvable in polynomial time. A detailed implementation and analysis of the constellation-induction algorithm are provided. Exact solution methods are also established for several types of minimax change-detection problems. Finite-horizon problems with arbitrary observation distributions are modeled as extensive-form games and solved using linear programs. Infinite-horizon problems with linear penalty for detection delay and identically- and independently-distributed observations can be solved in polynomial time via epsilon-optimal parameterization of a cumulative-sum procedure. Finally, the properties of policies for change-detection problems are described and analyzed. Simple classes of formal languages are shown to be sufficient for epsilon-exact solution of change-detection problems, and methods for finding minimally sized policy representations are described.

Multiple-Retrieval Case-Based Reasoning for Course Timetabling Problems

The structured representation of cases by attribute graphs in a Case-Based Reasoning (CBR) system for course timetabling has been the subject of previous research by the authors. In that system, the case base is organised as a decision tree and the retrieval process chooses those cases which are sub attribute graph isomorphic to the new case. The drawback of that approach is that it is not suitable for solving large problems. This paper presents a multiple-retrieval approach that partitions a large problem into small solvable sub-problems by recursively inputting the unsolved part of the graph into the decision tree for retrieval. The adaptation combines the retrieved partial solutions of all the partitioned sub-problems and employs a graph heuristic method to construct the whole solution for the new case. We present a methodology which is not dependant upon problem specific information and which, as such, represents an approach which underpins the goal of building more general timetabling systems. We also explore the question of whether this multiple-retrieval CBR could be an effective initialisation method for local search methods such as Hill Climbing, Tabu Search and Simulated Annealing. Significant results are obtained from a wide range of experiments. An evaluation of the CBR system is presented and the impact of the approach on timetabling research is discussed. We see that the approach does indeed represent an effective initialisation method for these approaches.

Multiple-retrieval case-based reasoning for course timetabling problems

The structured representation of cases by attribute graphs in a Case-Based Reasoning (CBR) system for course timetabling has been the subject of previous research by the authors. In that system, the case base is organised as a decision tree and the retrieval process chooses those cases which are sub attribute graph isomorphic to the new case. The drawback of that approach is that it is not suitable for solving large problems. This paper presents a multiple-retrieval approach that partitions a large problem into small solvable sub-problems by recursively inputting the unsolved part of the graph into the decision tree for retrieval. The adaptation combines the retrieved partial solutions of all the partitioned sub-problems and employs a graph heuristic method to construct the whole solution for the new case. We present a methodology which is not dependant upon problem specific information and which, as such, represents an approach which underpins the goal of building more general timetabling systems. We also explore the question of whether this multiple-retrieval CBR could be an effective initialisation method for local search methods such as Hill Climbing, Tabu Search and Simulated Annealing. Significant results are obtained from a wide range of experiments. An evaluation of the CBR system is presented and the impact of the approach on timetabling research is discussed. We see that the approach does indeed represent an effective initialisation method for these approaches.

Algorithmique et complexité des systèmes à compteurs

Réalisé en cotutelle avec l'École normale supérieure de Cachan – Université Paris-Saclay

Validación de la simulación numérica del flujo bifásico hidrodinámico en sistemas de lecho fluido

Este trabajo tiene como objetivo la mejora en la validación de la simulación numérica del flujo bifásico característico del transporte de lecho fluido, mediante la formulación y desarrollo de un modelo numérico combinado Volúmenes Finitos - Elementos Finitos. Para ello se simula numéricamente el flujo de mezcla sólido-gas en una Cámara de Lecho Fluido, bajo implementación en código COMSOL, cuyos resultados son mejores comparativamente a un modelo basado en el método de Elementos Discretos implementado en código abierto MFIX. El problema fundamental de la modelización matemática del fenómeno de lecho fluido es la irregularidad del dominio, el acoplamiento de las variables en espacio y tiempo y, la no linealidad. En esta investigación se reformula apropiadamente las ecuaciones conservativas del fenómeno, tales que permitan obtener un problema variacional equivalente y solucionable numéricamente. Entonces; se define una ecuación de estado en función de la presión hidrodinámica y la fracción volumétrica de sólidos, quedando desacoplado el sistema en tres sub-problemas, garantizando así la existencia de solución del problema general. Una vez aproximados numéricamente ambos modelos, se comparan los resultados de donde se observa que el modelo materia del presente artículo, verifica de forma más eficaz las condiciones de mezcla óptima, reflejada en la calidad del burbujeo y velocidad de mezcla.