In this work, we investigate job-shop problems where limited capacity buffers to store jobs in non-processing periods are present. In such a problem setting, after finishing processing on a machine, a job either directly has to be processed on the following machine or it has to be stored in a prespecified buffer. If the buffer is completely occupied the job may wait on its current machine but blocks this machine for other jobs. Besides a general buffer model,also specific configurations are considered.The key issue to develop fast heuristics for the job-shop problem with buffers is to find a compact representation of solutions. In contrast to the classical job-shop problem,where a solution may be given by the sequences of the jobs on the machines, now also the buffers have to be incorporated in the solution representation. In this work, we propose two solution representations for the job-shop problem with buffers. Furthermore, we investigate whether the given solution representations can be simplified for specific buffer configurations. For the general buffer configuration it is shown that an incorporation of the buffers in the solution representation is necessary, whereas for specific buffer configurations possible simplifications are presented. Based on the given solution representations we develop local search heuristics in the second part of this work. Therefore, the well-known block approach for the classical job-shop problem is generalized to the job-shop problem with specific buffer configurations.

This thesis deals with the problem of vehicle scheduling in public transport. It contains a theoretical introduction to vehicles scheduling and evolutionary algorithms. Vehicle scheduling is analyzed with respect to the bus timetables. Analysis of evolutionary algorithms is done with emphasis on the genetic algorithms and tabu-search method After the theoretical introduction, a memetic algorithm for the given problem is analyzed. Finally, the thesis contains a description of the optimization system implementation and discusses the experiments with the system.

No description available.

No description available.

The purpose of a cost model is to provide designers and decision-makers with accurate cost information to assess and compare multiple alternatives for obtaining the optimal solution and controlling cost. The cost models developed in the design phases are the most important and the most difficult to develop. Therefore it is necessary to identify appropriate cost drivers and employ appropriate modeling techniques to accurately estimate cost for directing designers. The objective of this study is to provide higher predictive accuracy of cost estimation for directing designer in the early design phases of complex products. After a generic cost estimation model is presented and the existing methods for identification of cost drivers and different cost modeling techniques are reviewed, the dissertation first proposes new methodologies to identify and select the cost drivers: Causal-Associated (CA) method and Tabu-Stepwise selection approach. The CA method increases understanding and explanation of the cost analysis and helps avoid missing some cost drivers. The Tabu-Stepwise selection approach is used to select significant cost drivers and eliminate irrelevant cost drivers under nonlinear situation. A case study is created to illustrate their procedure and benefits. The test data show they can improve predictive capacity. Second, this dissertation introduces Tabu-SVR, a nonparametric approach based on support vector regression (SVR) for cost estimation for complex products in the early design phases. Tabu-SVR determines the parameters of SVR via a tabu search algorithm improved by the author. For verification and validation of performance on Tabu-SVR, the five common basic cost characteristics are summarized: accumulation, linear function, power function, step function, and exponential function. Based on these five characteristics and the Flight Optimization Systems (FLOPS) cost module (engine part), seven test data sets are generated to test Tabu-SVR and are used to compare it with other traditional methods (parametric modeling, neural networking and case-based reasoning). The results show Tabu-SVR significantly improves the performance compared to SVR based on empirical study. The radial basis function (RBF) kernel, which is much more robust, often has better performance over linear and polynomial kernel functions. Compared with other traditional cost estimating approaches, Tabu-SVR with RBF kernel function has strong predicable capability and is able to capture nonlinearities and discontinuities along with interactions among cost drivers. The third part of this dissertation focuses on semiparametric cost estimating approaches. Extensive studies are conducted on three semiparametric algorithms based on SVR. Three data sets are produced by combining the aforementioned five common basic cost characteristics. The experiments show Semiparametric Algorithm 1 is the best approach under most situations. It has better cost estimating accuracy over the pure nonparametric approach and the pure parametric approach. The model complexity influences the estimating accuracy for Semiparametric Algorithm 2 and Algorithm 3. If the inexact function forms are used as the parametric component of semiparametric algorithm, they often do not bring any improvement of cost estimating accuracy over the pure nonparametric approach and even worsen the performance. The last part of this dissertation introduces two existing methods for sensitivity analysis to improve the explanation capability of the cost estimating approach based on SVR. These methods are able to show the contribution of cost drivers, to determine the effect of cost drivers, to establish the profiles of cost drivers, and to conduct monotonic analysis. They finally can help designers make trade-off study and answer “what-i” questions. / Ph. D.

