La asignación de los conductores es la cuarta y última fase de las cuatro etapas en que se suele dividir el complejo problema de la organización de servicios en una empresa de transporte terrestre regular.Se encuadra dentro de lo que se conoce como problema de rostering ya que se concreta en la elaboración de turnos de trabajo rotativo.Así como las tres etapas que preceden al rostering son problemas ampliamente estudiados y mecanizados en la mayor parte de las grandes compañías de trasporte, el problema de rostering plantea peculiaridades debidas a los usos de cada país y a los convenios laborales de cada empresa que hace prácticamente imposible una solución universal.La tesis presenta un acercamiento a los requisitos impuestos en algunas de las principales compañías españolas y ratifica este hecho mediante la constatación de que existen restricciones no sólo distintas sino contradictorias entre compañías.En muchos casos las restricciones impuestas son fruto de unos derechos adquiridos históricamente y en consecuencia difíciles de cambiar, cabe no obstante preguntarse si es posible mejorar la asignación que se está haciendo actualmente sin violar ninguno de los requisitos impuestos. Como respuesta, el presente trabajo plantea el cómo mejorar una situación concreta, para ello elabora un procedimiento que apoyado en técnicas de programación lineal y una heurística greedy mejora la actual asignación notablemente.Por último plantea un problema genérico donde sólo se imponen criterios de equidad en el sentido de tratar de buscar aquellas soluciones que mejor repartan la carga de trabajo y los días libres. Para resolverlo aporta un nuevo procedimiento que se divide en dos fases: construcción de patrones y construcción de listas de tareas.En la construcción de los patrones se exige que estos sean de ciclo corto, lo cual lleva a la innovación de un procedimiento que concretado en dos estrategias alternativas modifica de forma dinámica un programa lineal entero y va presentando las distintas soluciones o patrones de ciclo corto que cubren perfectamente la demanda de conductores solicitada.La elaboración de listas de tareas se aborda y resuelve satisfactoriamente mediante una heurística GRASP, la cual plantea una secuencia de programas lineales mixtos que dan la cota inferior de las asignaciones planteadas, con dicha información se van construyendo las distintas soluciones a partir de las cuales, posteriormente se lleva a cabo la búsqueda local.Se han procesado ejemplos con datos reales facilitados por algunas compañías y los resultados obtenidos reducen espectacularmente el desequilibrio observado en la carga laboral actual entre conductores. / The complex problem of assigning duties to public transport drivers is the fourth and last phase in which the problem is usually divided.It is a scheduling problem well known in the business world, due to the fact that crews work in rotating shifts.The three phases that precede the above mentioned problem are widely studied and mechanized by the majority of the large transport companies. However, the rostering problem is complicated by each country's use of this phase and to the labour agreements of each company. It makes a universal solution practically impossible.This thesis presents an approach to the requirements imposed by some of the main Spanish companies. It confirms this fact by establishing that distinct and contradictory restrictions exist among companies.In many cases the imposed restrictions are the result of historically acquired rights and are difficult to change. Nevertheless, it is feasible to improve the assignment without violating any of the imposed requirements. In short the present thesis raises the question of how to improve the situation. It details a procedure that is supported in lineal programming techniques and a greedy heuristic.Finally the thesis presents a general problem where only criteria of equity are imposed in the sense of seeking solutions that better distribute the workload and the days-off. Seeking to solve the problem has led to a new procedure that is divided into two phases: constructions of patterns and roster construction.The construction of the patterns requires short cycles, leading to an innovation that summarizes two alternative strategies that dynamically modify an Integer lineal program and displays the different solutions, or short cycle patterns that cover perfectly the drivers' demands.The roster elaboration is approached and solved satisfactorily by means of a GRASP algorithm, which raises a mixed lineal programs sequence that give the lower band of the assignments presented. With this information one arrives at different solutions from which the local search is carried out.Examples with real data have been processed, the data coming from existing companies. The results spectacularly reduce the differences observed in the present driver workload distribution.

En aquesta tesi, presentem una solució per a dos problemes rellevants en la teoria de control: el problema del cost quadràtic garantit i el problema del control H∞, per a un cert tipus de sistemes. Considerem els sistemes interconnectats lineals amb incerteses, sota la presència de fallades en els actuadors, i dissenyem controls descentralitzats que a més a més d'assegurar estabilitat, resolen aquests dos problemes. Treballem amb tres models diferents d'incerteses: incerteses normades o acotades, incerteses definides sobre un politop i incerteses que segueixen el model multiconvex. El model de fiabilitat emprat permet plantejar-se tant una fallada total en l'actuador com una fallada parcial. Els dos problemes tractats són:· Problema del control RGC. Sintetitzar el control fiable sota fallada en els actuadors, que assegura estabilitat i garanteix un cert nivell de rendiment o de cost, calculant una cota mínima per a la funció de cost.· Problema del control robust. Dissenyar el control que assegura estabilitat interna sota pertorbacions en el sistema, obtenint una cota per a la relació entre la pertorbació i la sortida controlable. Es considera la norma H∞ del sistema, que representa l'increment màxim en energia, entre l'entrada i la sortida del sistema..A l'hora de dissenyar ambdos controls, utilitzem les tècniques donades per les inequacions lineals matricials (LMI), que permeten una fàcil implementació numèrica. Així doncs, a part de tractar els problemes de la llei RGC i del control robust, hem determinat una relació general entre inequacions matricials lineals i no lineals, que permet obtenir caracteritzacions LMI per a un gran ventall de problemes de teoria de control. Les LMI que hem obtingut separen les dades del problema i les variables de disseny, permetent una resolució menys restrictiva. En particular, faciliten l'ús de funcions de Lyapunov paramètriques que asseguren l'estabilitat del sistema quan una funció no paramètrica no arriba a fer-ho. La formulació per mitjà de les tècniques LMI ens ha permès obtenir implementacions numèriques efectives, així com relaxacions en les condicions d'estabilitat. En el cas del problema del control RGC, trobem que quan es consideren fallades en el sistema, el model d'incerteses es veu reduït en certa manera, perdent també llibertat en la definició de la funció de cost. Un cop sintetitzat el control RGC, presentem dues maneres que permeten obtenir una cota òptima del cost garantit, així com treure'n la dependència respecte les condicions inicials. Hem dut a terme exemples numèrics que mostren l'eficiència dels mètodes enunciats, tractant els models d'incerteses normat i politòpic. Els resultats s'han obtingut usant el Toolbox LMI Control del programa Matlab.El segon problema que ens plantejem és el del control estàtic realimentat per l'estat, tal que la norma H∞ del sistema es troba acotada. Aquest fet assegura que l'efecte de pertorbacions en el sistema està dins de marges desitjats. A més a més, la síntesi obtinguda és independent del model de incerteses i, en el cas dels models normat i politòpic, hem obtingut una caracterització LMI. També fem un breu estudi del control robust realimentat per la sortida, obtenint una caracterització en termes LMI, en el cas que no se suposin errors en la medició de la sortida. / This thesis presents a design of a reliable decentralized state feedback control for a class of uncertain interconnected systems. We present a solution for two outstanding problems in the control theory: the problem of the guaranteed quadratic cost control and the H∞ problem. We have designed decentralized controls that besides assuring stability, they solve these two problems. We have considered three uncertainty models: born-normed model, polytopic model and multiconvex model. A model of failures in actuators is adopted which considers outages or partial degradation in independent actuators. The two treated problems are: · RGC Control. This problem is related to the decentralized reliable guaranteed cost control problem for interconnected systems. The presented reliable control shows that the admission of control failures imposes some restriction in the control weighting matrices in the performance criterion. Thus the designer can take some trade-off between control performance and admitted reliability.· Robust Control. The control problem considered is to design feedback controller, such that the closed loop structure is stable and has a specified performance. In the standard H problem, stability means internal stability and the performance is taken to be the H norm of the transfer function from the exogenous inputs and the regulators outputs. An estimation of worst-case H norm is required. A key point in the control design has been the formulation of a new linear matrix inequality (LMI) characterization, which uses parameter-dependent Lyapunov functions and slack variables. The obtained LMI separate the unknown variables from the system parameter data, which smoothes the numerical solution. This characterization can be useful for different classes of problems, such as guaranteed cost control, H2 or H∞ control design.We use this type of LMI to proof that the proposed decentralized control scheme guarantees the quadratic stability and a cost bound, for RGC control problem, and a H∞ norm bound for a robust control problem, for a class of failure model which considers outage or partial degradation of any independent specific actuator. We make this for the three uncertainties models. A numerical example has been included to illustrate the proposed decentralized control approach. Computations have been made by using standard Matlab's LMI Control Toolbox.

