This thesis studies Production Scheduling in a multistage hybrid flowshop facility. It first states the general Production Planning and Scheduling problem and highlights some drawbacks of classical solutions. A theoretical decomposition-based approach is introduced whose main issue is to overcome non-efficient capacity utilization. By using Branch and Bound methods, an in-depth analysis of the scheduling part of the system is then carried out throughout the study and development of upper and lower bounds as well as branching schemes. Already-existing and new heuristics are presented and compared on different shop floor configurations. Five different heuristic approaches are studied. By scheduling the HFS one stage at a time the first approach uses different stage sequencing orders. The second and third approaches are mainly list heuristics. The second approach uses ideas derived from the multistage classical flowshop with a single machine per stage, while the third approach uses classical dispatching priority rules. The fourth and fifth approaches, respectively, use random scheduling and local search techniques. Statistical analysis is carried out in order to compare the heuristics and to select the best of them for each shop configuration. Already-existing and new lower bounds on the single stage subproblem are also presented and compared. Three new lower bounds are developed: a dual heuristic based bound, a partially preemptive bound and a heuristic for the so-called subset bound. Some of these lower bounds use a network flow algorithm. A new version of the “Preflow Push” algorithm which runs faster than the original one is presented. The best lower bounds are selected based on numerical tests. Two branch and bound algorithms are presented, an improved version of the sequence enumeration method and a generalization of the so-called interval branching method, along with several bounding strategies. Based on the upper and lower bound studies, several branch and bound algorithms are presented and compared using numerical tests on different shop floor configurations. Eventually, an Object Model for Scheduling Algorithm Implementations (OMSAI), that has been used for the computer implementation of the developed algorithms, is presented.

This thesis is about solving the manpower planning problem concerning stangand transitioning of pilots. The objective of the planning is to have enoughpilots to satisfy the demand while minimizing the cost. The main decisions totake are how many pilots to hire, which pilots to train and which courses toschedule. The planning problems that arise are both large and dicult whichmakes it important to use ecient solution methods. Seniority rules betweenpairs of pilots are the most complicating factor.A major part in the solution process is the solving of mixed integer programs.The emphasis in the thesis is to develop and test adaptations of the branch andbound algorithm to solve mixed integer programs faster. One of these is abranching principle that takes a problem specic structure into account. Agraph of implications is constructed from the seniority rules and this graph isthen used to estimate the impact of each branching candidate. The implementedmethods outperform the software XPRESS on some instances, while for mostinstances the performance is comparable.