In this thesis we investigate the application of two heuristic methods, genetic algorithms and tabu/scatter search, to the optimisation of realistic portfolios. The model is based on the classical mean-variance approach, but enhanced with floor and ceiling constraints, cardinality constraints and nonlinear transaction costs which include a substantial illiquidity premium, and is then applied to a large I 00-stock portfolio. It is shown that genetic algorithms can optimise such portfolios effectively and within reasonable times, without extensive tailoring or fine-tuning of the algorithm. This approach is also flexible in not relying on any assumed or restrictive properties of the model and can easily cope with extensive modifications such as the addition of complex new constraints, discontinuous variables and changes in the objective function. The results indicate that that both floor and ceiling constraints have a substantial negative impact on portfolio performance and their necessity should be examined critically relative to their associated administration and monitoring costs. Another insight is that nonlinear transaction costs which are comparable in magnitude to forecast returns will tend to diversify portfolios; the effect of these costs on portfolio risk is, however, ambiguous, depending on the degree of diversification required for cost reduction. Generally, the number of assets in a portfolio invariably increases as a result of constraints, costs and their combination. The implementation of cardinality constraints is essential for finding the bestperforming portfolio. The ability of the heuristic method to deal with cardinality constraints is one of its most powerful features. / Decision Sciences / M. Sc. (Operations Research)

Thèse numérisée par la Division de la gestion de documents et des archives de l'Université de Montréal.

Mémoire numérisé par la Division de la gestion de documents et des archives de l'Université de Montréal.

The thesis deals with optimization problems which arise at distribution planning. These problems can often be easily formulated as integer programming problems, but rarely can be solved using mixed integer programming techniques. Therefore, it is necessary to study the efficiency of heuristic algorithms. The main focus of the thesis is on the vehicle routing problem with time windows. A tabu search algorithm for this problem was developed and implemented. It uses integer programming to solve the set partitioning problem in order to find optimal distribution of all customers into feasible routes found during the search. The results of the classical integer programming approach, basic insertion heuristic and presented tabu search algorithm are compared in a numerical study.

Route optimization aims to optimize routes for vehicles withregards to resource usage. Especially when the vehicle needsto visit multiple customers on the route, a route optimizationtool is beneficiary. The purpose of this study is to comparehuman experience with a route optimization program. This isdone by comparing how a truck driver makes his routes to theroute a GIS-tool has calculated and then see which of theroutes was shorter, measured in kilometers. The data for thisstudy was gathered from a big shipping company. In order toachieve the purpose of this study 10 routes were analysed bya GIS program called ArcGIS. The algorithm used by ArcGISin route optimization is tabu search, this type of program wasused because it is based on heuristic methods that is muchfaster than exact methods. Expert systems are based onknowledge from experts that have been accumulated duringmany years of experience. Providing recommendations basedon probability reasoning instead of absolute answer. Thesekind of systems is often used in GIS programs to improveresults and calculation time. The aim of this study wasanalyze if a optimization program finds a better route than theexpert. This study shows an improvement of 60% of theanalyzed routes. To verify the results of this study anhypothesis test was made which gave a level of significanceby more than 85 %. The routes were optimized to a certainextent even before the study was done due to the driveralready being familiar with the routes in question. Because ofthis the results of this study were lower compared to othersimilar studies. Another reason may be that the coordinatesgiven to us did not always correspond perfectly with actuallocation of the stops. / Ruttoptimering avser att optimera rutter för fordon medminsta möjliga resursåtgång. När fordonet ska besöka ettflertal givna platser är ett ruttoptimeringsverktyg förmånligtatt använda. Denna studie syftar till att jämföra den mänskligaerfarenheten mot ett ruttoptimeringsprogram. Detta har gjortsgenom att jämföra hur en lastbilschaufför har kört en rutt mothur ett GIS-verktyg räknat fram den optimerade färdvägen avsamma rutt. Sedan jämfördes om det fanns skillnader ochvilken av rutterna som var kortast, räknat i kilometer. Datahar hämtats från ett stort fraktföretag. För att nå syftet har 10rutter undersökts i programmet ArcGIS Online som använderalgoritmen tabusökning. En kommersiell beräkningsmetodhar använts då det bygger på heuristiska metoder som ärbetydligt snabbare än exakta metoder. Expertsystem byggerpå erfarenhet som experter har samlat på sig genom åren, deger rekommendationer baserade på sannolikhetsresonemangistället för definitiva svar, dessa system sätts ofta in i GIS för att förbättra resultat och beräkningstider i systemen. Studienresulterade i en förbättring på 60 % av rutterna. Målet meddenna undersökning var att visa om ett optimeringsprogramhittar en bättre rutt än experten. För att verifiera resultaten istudien gjordes en hypotesprövning vilket gav ensignifikansnivå på över 85%. Chauffören har kört dessa rutteri flera år vilket gör att rutterna är optimerade i en viss månredan innan studien gjordes. Det har inverkat på resultatetsom gett ett lågt medelvärde av den procentuella skillnaden,jämfört med tidigare undersökningar. En annan faktor kanvara att koordinaterna i datan från företaget inte helt stämdemed den verkliga placeringen av stoppen på rutterna.