The most common decisions to be taken in the design of logistic systems are related to the location of facilities and the management of vehicle fleets.In this thesis, we study three of the optimization problems arising around this kind of decisions; namely the LRP, the SGAP and the SLRP. The first problem analyzed in this work is a capacitated LRP with one single uncapacitated vehicle at each open plant. To model this problem we resort to an auxiliary network that allows us to represent feasible solutions as families of paths satisfying a series of side constraints.The solutions of a reinforced LP relaxation of this model are used as the basis of a rounding heuristic designed to build feasible solutions of the problem. Those solutions are then improved with a TS heuristic.Two lower bounds, distinct from that obtained with the LP relaxation of the model, are proposed for this problem. The first one is obtained by bound ing separately the two different parts of the cost of any feasible solution, namely the fixed costs for opening plants and the route costs. The second lower bound is the result of applying CG to the Lagrangian dual obtained by dualizing the assignment constraints. The pricing problem obtained from our formulation is an ESPPRC. The complexity of this problem, and the fact that optimality of the obtained solutions is not always necessary, have motivated us to develope a simple heuristic for it.The computational experiences show a very good behavior of the TS procedure both, for the computational effort required and the quality of the solutions. The first lower bound proposed gives satisfactory results in reasonable amounts of time. In the case of the CG approach, results are very encouraging. In some of the tested instances the program terminated because of the CPU time limit specification, before succeeding to find a valid lower bound.In those instances, the algorithm was always stalled in the exact resolution of an ESPPRC. The difficulties encountered to solve this problem represent a limitation of this approach and suggest the future study of alternative solution methods. In spite of this limitation, in a high proportion of the instances the algorithm succeeded, and the final gap between the upper and the lower bound was always 0. The success in these instances is partially due to the use of our heuristic to generate new columns whenever this is possible.The second problem studied in this thesis is a SGAP. In this assignment problem the jobs are interpreted as customers that can request a service with a given probability, and each agent can serve a limited number of customers. This uncertainty about the presence of each customer is represented by modelling the demands of the customers as Bernoulli distributed independent random variables. The problem consists of finding an a priori assignment of customers to agents. Once the actual requests for service are known, an adaptive action is taken to tackle violations of the capacity constraints. On the one hand, part of the customers assigned to overloaded agents can be reassigned. On the other hand, some of the service requests can be disregarded. Different penalties for reassignment and for unattended service requests are pre-specified. The problem is formulated as a recourse model, where the recourse function gives the expected penalties for reassignments and unattended service requests.Since this recourse function is defined as the expected value of an integer programming recourse model, it does not have the regularity properties characteristic of those defined by linear recourse models. To overcome the difficulties caused by this, we construct a convex approximation of the recourse function that is tight in all feasible points. Moreover, as illustrated in the computational experiences, the use of this approximation reduces the computational effort required to evaluate the recourse function is some orders of magnitude. The convex approximation of the recourse function allows us to adapt the well-known L-shaped method to our problem. Integrality of the first stage variables is tackled in three different ways, giving raise to three versions of the algorithm. The difference among them resides in the hierarchy between the branching and the addition of violated cuts. On the one hand, we present a version where cuts are only added when integer solutions are found. On the other hand, a version is proposed where branching is only performed when no more violated cuts can be identified. The remaining version is designed as a tradeoff of these two; at each node of the search tree, new optimality cuts are added, if needed, and branching is performed if the solution at hand is fractional. Computational experiences point out this last version as the best of the three, since the efforts devoted to obtain a rich approximation of the recourse function and to achieve integrality are more balanced.We have also derived both, lower and upper bounds for this specific SGAP. Upper bounds are obtained from three simple heuristics. All them are based on solving deterministic approximations of the SGAP and provide good quality solutions in small amounts of CPU time. A lower bound is derived from a family of linear stochastic subproblems. Althoug in some of the tested instances the gap between the bounds exceeded the 30%, in the general case we obtained small gaps.One of the heuristics was used in the exact algorithm to provide it with a good upper bound. The lower bound is also used in the three versions of the algorithm, as the basis of some of the optimality cuts and also to identify optimal solutions. The quality of these bounds is one of the factors that explain the success of the exact algorithm.The last problem studied in this thesis is a SLRP. The stochasticity considered here is of the same type as that considered for the SGAP. Again, customers may request a service with a given probability and this is modeled by introducing Bernoulli random variables to represent the demands. A two stage model is proposed for this problem. In a first stage, a set of plants to open has to be chosen together with a family of disjoint routes (one rooted at each open plant) that visit all the customers. In the second stage, once all the demands become available, the actual routes have to be designed. For plants whose number of service requests does not exceed the capacity, the actual route is derived from that designed a priori by skipping customers with no demand. When the requests for service allocated to a plant exceed its capacity, a subset of them is randomly chosen to be served, and they are visited in the order defined by the a priori route.Penalties are paid for the unattended service requests. The expected total cost of the actual routes and the expected penalties for unserviced customers are contained in the recourse function.We present a two phase heuristic to solve this problem. In the first phase, a series of subproblems are sequentially solved to build an initial solution. In the second phase, this solution is successively improved using LS. This improving phase requires a high number of evaluations of the recourse function. Although we have developed an analytical expression for this recourse function, the computational effort required for its evaluation is considerable due to its combinatorial nature. For this reason, we approximate it with a simpler auxiliary function that has allowed us to obtain solutions in small computational times.We also propose a lower bound obtained from bounding different parts of the objective function independently. Unfortunately, we only could find reasonable bounds for the sum of fixed costs for opening the plants plus the expected penalty paid for unserviced customers. Further research is intended to improve the bounding of the expected total cost of the routes.The evaluation of the quality of the solutions obtained with our heuristic is not easy due to the lack of a tight global lower bound. However, the partial bound on the costs relative to the plants allows to conclude that the heuristic makes in general a good choice of the set of plants. As for the allocation of customers to plants and the design of the routes we can only evaluate the evolution along the search. In the computational experiences reported it can be seen that this evolution is satisfactory.