We introduce a very simple but efficient idea for branch & bound (B&B) algorithms in global optimization (GO). As input for our generic algorithm, we need an upper bound algorithm for the GO maximization problem and a branching rule. The latter reduces the problem into several smaller subproblems of the same type. The new B&B approach delivers one global optimizer or, if stopped before finished, improved upper and lower bounds for the problem. Its main difference to commonly used B&B techniques is its ability to approximate the problem from above and from below while traversing the problem tree. It needs no supplementary information about the system optimized and does not consume more time than classical B&B techniques. Experimental results with the maximum clique problem illustrate the benefit of this new method. (author's abstract) / Series: Working Papers on Information Systems, Information Business and Operations

No description available.

No description available.

Techn. University, Diss., 2006--Darmstadt.

Thesis (M.S.)--University of Nevada, Reno, 2008. / "May, 2008." Includes bibliographical references (leaves 63-64). Online version available on the World Wide Web.

Universiẗat, Diss., 2005--Karlsruhe.

El objetivo general del presente trabajo de título es realizar, mediante la aplicación de criterios técnicos de ingeniería, una evaluación técnica del desempeño de los algoritmos de Relajación Lagrangeana (RL) y Branch and Bound (B&B) en la búsqueda de soluciones para el problema de optimización de corto plazo en el sistema eléctrico interconectado del norte grande (SING). En la primera parte de la memoria se muestra el planteamiento general del problema de optimización de la operación de corto plazo, el cual corresponde a un problema de optimización entero-mixto y un conjunto de restricciones lineales mediante las cuales se establecen las características técnicas del sistema. Por otra parte, la función objetivo de dicho problema de optimización corresponde a la minimización de los costos asociados a la operación de las unidades en el horizonte de tiempo evaluado. Posteriormente, se muestra una revisión del estado del arte presentando algunas de las principales técnicas utilizadas para resolver este tipo de problema: Lista de Prioridad, Programación Dinámica, Unit Decommitment, RL, Método de Benders, B&B y Algoritmos Genéticos. Para realizar la evaluación sobre los algoritmos de RL y B&B, se realizan programas en Matlab de dichos métodos con el objeto de realizar pruebas que permitan efectuar un análisis comparativo de los rendimientos de ambos algoritmos. Se aplican dichos programas para resolver problemas de predespacho en un modelo reducido del SING. De esta forma se puede observar el rendimiento de cada algoritmo respecto de su capacidad de obtener soluciones factibles, calidad de las soluciones, uso de heurística para generar soluciones y tiempos de ejecución requeridos. Adicionalmente, se puede estudiar la flexibilidad de ambos algoritmos para considerar restricciones de mayor complejidad y sus limitaciones para resolver predespacho en sistemas de dimensiones reales. Se concluye que el algoritmo que presenta un rendimiento que permite resolver de manera más eficiente el problema de predespacho en el SING corresponde al algoritmo RL, lo anterior debido principalmente a los tiempos de ejecución requeridos para su aplicación en sistemas de dimensiones reales y a que las soluciones generadas presentan una precisión del orden del 99% respecto a las soluciones generadas por el otro algoritmo. Adicionalmente, se puede acotar que las actuales políticas de operación aplicadas en el SING no representan una gran complejidad de programación y por lo tanto, la heurística requerida no presenta una complejidad adicional.

Les algorithmes Branch-and-Bound (B&B) font partie des méthodes exactes pour la résolution de problèmes d’optimisation combinatoire. Les calculs induits par un algorithme B&B sont extrêmement couteux surtout lorsque des instances de grande tailles sont considérées. Un algorithme B&B peut être vu comme une exploration implicite d’un espace représenté sous la forme d’un arbre qui a pour spécificité d’être hautement irrégulier. Pour accélérer l’exploration de cet espace, les calculs parallèles et distribués à très large échelle sont souvent utilisés. Cependant, atteindre des performances parallèles optimales est un objectif difficile et jalonné de plusieurs défis, qui découlent essentiellement de deux facteurs: (i) l’irrégularité des calculs inhérents à l’arbre B&B et (ii) l’hétérogénéité inhérente aux environnements de calcul large échelle. Dans cette thèse, nous nous intéressons spécifiquement à la résolution de ces deux défis. Nous nous concentrons sur la conception d’algorithmes distribués pour l’équilibrage de charge afin de garantir qu’aucune entité de calcul n’est surchargée ou sous-utilisée. Nous montrons comment résoudre l’irrégularité des calculs sur différents type d’environnements, et nous comparons les approches proposées par rapport aux approches de références existantes. En particulier, nous proposons un ensemble de protocoles spécifiques à des contextes homogènes, hétérogène en terme de puissance de calcul (muti-coeurs, CPU et GPU), et hétérogènes en terme de qualité des lien réseaux. Nous montrons à chaque fois la supériorité de nos protocoles à travers des études expérimentales extensives et rigoureuses. / Branch and Bound (B&B) algorithms are exact methods used to solve combinatorial optimization problems (COPs). The computation process of B&B is extremely time-intensive when solving large problem instances since the algorithm must explore a very large space which can be viewed as a highly irregular tree. Consequently, B&B algorithms are usually parallelized on large scale distributed computing environments in order to speedup their execution time. Large scale distributed computing environments, such as Grids and Clouds, can provide a huge amount of computing resources so that very large B&B instances can be tackled. However achieving high performance is very challenging mainly because of (i) the irregular characteristics of B&B workload and (ii) the heterogeneity exposed by large scale computing environments. This thesis addresses and deals with the above issues in order to design high performance parallel B&B on large scale heterogeneous computing environments. We focus on dynamic load balancing techniques which are to guarantee that no computing resources are underloaded or overloaded during execution time. We also show how to tackle the irregularity of B&B while running on different computing environments, and consider to compare our proposed solutions with the state-of-the-art algorithms. In particular, we propose several dynamic load balancing algorithms for homogeneous, node-heterogeneous and link-heterogeneous computing platforms. In each context, our approach is shown to perform much better than the state-of-the-art approaches.