No description available.

No description available.

The purpose of this thesis is to develop a heuristic solution for the static problem of resequencing unblocked vehicles as a part of an ongoing research project at Daimler AG. The target client of this project is Mercedes-Benz Cars. An unblocked vehicle is defined as a vehicle that for some reason could not be processed in its given time slot but at a later point in time needs to be inserted into the production sequence. Work overload is defined as work that the worker is unable to finish prior to reaching the station border. The resequencing problem can be described as finding new positions for a set of unblocked vehicles in a sequence of previously not blocked vehicles, such that the new sequence containing the previously not blocked vehicles and the additional unblocked vehicles causes as little work overload as possible. A decision has to be made in real-time, forcing the solution method to return a solution within a cycle time. Today, Mercedes-Benz Cars uses the sequencing approach “car sequencing”. This approach relies on so called spacing constraints, which basically means, trying to distribute work intensive vehicles as evenly as possible over the planning horizon and thereby enabling a hopefully smooth production. The car sequencing approach needs limited information. The difficulty is to find spacing constraints that fits the high level of product customization characterizing a modern car manufacturer. To overcome these difficulties, a new approach is being considered, namely the mixed-model sequencing, which takes more detailed data into account than the car sequencing approach but on the other hand is more costly in terms of computation. To this end, a simple but promising tabu search scheme was developed, that for many instances was able to find the optimal solution in less than 30 seconds of computing time and that also clearly outperformed all benchmark heuristics.

El presente trabajo de título tuvo como objetivo el diseño, desarrollo y evaluación de una herramienta que permitiera apoyar la toma de decisiones respecto de la programación de operaciones en cada una de las dos plantas con que actualmente cuenta una compañía siderúrgica. Se buscó de esta forma encontrar la secuencia en que debieran ejecutarse los distintos trabajos mensuales, minimizando los tiempos de producción así como los tiempos de retrasos en las fechas de entrega. La investigación se centró, por razones de tiempo, únicamente en el proceso de laminación de la compañía, que es aquel en donde se le da la forma final a los productos siderúrgicos mediante deformación termomecánica. Esta elección no fue al azar y se tomó considerando el hecho de que dicho proceso es hasta el día de hoy el principal “cuello de botella” y por lo tanto representaba las mayores oportunidades de ganancia. Ahora bien, fue posible demostrar que el problema pertenece a la clase NP-Hard por lo que no se conocen algoritmos capaces de resolverlo en un tiempo polinomial. Como consecuencia, y dado que el tamaño de la instancia es relativamente grande, se hizo necesario incorporar enfoques heurísticos que permitieran obtener resultados suficientemente buenos en un tiempo de computación razonable. Es así como se optó por un algortimo de Búsqueda Tabú. La elección se basó principalmente en los buenos resultados reportados en la literatura para otros problemas de programación de operaciones (Lin y Ying, 2006; Gupta y Smith, 2007 y Valente y Alves, 2008). Gran parte del desempeño de este tipo de heurística depende de dos elementos: la solución inicial y la metodología de generación de vecindades. Es por ello que la estrategia seguida consistió en evaluar un amplio espectro de las técnicas más utilizadas para tales fines, escogiendo finalmente aquella combinación que presentó un mejor desempeño. Los resultados obtenidos muestran que la aplicación de la heurística propuesta a instancias reales permite obtener reducciones importantes en comparación a la situación actual: un 7% promedio en los tiempos de producción y disminuciones promedio del 35% en lo que se refiere a los tiempos de retraso. Por otra parte, se observa una dramática caída del 82% promedio en lo que al tiempo necesario para determinar la programación respecta. Finalmente, cabe destacar que la investigación realizada sugiere también que aún hay espacio para futuras mejoras, por lo que se recomienda dar continuidad al estudio y en lo posible ampliarlo a otros procesos de la cadena productiva.