Avui en dia la conversió DC-AC té una important aplicació pràctica en el camp dels sistemes de potència ininterrompuda (SPI). Els convertidors commutats bàsics (el buck, lineal, i el boost i el buck-boost, no lineals) presenten una estructura molt simple, i al llarg dels últims quinze anys s'ha estudiat la possibilitat d'usar-los en esquemes de conversió DC-AC. L'objectiu de la tesi és aconseguir que els convertidors DC-DC de potència bàsics puguin seguir referències alternes mitjançant el voltatge de sortida. També es desenvolupen esquemes robustos per tal d'eliminar l'efecte de possibles pertorbacions en la tasca de seguiment. Els modes de lliscament s'usen com a tècnica de control, i es presenten resultats de simulació.La tesi s'organitza en capítols. El primer i el segon contenen una introducció i una revisió de la literatura existent. Els continguts i distribució de la resta de capítols segueix a continuació. El capítol 3 tracta el seguiment exacte i asimptòtic d'una referència variable en el temps per part del voltatge de sortida d'un convertidor reductor, controlat indirectament via el corrent d'entrada. A partir de l'estudi del problema del seguiment en sistemes lineals amb guanys fixos -mitjançant la teoria de mòduls- s'obtenen restriccions sobre els possibles senyals a seguir. A més, es proporciona una estratègia de control lliscant per aconseguir el seguiment, consistent en un procediment per modificar una superfície de lliscament inicialment bona en tasques de regulació i una llei de control. Una adequada elecció de variables d'estat permet que les possibles pertorbacions de la resistència de càrrega satisfacin la condició de superposició. En el capítol 4 s'usa un procediment basat en inversió per aconseguir el seguiment exacte de referències periòdiques amb la resistència de càrrega dels convertidors no lineals boost i buck-boost. També s'obtenen condicions suficients per a possibles senyals a seguir. Es presenta també un marc general per a un tractament via inversió del problema de seguiment exacte en una certa classe de sistemes bilineals de segon ordre: aquells en els quals el problema d'inversió dóna lloc a una EDO del tipus Abel. El capítol 5 estudia l'ús del mètode de Galerkin -una generalització del mètode del Balanç Harmònic- en la solució aproximada del problema invers aparegut al capítol anterior, així com l'efecte que té la seva utilització en el control del sistema. Es demostra l'existència d'una successió de solucions aproximades de l'EDO que representa l'esmentat problema invers. També es prova que aquesta successió convergeix uniformement cap a la solució periòdica de l'EDO, i s'obté una cota d'error. La sortida del sistema presenta un comportament periòdic i asimptòticament estable quan es fa anar la successió d'aproximacions de Galerkin en el control del sistema. A l'hora, la successió de sortides periòdiques presenta convergència uniforme cap a la funció desitjada sota una hipòtesi raonable. També s'obtenen en aquest cas cotes d'error. En el capítol 6 s'aconsegueix seguiment asimptòtic aproximat per a convertidors no lineals bàsics que presenten pertorbacions de càrrega. Això es fa mitjançant un control adaptatiu que estima el paràmetre pertorbat i una aproximació de Galerkin de primer ordre que incorpora l'actualització on-line a una superfície de lliscament apropiada. El capítol 7 proposa exercir un control directe del voltatge de sortida en convertidors boost i buck-boost bidireccionals, tot aprofitant la robustesa davant pertorbacions externes que ofereix aquest tipus de control. Es segueixen referències periòdiques mentre el voltatge de sortida es regula independentment a un nivell prefixat. / Nowadays, DC-to-AC conversion has an important practical application in the field of uninterruptible power systems (UPS). Basic DC-to-DC switch mode power converters (the buck, which is linear, and the boost and buck-boost, which are nonlinears) possess a very simple structure, and during the last fifteen years the possibility of using them in DC-to-AC conversion schemes has been studied. The aim of this thesis is to achieve that the output voltage of the DC-to-DC buck, boost and buck-boost power converters can track periodic references. Robust schemes to eliminate disturbance effects in the tracking task are also developed. Sliding modes are used as the control technique, and the obtained results are validated by numeric simulation.The thesis is organized in chapters. The first and the second one contain an introduction and a review of the existing literature. The contents and contributions of the other chapters follow below. Chapter 3 deals with the exact and asymptotic tracking of a time varying reference by the load voltage of a step-down converter, indirectly controlled through the input current. Departing from the study of the tracking problem in linear systems with fixed gains with the aid of module theory, conditions over possible reference signals have been obtained. Moreover, a sliding mode strategy to achieve the control target, consisting in a procedure to modify a switching surface initially good for regulation tasks and a control law, is provided. An approppriate choice of state variables allows possible load perturbations to satisfy the matching condition. In chapter 4, an inversion-based indirect control is used to reach exact tracking of periodic references with the load resistance of nonminimum phase, nonlinear boost and buck-boost converters. Sufficient conditions for candidate references are also obtained. A general frame for an inversion-based treatment of the perfect tracking problem in a certain class of nonminimum phase, second order bilinear systems is proposed: those in which the inversion problem gives raise to an ODE of the Abel type. Chapter 5 studies the use of the Galerkin method -a generalization of the Harmonic Balance method- in the approximate solution of the inverse problem stated in the former chapter, as well as the effect of its use on the control of the system. The existence of a sequence of approximate solutions for the ODE that represents the quoted inverse problem is proved. This sequence is also proved to converge uniformly to the periodic solution of the ODE, and an error bound has been derived. The system output exhibits a periodic and asymptotically stable behavior when the indirect control using the sequence of Galerkin approximations is performed. In turn, the sequence of periodic outputs is shown to exhibit uniform convergence to the original target function under a reasonable hypothesis. Error bounds have also been obtained. In chapter 6, approximate asymptotic tracking is achieved for load perturbed, basic, nonlinear power converters. This is done by means of an adaptive control that estimates the perturbation parameter and a first order Galerkin approximation that incorporates the on-line updating into an appropriate sliding surface. Chapter 7 propounds to exert a direct control of the output voltage in bidirectional boost and buck-boost converters, thus taking advantage of the insensitiveness to external disturbances offered by this type of control. Periodic references are followed, while the unstable inductor current is independently regulated at a prescribed level.

La planificación de la producción en plantas de proceso discontinuo es uno de los problemas más complejos e importantes para una amplia variedad de procesos industriales. A pesar de esta importancia la planificación de la producción es habitualmente un proceso manual que puede conducir a un exceso de inventario, una utilización ineficiente del capital y aumento en costes de producción.Este problema ha sido el sujeto de un importante esfuerzo investigador en los últimos años, especialmente desde principios de los 80 hasta la actualidad, aunque la industria se ha mostrado interesada en el problema desde los años 40. Durante este tiempo se ha realizado mucha investigación al respecto, pero la naturaleza compleja de problema hace que todavía no exista una solución aceptada ampliamente en la industria.Esta tesis describe un entorno genérico para la planificación de la producción en plantas de proceso discontinuo. Se han desarrollado diferentes componentes: un modelo de datos, un modelo de temporización, estrategias de asignación y secuenciación y diferentes alternativas de optimización.Uno de los aspectos más importantes del entorno presentado es su modularidad. El hecho de dividir el problema de planificación de la producción en diferentes módulos que comparten un modelo de datos común facilita la reutilización y la adaptación a escenarios industriales de las diferentes técnicas desarrolladas escogiendo la mejor alternativa para cada uno de ellos.El modelo de información orientado a objetos que se presenta en esta tesis permite la organización sistemática de la información de planta, permitiendo una representación detallada de las restricciones presentes en la industria.Por otra parte, el modelo de temporización de operaciones (EON) desarrollado en la presente tesis es la capacidad de representar restricciones temporales complejas presentes en la industria utilizando componentes sencillos. Se ha desarrollado una metodología para generar modelos EON a partir del modelo de información utilizado incluyendo restricciones de depósitos y restricciones temporales entre operaciones. Adicionalmente, un método iterativo permite tener en cuenta otros recursos limitantes dependientes de calendario, como mano de obra, electricidad, etc.En relación a las decisiones de nivel superior, se han desarrollado también reglas de balance de materiales, asignación y secuenciación que permiten obtener de una forma rápida y sencilla planes factibles a partir de un conjunto de demandas. Estas reglas se pueden aplicar tanto a planes de producción vacíos en situaciones de puesta en marcha de la planta, como a planes parcialmente llenos con la información de lotes que se están ejecutando en planta, lo que permite la replanificación en linea en caso de ser necesario.También se han aplicado diferentes técnicas de optimización a fin de mejorar planes de producción. Se han probado tanto métodos heurísticos como modelización matemática.En lo referente a los métodos heurísticos, se ha desarrollado un nuevo método de optimización (MSES) que mejora algunos aspectos referentes al algoritmo estándar de recocido simulado. Los algoritmos genéticos han sido también objeto de estudio, incorporando un algoritmo que transforma los individuos infactibles en factibles. Todos estos métodos han sido adaptados al entorno desarrollado permitiendo cambios de secuencia y asignación.En lo que respecta a la modelización matemática, se ha desarrollado un nuevo modelo MILP basado en una extensión del EON introduciendo variables de decisión de secuencia y asignación así como restricciones asociadas a almacenamientos intermedios.El entorno desarrollado en esta tesis ha sido aplicado a diferentes entornos industriales, proporcionando una validación de las tecnologías y modelos desarrollados. En todos los casos estudiados se han podido obtener planes de producción que cumplen con las restricciones presentes en planta, lo que permite establecer la validez de las metodologías desarrolladas para la planificación de la producción en plantas químicas de proceso discontinuo. / The scheduling of batch processes is one of the most complex and important problems faced by a wide variety of processing industries. In spite of this importance, scheduling is often a manual procedure, which leads to operation characterized by high inventories, inefficient capital utilization and increased operation costs. There are also reported complains about the lack of powerful, easy-to-use, PC based tools able to solve detailed operational problems, as well as perform high level analysis across the supply chain.This problem has been the focus of an important amount of research work in the recent years, especially from the early 1980's to nowadays, although the industry has been interested in effective ways of solving the scheduling problem since the early 1940's. An extensive work has been done but the complex nature of the scheduling problem results on the lack of a unique solution widely accepted in the industry.This thesis describes a global generic framework for planning and scheduling of batch chemical plants. Different components have been studied: a data model, a timing model, heuristic sequencing and assignment strategies and optimization procedures.One of the strongest points of the framework presented is its modularity. The fact of having the different components of planning and scheduling as separate modules sharing a common data model allows an easy use and adaptation of different techniques that can help solving the scheduling and planning problem in specific cases. This modular approach has been useful when applying the techniques presented to industrial scenarios. Adaptation to specific scenarios choosing the best alternative for each one is not only possible but also easy.The key point for achieving this is to share the common data and timing model (the EON model). The extensible object oriented data model presented in this thesis allows an organized and systematic information management dealing with the detailed representation of batch processes in the chemical industry. The main strength of the EON model is the capability of representation of complex time constraints between operations in the same schedule using simple components. EON model is presented and developed in detail. A methodology for the representation of storage constraints as time constraints as EON constraints is also presented. An iterative procedure allows also to take into account of limited resources as manpower, electricity, etc.Dispatching-like rules have been developed for the calculation of the material balances, the unit assignment and the batch sequencing. The strength of this approach is based in the easy implementation and adaptation to a batch oriented framework. These rules can be applied to empty schedules or to schedules that already contain frozen batches, which represents the actual situation in the plant. This last aspect allows the use of this kind of rules when performing on-line scheduling.Different optimization techniques have been used in this thesis to solve the scheduling approach presented. Stochastic and mathematical methods have been used and tested.Regarding to the stochastic methods, a new optimization algorithm (MSES) has been introduced that improves the performance of the SA standard algorithm. A modified GA algorithm has also been proposed that transforms the infeasible sequences commonly generated into feasible ones. All the stochastic methods used were adapted to batch processing structures involving batch sequencing and rule driven unit assignment.Regarding to the mathematical approach, the mathematical formulation presented in the EON timing model has been extended by introducing sequence and assignment variables as well as storage constraints.The framework developed in this thesis has been successfully applied to different industrial scenarios that are shown. The proposed solutions have been able to represent all the complexity of the test cases studied providing a powerful tool for planning and scheduling of the different plants.