In this thesis there is a set of waste disposal facilities, a set of customers at which waste is collected and an unlimited number of homogeneous vehicles based at a single depot. Empty vehicles leave the depot and collect waste from customers, emptying themselves at the waste disposal facilities as and when necessary. Vehicles return to the depot empty. We take into consideration time windows associated with customers, disposal facilities and the depot. We also have a driver rest period. The problem is solved heuristically. A neighbour set is defined for each customer as the set of customers that are close, but with compatible time windows. This thesis uses six different procedures to obtain initial solutions for the problem. Then, the initial solutions from these procedures are improved in terms of the distance travelled using our phase 1 and phase 2 procedures, whereas we reduce the number of vehicles used using our vehicle reduction (VR) procedure. In a further attempt to improve the solutions three metaheuristic algorithms are presented, namely tabu search (TS), variable neighbourhood search (VNS) and variable neighbourhood tabu search (VNTS). Moreover, we present a modified disposal facility positioning (DFP), reverse order and change tracking procedures. Using all these procedures presented in the thesis, four solution procedures are reported for the two benchmark problem sets, namely waste collection vehicle routing problems with time windows (VRPTW) and multi-depot vehicle routing problem with inter-depot routes (MDVRPI). Our solutions for the waste collection VRPTW problems are compared with the solutions from Kim et al (2006), and our solutions for the MDVRPI problems are compared with Crevier et al (2007). Computational results for the waste collection VRPTW problems indicate that our algorithms produce better quality solutions than Kim et al (2006) in terms of both distance travelled and number of vehicles used. However for the MDVRPI problems, solutions from Crevier et al (2007) outperform our solutions.

This study aims to answer whether a heuristic that trades cycles between the tours in a solution would show good results when trying to solve the Weighted k-Chinese Postman Problem for undirected graphs, of varying size, representing neighbourhoods in Sweden.A tabu search heuristic was implemented with each iteration consisting of giving a cycle from the most expensive tour to the cheapest. The heuristic performed increasingly well for graphs of increasing size, although the solution quality decreased when increasing the number of tours to be used in the solution. It is suspected that the cause for this behavior is due to the heuristic only giving cycles from the most expensive tour, not considering trading cycles from other tours in the solution. It is believed that a heuristic considering more than only the most expensive tour when trading cycles would produce even better solutions.

Portfolio selection is an example of decision making under conditions of uncertainty. In the face of an unknown future, fund managers make complex financial choices based on the investors perceptions and preferences towards risk and return. Since the seminal work of Markowitz, many studies have been published using his mean-variance (MV) model as a basis. These mathematical models of investor attitudes and asset return dynamics aid in the portfolio selection process. In this thesis we extend the MV model to include the cardinality constraints which limit the number of assets held in the portfolio and bounds on the proportion of an asset held (if any is held). We present our formulation based on the Markowitz MV model for rebalancing an existing portfolio subject to both fixed and variable transaction cost (the fee associated with trading). We determine and demonstrate the differences that arise in the shape of the trading portfolio and efficient frontiers when subject to non-cardinality and cardinality constrained transaction cost models. We apply our flexible heuristic algorithms of genetic algorithm, tabu search and simulated annealing to both the cardinality constrained and transaction cost models to solve problems using data from seven real world market indices. We show that by incorporating optimization into the generation of valid portfolios leads to good quality solutions in acceptable computational time. We illustrate this on problems from literature as well as on our own larger data sets.

In this thesis we have presented a mathematical model of a scheduling problem which arises in the Brewing Industry. We have implemented two different types of global optimization algorithms to find the global minimum of the problem. Several instances of the scheduling problem are considered and the results thereof are presented. The results show that significant savings can be made if the global optimization techniques are used in brewery Industry.

The object of Master Thesis is the creation and research optimization of blank realization procedures. Four main parts comprise the thesis: analysis of the problem, theoretical solutions, research and outcomes, conclusions and recommendations. Optimization methods, their advantages and limitations have been analyzed in the first part. The most appropriate optimization method for problem solving was selected. Designed optimization methods have been presented in the theoretical solutions part: exhaustive search, tabu search and a new one, presented by the author. A program was created for comparison of these methods. In the third part of the thesis outcomes of the research are presented. Designed methods were tested and compared by their routes length, process time, computations duration and other parameters. Conclusions of the thesis and recommendations for implementation of analyzed procedures have been presented in the part of conclusions. Literature in Lithuanian, English was used in preparing the thesis. There are 19 tables and 29 pictures in the thesis.

It is a well-known fact that project activities are subject to considerable uncertainty, which may lead to multiple schedule disruptions during project execution. As a result, the random nature of activity durations has been the subject of numerous research efforts since the introduction of the initial PERT. A common problem which arises in project management is the fact that the planned schedule is often disrupted by several uncontrollable factors like weather conditions, other environmental factors, additional time that might be required for rework and correction of detected defects. As a result, project managers are often unable to meet the promised completion dates. It is therefore vital to take into account such possible disruptions and their potential negative consequences at the project schedule design stage. Hence, the ability of the pre-schedule to absorb disruptions may be very important in such settings. At this point two new criteria are used in modern scheduling literature: &quot / robustness&quot / and &quot / stability&quot / . In this thesis, we propose several stability measures. These measures are embedded in a tabu search algorithm to generate stable schedules in a multi resource environment subject to random disruptions.