La implementació dels sistemes de transport intel·ligent (ITS) ha possibilitat disposar de gran quantitat de dades de trànsit en temps real, utilitzant les actuals infrastructures en la xarxa viària que ens permeten recollir informació on-line. Mesures de flux de trànsit, velocitats o ocupació proporcionats pels detectors son un exemple. Com utilitzar les dades de trànsit en temps real, així com les dades històriques, per realitzar una predicció a curt termini és encara un problema obert als investigadors. El problema de la predicció del trànsit a curt termini és determinar l'evolució del flux del trànsit o, de forma equivalent, l'estat de la xarxa. La possibilitat de realitzar una predicció dinàmica de l'estat de la xarxa és essencial per la gestió del trànsit i centres d'informació de trànsit, permetent l'aplicació de polítiques de control o gestió per prevenir les congestions, i evitar el problemes que es deriven quan aquesta congestió ja és present.Els sistemes avançats de gestió de trànsit (ATMS) i sistemes avançats d'informació de trànsit (ATIS) han de considerar en temps real períodes de temps on ni la demanda ni el flux de trànsit son constants ni homogenis. La demanda i el flux tenen un comportament dinàmic, és a dir, son dependents del temps. El concepte de gestió de trànsit, com es defineix en Barceló (1991), té un sentit més ampli que el clàssic concepte de control de trànsit, ja que realitza accions sobre el temps, incloent el control sobre l'espai, com per exemple la redistribució dels fluxos amb accions de "rerouting" proposant rutes alternatives. Com a conseqüència la gestió de trànsit requereix una modelització dinàmica que representi la variació del flux a través del temps. Totes les propostes de sistemes avançats de trànsit i sistemes de control basats en les tecnologies telemàtiques estan d'acord amb la importància de la predicció a curt termini de l'evolució del flux de trànsit, que és equivalent a tenir una predicció a curt termini de l'estat de la xarxa viària per gestionar correctament el trànsit, disseminació de la informació als usuaris, etc. Algunes arquitectures de sistemes han estat proposades i avaluades en projectes Europeus en els darrers anys. Malauradament els resultats obtinguts en aquests projectes no es poden extrapolar o aplicar a estructures urbanes complexes. Altres propostes més adequades a estructures més complexes han estat desenvolupades, com per exemple les referenciades en Cascetta (1993) i Barceló (1997), però aquests models no son massa apropiats en aplicacions totalment dinàmiques i això ens ha portat a explorar altres direccions per cercar un model de predicció adequat. Davant les prometedores capacitats de les xarxes neuronals com a eines útils en la predicció, (Baldi i Hornik, 1995), vàrem decidir explorar aquesta alternativa. Aquest plantejament, basat en l'obtenció de dades de detecció reals combinat amb les matrius OD històriques, determina la predicció a curt termini de la matriu OD, definida per períodes. Aquesta matriu obtinguda com a resultat, pot ser utilitzada com a dada d'entrada en el simulador microscòpic de trànsit i obtenir l'evolució dels fluxos de trànsit, i com a conseqüència, la predicció de l'estat de la xarxa.Considerant aquesta visió dinàmica de la demanda, podem considerar cada element de la matriu O/D com una sèrie temporal, i per tant la predicció d'una matriu OD consisteix en realitzar la predicció de cada component de la matriu, és a dir, la predicció simultània de diverses sèries temporals multivariants. Solucions a aquest problema basades en mètodes de predicció clàssics, com per exemple Box-Jenkins o filtres de Kalman, han estat proposat per diversos autors (Davis, 1993; Davis et al., 1994; Van der Ziipp i Hamerslag, 1996), i aquestes propostes donen bons resultats en infrastructures lineals, com podria ser el cas d'autopistes, però en el cas de xarxes amb una estructura més complexa, com podria ser un xarxa urbana, no està clar si proporcionen resultats acceptables, encara que en alguns del més prometedors casos, (Davis,1994), la càrrega computacional necessària posa en dubte el seu ús en aplicacions en temps real de xarxes d'una mida considerable, fent necessari la cerca d'altres mètodes.Les xarxes neuronals apareixen com a candidates naturals per un model de predicció, amb el valor afegit de la seva estructura fàcilment paral·lelitzable que en el cas d'un sistema en temps real és una característica a tenir en compte. Una altra raó per pensar en la utilització de les xarxes neuronals son els resultats reportats per en Chakraborty (1992) en l'anàlisi de sèries temporals multivariant utilitzant xarxes neuronals, o d'en Weigend (1992) en l'avaluació de les capacitats predictives comparades amb altres models clàssics.La predicció dinàmica de l'estat de la xarxa en termes de predicció de la matriu OD utilitzant Xarxes Neuronals té un inconvenient: la quantitat de dades necessàries per un correcte aprenentatge. El treball de recerca realitzat en aquesta tesis proposa solventar aquest desavantatge particionant la xarxa neuronal amb grups de parells OD "independents" segons la identificació de camins més utilitzats.La predicció a curt termini desemboca d'aquesta forma cap al crític problema de l'Assignació Dinàmica de Trànsit (DTA), que en aquesta tesis és resolta amb una heurística basada en la microsimulació. El treball de recerca planteja un dels aspectes més crítics de la simulació dinàmica de xarxes viàries, anomenat heurística d'assignació dinàmica, amb la consideració dels models de selecció de rutes, i la metodologia de la validació, un aspecte important per determinar el grau de validació i significació dels resultats de simulació. Aquest treball està estructurat en dues parts, la primera ens dóna una visió global de com les principals funcionalitats han estat implementades en el simulador microscòpic AIMSUN, (AIMSUN 2002), i una segona part dedicada a parlar en detall de la heurística dissenyada i determinar una guia en la calibració/validació dels seus paràmetres. Un cop el model de simulació està validat i calibrat, llavors és utilitzat per realitzar el DTA on els seus resultats ens permeten identificar els camins més utilitzats per llavors determinar la partició dels parells OD i així la definició de les xarxes neuronals per la realitzar la predicció. / The implementation of Intelligent Transport Systems (ITS) has made vast quantities of real-time traffic data available, by making use of current road network infrastructure that enables information to be gathered on-line. Detectors that measure traffic flow, speed and occupancy are an example. How to use real-time traffic data, as well as historical data, to provide short-term traffic prediction, remains an open problem for researchers. The problem of short-term traffic prediction involves determining the evolution of traffic flows or, equivalently, of the network state. The ability to predict the network state dynamically is essential in traffic management and for traffic information centres particularly, since it enables them to apply traffic control and traffic management policies to prevent traffic congestion rather than dealing with traffic problems after congestion has already occurred. Advanced traffic management systems (ATMS) and advanced traffic information systems (ATIS) must consider, in real time, short time intervals in which neither demand nor flows are constant and homogenous. Demand and flow behave dynamically, that is, they are both time-dependent. The concept of traffic management, as defined by Barceló (1991), is broader than the classic concept of traffic control, because it takes action over time, including control over space, such as, for instance, redistributing flows by rerouting, that is, by proposing alternatives routes. Therefore, traffic management applications require dynamic modelling that shows flow variation over time.All proposals for advanced traffic management and control systems that are based on telematic technologies agree on the importance of short-term prediction of traffic flow evolution, which is equivalent to the short-term prediction of the network state, for correct decision-making in traffic management, information dissemination to users, etc. Several system architectures have been proposed and evaluated in European projects in recent years. Although the achievements of these projects cannot be applied or extrapolated to complex urban structures, other models that are more suited to complex networks have been developed, by Cascetta (1993) and Barceló (1997), for example. Unfortunately, these models do not appear to be appropriate for full dynamic applications, and so we had to look elsewhere in our search for a suitable prediction model. The promising features of neural networks, which make them suitable for use as predictive tools (Baldi and Hornik, 1995), encouraged us to explore this approach. The approach, which is based on real-time detector measurements combined with historical OD matrices, involves determining a short-term forecast of a sliced OD matrix. The forecast OD matrix could be used as input for a microscopic traffic simulator such as AIMSUN; thus the evolution of traffic flows and, as a consequence, the forecast network state could be obtained.According to this dynamic vision of demand, we can consider each of the OD matrix's components as a time series. Therefore, forecasting an OD matrix consists in performing the forecast for each component in the matrix, that is, in simultaneously forecasting many multivariate time series. Solutions to this problem that are based on classic forecasting methods, such as Box-Jenkins or Kalman filtering, have been proposed by several authors (Davis, 1993; Davis et al., 1994; Van der Ziipp and Hamerslag, 1996). The approaches proposed provide relatively good results for linear infrastructures, such as motorways, although it remains unclear whether they would provide reliable results in the case of more complex networks, such as urban networks. In some of the most promising cases (Davis, 1994), however, the computational task required practically invalidates their use in real-time applications in large-scale networks and makes it advisable to look for other methods. Neural networks appear to be natural candidates for forecasting models, particularly if their easily parallelisable structure is taken into account, and high computational speed is required to achieve a system's objectives. Further reasons to consider a neural network approach are the results reported by Chakraborty (1992) for multivariate time series analysis using neural networks and by Weigend (1992) in his evaluation of their predictive capabilities compared to other classic models.The dynamic prediction of the network state in terms of the OD matrix by means of neural networks has one main drawback: the amount of data required for the proper training of the neural network. This thesis proposes solving this handicap by partitioning the neural network in terms of clusters of independent or almost independent OD pairs. This technique allows an original neural network of a large size to be split into a set of smaller neural networks that are easier to train. Before the clustering problem can be solved, however, the paths that are most likely to be used between each OD pair must be identified.Short-term forecasting leads, in this way, to the critical problem of dynamic traffic assignment, which is solved in this thesis by a microsimulation-based heuristic. In the thesis, some of the most critical aspects of the dynamic simulation of road networks are discussed, namely heuristic dynamic assignment, implied route choice models and the validation methodology, a key issue in determining the degree of validity and significance of the simulation results. The work is divided into two parts: the first provides an overview of how the main features of microscopic simulation were implemented in the microscopic simulator AIMSUN (AIMSUN 2002) and the second is a detailed discussion of heuristic dynamic assignment and sets guidelines for calibrating and validating dynamic traffic assignment parameters. The calibrated and validated simulation model is then used to conduct a dynamic traffic assignment, whose output identifies the paths that are most likely to be used, which will be clustered in subsets that connect the OD pairs and will define the neural networks for the forecast.

El problema de la rectificación AC/DC de la energía eléctrica con criterios de eficiencia de conversión de potencia, baja interferencia electromagnética, bajo contenido armónico en la corriente de línea, factor de potencia cercano a la unidad y regulación de tensión para cargas variables ha sido un tema de interés en los últimos años especialmente por la existencia de regulaciones estrictas sobre máximos permitidos en estas especificaciones.La necesidad de utilizar convertidores electrónicos conmutados en estos sistemas obliga al diseño de controladores para el logro de los objetivos deseados. Se han propuesto en la última década diversos esquemas y técnicas de control para sistemas de este tipo; siendo un requerimiento importante el que los esquemas y técnicas de control empleadas impliquen un bajo costo de implementación. Las implementaciones prácticas de estos controladores sin embargo, presentan algunos inconvenientes que se han reportado en la literatura y que animan a la búsqueda de otros esquemas y técnicas de control.En ésta tesis se presenta y valida mediante simulación y experimentación, un esquema de control para un rectificador AC/DC tipo boost de puente completo que ofrece la posibilidad de convertir el problema no estándar de control derivado de los objetivos en este sistema, en uno estándar de regulación que permite la utilización de técnicas de control lineales y no lineales simples y ampliamente conocidas. Esto se logra gracias a la utilización de una técnica de modelado promediado en el espacio de estados conocida como GSSA. Para la aplicación del esquema propuesto se requiere la construcción de filtros digitales que extraigan en tiempo real de los coeficientes complejos de Fourier para armónicos específicamente seleccionados de las señales. En esta tesis se diseñan filtros que satisfacen esta necesidad con un bajo costo computacional a fin de que la propuesta sea de complejidad similar a las técnicas convencionales.Bajo el esquema de control propuesto, se diseñan y validan algunos reguladores lineales y no lineales para el rectificador boost de puente completo cuyo objetivo es principal es mostrar que el esquema propuesto puede dar origen a la utilización de técnicas de control más simples diferentes a las utilizadas hasta ahora para este mismo problema. / The problem of power electric AC/DC rectification with power conversion efficiency, low electromagnetic interference, low harmonic content in the line current, closer to unity power factor, and voltage regulation for variable loads criteria, has been a topic of special interest in the last years due to the existence of strict regulations on the maximum allowed values for these specifications. The necessity to use electronic switching converters in these systems, forces to the design of controllers for the achievement of the desired objectives. In the last decade diverse schemes and control techniques for systems of this type have been proposed; being an important requirement the one that the used schemes and control techniques they imply a low implementation cost. Practical implementations of these controllers however, present some inconveniences that have been reported in the literature and that they encourage to the search of other schemes and control techniques. In this thesis a control scheme for a full-bridge type boost AC/DC rectifier is presented and validated by means of simulation and experimentation, which offers the possibility to transform the non-standard problem derived from the control objectives into this system, in one standard regulation problem, allowing the use of simpler and broadly well-known lineal and non-linear control techniques. This is achieved thanks to the use of a state space averaged modeling approach known as GSSA. For the application of the proposed scheme, the design of digital filters for the extraction in real time of the complex Fourier coefficients of specifically selected harmonics is required. In this thesis some of these filters satisfying this necessity are designed achieving a low computational cost so that the proposal has a complexity similar to that of the conventional techniques. Under the proposed control scheme some lineal and non-linear regulators for the full-bridge type boost rectifier are designed, being the main objective showing that the proposed scheme can give rise to the use of simpler control techniques different to the utilized ones before for this same problem.

En esta tesis se estudia de manera analítica y numérica el comportamiento del convertidor tipo buck cuando es manejado con PWM y el cálculo de ciclo de trabajo se hace obligando a la dinámica de primer orden en el error del sistema a tener promedio cero en cada iteración (ZAD). Esta técnica de manejo del PWM, reportada por primera vez en la literatura en el año 2001, y ampliamente estudiada en la presente tesis, promete llevar al sistema a tener características deseables tales como: frecuencia fija de conmutación, robustez y bajo error de salida; cualidades estas muy importantes en un convertidor. Los principales puntos de análisis en la presente tesis son: determinación del punto de equilibrio de la aplicación de Poincaré del convertidor manejado con PWM y ZAD. Cálculo de la estabilidad de la órbita de período 1 asociada a la aplicación de Poincaré. Este estudio se ha hecho via Exponentes de Lyapunov, Exponentes de Floquet y Multiplicadores característicos. Debido a la presencia inherente de un periodo de atraso en un esquema de PWM con pulso al centro, se incuye para el análisis de estabilidad este caso particular. También se hace un estudio de la transición al caos, basado en la aplicación de Poincaré y se caracterizan de manera analítica las tres primeras bifurcaciones (Flip-colisión de borde-Flip). Se muestra además la conformación del caos a tavés de una aplicación estilo tienda de campaña. Se ha diseñado un controlador para cuando el sistema opera en zona de caos y se ha comparado con la técnica TDAS, mostrando mayor velocidad de respuesta y error más bajo. Por medio de la aplicación de la teoría de promedios se calcula una cota para el error, cuando el sistema opera en zona estable y en estado estacionario, garantizando un bajo error de salida. Finalmente los resultados experimentales corroboran algunos fenómenos no lineales y el límite de la estabilidad. / In this thesis the behaviour of the buck converter, driven with PWM and Zero Average Dynamic on error (ZAD) technique is studied in an analytical and numerical form. This technique for evaluating duty cycle in a PWM was reported for the first time in the literature in the year 2001. ZAD is widely studied in this thesis. Its main characteristics are: fixed frequency switching, robustness, and low error in the regulation case. These characteristics are very important in power converters. The main issues of this thesis are: To calculate the equilibrium point associated to the buck converter Poincaré map. To determine the stability of the 1-periodic orbit, based on Lyapunov exponents, Floquet exponents and characteristic multipliers. Also an scheme of PWM with a delay time has been studied finding its stability limit. A study of transition to chaos has been made. It has confirmed analytically that the first bifurcation is flip type, the second bifurcation is corner collision type and third bifurcation is flip type, again. Also a controller for chaos is designed and tested and it has been compared with TDAS technique, showing lower error and very fast response. Applying Average theory, a bound for error in the regulation case and in stationary state has been found. This bound confirms the advantages of the ZAD technique. Finally the analytical and numerical results are confirmed in an experimental form.

This operations research thesis should be situated in the field of the power generation industry. The general objective of this work is to efficiently solve the Generalized Unit Commitment (GUC) problem by means of specialized software. The GUC problem generalizes the Unit Commitment (UC) problem by simultane-ously solving the associated Optimal Power Flow (OPF) problem. There are many approaches to solve the UC and OPF problems separately, but approaches to solve them jointly, i.e. to solve the GUC problem, are quite scarce. One of these GUC solving approaches is due to professors Batut and Renaud, whose methodology has been taken as a starting point for the methodology presented herein.This thesis report is structured as follows. Chapter 1 describes the state of the art of the UC and GUC problems. The formulation of the classical short-term power planning problems related to the GUC problem, namely the economic dispatching problem, the OPF problem, and the UC problem, are reviewed. Special attention is paid to the UC literature and to the traditional methods for solving the UC problem. In chapter 2 we extend the OPF model developed by professors Heredia and Nabona to obtain our GUC model. The variables used and the modelling of the thermal, hydraulic and transmission systems are introduced, as is the objective function. Chapter 3 deals with the Variable Duplication (VD) method, which is used to decompose the GUC problem as an alternative to the Classical Lagrangian Relaxation (CLR) method. Furthermore, in chapter 3 dual bounds provided by the VDmethod or by the CLR methods are theoretically compared.Throughout chapters 4, 5, and 6 our solution methodology, the Radar Multiplier (RM) method, is designed and tested. Three independent matters are studied: first, the auxiliary problem principle method, used by Batut and Renaud to treat the inseparable augmented Lagrangian, is compared with the block coordinate descent method from both theoretical and practical points of view. Second, the Radar Sub- gradient (RS) method, a new Lagrange multiplier updating method, is proposed and computationally compared with the classical subgradient method. And third, we study the local character of the optimizers computed by the Augmented Lagrangian Relaxation (ALR) method when solving the GUC problem. A heuristic to improve the local ALR optimizers is designed and tested.Chapter 7 is devoted to our computational implementation of the RM method, the MACH code. First, the design of MACH is reviewed brie y and then its performance is tested by solving real-life large-scale UC and GUC instances. Solutions computed using our VD formulation of the GUC problem are partially primal feasible since they do not necessarily fulfill the spinning reserve constraints. In chapter 8 we study how to modify this GUC formulation with the aim of obtaining full primal feasible solutions. A successful test based on a simple UC problem is reported. The conclusions, contributions of the thesis, and proposed further research can be found in chapter 9.

Esta Tesis esta motivada por el interés en aplicar procedimientos de optimización global a problemas del mundo real. Para ello, nos hemos centrado en el problema de Coordinación Hidrotérmica de la Generación Eléctrica a Corto Plazo (llamado Problema de Generación en esta Tesis) donde la función objetivo y las restricciones no lineales son polinomios de grado como máximo cuatro. En el Problema de Generación no tenemos disponible una representación en diferencia convexa de las funciones involucradas ni tampoco es posible utilizar la estructura del problema para simplificarlo. No obstante, cuando disponemos de una función continua f(x) definida en un conjunto cerrado y no vacío S el problema puede transformarse en otro equivalente expresado mediante minimize l(z) subject to z 2 D n int. (programa d.c. canónico), donde l(z) es una función convexa (en general suele ser una función lineal) con D y C conjuntos convexos y cerrados. Una estructura matemática tal como Dnint C no resulta siempre aparente y aunque lo fuera siempre queda por realizar una gran cantidad de cálculos para expresarla de manera que se pueda resolver el problema de una manera eficiente desde un punto de vista computacional.La característica más importante de esta estructura es que aparecen conjuntos convexos y complementarios de conjuntos convexos. Por este motivo en tales problemas se pueden usar herramientas analíticas tales como subdifernciales y hiperplanos soporte. Por otro lado, como aparecen conjuntos complementarios de conjuntos convexos, estas herramientas analíticas se deben usar de una manera determinada y combinándolas con herramientas combinatorias tales como cortes por planos, Branco and bound y aproximación interior.En esta tesis se pone de manifiesto la estructura matemática subyacente en el Problema de Generación utilizando el hecho de que los polinomios son expresables como diferencia de funciones convexas. Utilizando esta propiedad describimos el problema como un programa d.c. canónico equivalente. Pero aun mas, partiendo de la estructura de las funciones del Problema de Generación es posible rescribirlo de una manera mas conveniente y obtener de este modo ventajas numéricas desde elpunto de vista de la implementación.Basándonos en la propiedad de que los polinomios homogéneos de grado 1 son un conjunto de generadores del espacio vectorial de los polinomios homogéneos de grado m hemos desarrollamos los conceptos y propiedades necesarios que nos permiten expresar un polinomio cualquiera como diferencia de polinomios convexos, También, se ha desarrollado y demostrado la convergencia de un nuevo algoritmo de optimización global (llamado Algoritmo Adaptado) que permite resolver el Problema de Generación. Como el programa equivalente no esta acotado se ha introducido una técnica de subdivisión mediante prismas en lugar de la habitual subdivisión mediante conos.Para obtener una descomposición óptima de un polinomio en diferencia de polinomios convexos, se ha enunciado el Problema de Norma Mínima mediante la introducción del concepto de Descomposición con Mínima Desviación, con lo cual obtenemos implementaciones m´as eficientes, al reducir el n´umero de iteraciones del Algoritmo Adaptado. Para resolver el problema de Norma Mínima hemos implementado un algoritmo de programación cuadrática semi-infinita utilizando una estrategia de build-up and build-down, introducida por Den Hertog (1997) para resolver programas lineales semi-infinitos, la cual usa un procedimiento de barrera logarítmica.Finalmente, se describen los resultados obtenidos por la implementación de los algoritmos anteriormente mencionados y se dan las conclusiones. / This Thesis has been motivated by the interest in applying deterministic global optimization procedures to problems in the real world with no special structures. We have focused on the Short-Term Hydrothermal Coordination of Electricity Generation Problem (also named Generation Problem in this Thesis) where the objective function and the nonlinear constraints are polynomials of degree up to four. In the Generation Problem there is no available d.c. representation of the involved functions and we cannot take advantage of any special structure of the problem either. Hence, a very general problem, such as the above-mentioned, does not seem to have any mathematical structure conducive to computational implementations. Nevertheless, when f(x) is a continuous function and S is a nonempty closed set the problem can be transformed into an equivalent problem expressed by minimize l(z) subject to z 2 D n intC (canonical d.c. program), where l(z) is a convex function (which is usually a linear function) and D and C are closed convex sets. A mathematical complementary convex structure such as D n int C is not always apparent and even when it is explicit, a lot of work still remains to be done to bring it into a form amenable to efficient computational implementations. The attractive feature of the mathematicalcomplementary convex structure is that it involves convexity. Thus, we can use analytical tools from convex analysis like sub differential and supporting hyper plane.On the other hand, since convexity is involved in a reverse sense, these tools must be used in some specific way and combined with combinatorial tools like cutting planes, branch and bound and outer approximation.We introduce the common general mathematical complementary convex structure underlying in global optimization problems and describe the Generation Problem, whose functions are d.c. functions because they are polynomials. Thus, by using the properties of the d.c. functions, we describe the Generation Problem as an equivalent canonical d.c. programming problem. From the structure of its functions the Generation Problem can be rewritten as a more suitable equivalent reverse convex program in order to obtain an adaptation for advantageous numerical implementations.Concepts and properties are introduced which allow us to obtain an explicit representation of a polynomial as a deference of convex polynomials, based on the fact that the set of mth powers of homogeneous polynomials of degree 1 is a generating set for the vector space of homogeneous polynomials of degree m.We also describe a new global optimization algorithm (adapted algorithm) in order to solve the Generation Problem. Since the equivalent reverse convex program is unbounded we use prismatical subdivisions instead of conical ones. Moreover, we prove the convergence of the adapted algorithm by using a prismatical subdivision process together with an outer approximation procedure.We enounce the Minimal Norm Problem by using the concept of Least Deviation Decomposition in order to obtain the optimal d.c. representation of a polynomial function, which allows a more efficient implementation, by reducing the number of iterations of the adapted algorithm.A quadratic semi-infinite algorithm is described. We propose a build-up and down strategy, introduced by Den Hertog (1997) for standard linear programs that uses a logarithmic barrier method.Finally, computational results are given and conclusions are explained.