The transportation cost of logs from forest to customers is a large part of the overall cost for the Swedish forestry industry. Finding good routes from harvesting points to saw and pulp mills is a complex task, where the total number of feasible routes is extremely high. In this thesis we present two methods for log truck scheduling. The first is to, from a given set of routes, find the most valuable subset that fulfils the customers demand. We use a model that is similar to the set partitioning problem and a method that is referred to as a composite pricing coupled with Branch and Bound. The composite pricing based method prices the routes (columns) and chooses the most valuable ones that are then added to the LP relaxation. Once an LP optimum is found, the Branch and Bound method is used to find an integer optimum solution. We have tested this on a case of realistic size. The second method is a tabu search heuristic. Here, the purpose is to create efficient and qualitative routes from a given number of trips (referred to as predefined trips). From a start solution tabu search systematically generates new solutions. This method was tested on a small problem and on a five times larger problem to study how the size of the problem affected the result. It was also tested and compared on two cases in which the backhauling possibilities (i.e. instead of traveling empty the truck picks up another load on the return trip) had and had not been studied. The composite pricing based method and the tabu search method proved to be very useful for this kind of scheduling.

Traffic planning in a modern congested society is an important and time consuming procedure. Finding fast algorithms for solving traffic problems is therefore of great interest for traffic planners allover the world. This thesis concerns solving the fixed demand traffic assignment problem (TAP) on a number of different transportation test networks. TAP is solved using the Frank-Wolfe algorithm and the shortest path problems that arise as subproblems to the Frank-Wolfe algorithm are solved using the network simplex algorithm. We evaluate how a number of existing pricing strategies to the network simplex algorithm performs with TAP. We also construct a new efficient pricing strategy, the Bucket Pricing Strategy, inspired by the heap implementation of Dijkstra's method for shortest path problems. This pricing strategy is, together with the actual use of the network simplex algorithm, the main result of the thesis and the pricing strategy is designed to take advantage of the special structure of TAP. In addition to performing tests on the conventional Frank-Wolfe algorithm, we also test how the different pricing strategies perform on Frank-Wolfe algorithms using conjugate and bi-conjugate search directions. These test results show that the updating shortest path calculations obtained by using the network simplex outperforms the non-updating Frank-Wolfe algorithms. Comparisons with Bar-Gera's OBA show that our implementation, especially together with the bucket pricing strategy, also outperforms this algorithm for relative gaps down to 10E-6.

<p>The BMW Group uses load units for the transportation of assembly parts from the suppliers to the plants and for the internal material flow. This thesis analyses the advantageousness of introducing a load unit with a new size. There are three reasons why the current choice of containers is not sufficient. Firstly, there is a certain range of assembly parts that does not fit very well into the existing standard load units. Secondly, the average measurements of the parts have grown in the last years and thirdly, several of the existing containers leave unused space in the transportation vehicles.</p><p>For this the relevant costs and other, more qualitative aspects like the placing at the assembly line are considered. A container size is identified that offers a significant savings potential. For this potential the handling and transportation costs are identified as the relevant leverages. These costs are found to depend mainly on the utilisation degree of the load units.</p><p>To calculate the different utilisation degrees, a packing-algorithm in form of a four-block heuristic is applied and its results are extrapolated on the basis of existing BMW packing information. Thus, several assembly parts are identified that fit better into the suggested load unit than in the existing ones. These results are assessed using BMW’s expense ratios for handling and transportation. 80 parts are determined for which the migration to the new size would result in savings of more than 5,000 EUR for each per year in Dingolfing. Together, these parts offer a savings potential of about 0.9 million Euro.</p>

<p>This thesis contributes to theoretical and quantitative aspects of machine scheduling. In fact, it is dedicated to the issue of scheduling n jobs on one single machine. The scope is limited to deterministic problems - i.e. those with all data available and known with certainty in advance - with tardiness involved objectives; hence, the common denominator of all problems addressed are jobs with a predetermined due date assigned to. A job is finished on time as long as it is completed before its due date, otherwise it is said to be tardy. Since the single machine utilized is assumed to be restricted to process at most one job at a time, the aim is to find a proper sequence - a schedule - of how to process the jobs in order to best fulfill a certain objective. The contribution of this thesis aims at giving a state of the art survey and detailed review of research effort considering the objectives "minimizing the number of tardy jobs" and "minimizing the weighted number of tardy jobs". Further, the objectives of "minimizing the total tardiness", "minimizing the total weighted tardiness" and "minimizing the maximum tardiness" are adumbrated but reduced to a rough overview of research effort made.</p>

<p>The main contributions in this thesis are advances in parametric programming. The thesis is divided into three parts; theoretical advances, application areas and constrained control allocation. The first part deals with continuity properties and the structure of solutions to convex parametric quadratic and linear programs. The second part focuses on applications of parametric quadratic and linear programming in control theory. The third part deals with constrained control allocation and how parametric programming can be used to obtain explicit solutions to this problem.</p>

The main contributions in this thesis are advances in parametric programming. The thesis is divided into three parts; theoretical advances, application areas and constrained control allocation. The first part deals with continuity properties and the structure of solutions to convex parametric quadratic and linear programs. The second part focuses on applications of parametric quadratic and linear programming in control theory. The third part deals with constrained control allocation and how parametric programming can be used to obtain explicit solutions to this problem.

This thesis contributes to theoretical and quantitative aspects of machine scheduling. In fact, it is dedicated to the issue of scheduling n jobs on one single machine. The scope is limited to deterministic problems - i.e. those with all data available and known with certainty in advance - with tardiness involved objectives; hence, the common denominator of all problems addressed are jobs with a predetermined due date assigned to. A job is finished on time as long as it is completed before its due date, otherwise it is said to be tardy. Since the single machine utilized is assumed to be restricted to process at most one job at a time, the aim is to find a proper sequence - a schedule - of how to process the jobs in order to best fulfill a certain objective. The contribution of this thesis aims at giving a state of the art survey and detailed review of research effort considering the objectives "minimizing the number of tardy jobs" and "minimizing the weighted number of tardy jobs". Further, the objectives of "minimizing the total tardiness", "minimizing the total weighted tardiness" and "minimizing the maximum tardiness" are adumbrated but reduced to a rough overview of research effort made.

This thesis studies the allocation of stock in a two-level inventory system with stochastic demand. The system consists of one central warehouse which supplies N non-identical retailers with one single product. Customer demand occurs solely at the retailers and follows independent Poisson processes. The purpose is to investigate the value of using a more advanced allocation policy than First Come-First Serve at the central warehouse. The focus is on evaluating how well the simple First Come-First Serve assumption works in a system where the warehouse has access to real-time point-of-sale data, and where shipments are time based and consolidated for all retailers. The considered allocation policy is a myopic policy where the solution to a minimization problem, formulated as a constrained newsvendor problem, determines how the warehouse allocates its stock to the retailers. The minimization problem is solved using (a heuristic method based on) Lagrangian relaxation, and simulation is used to evaluate the average inventory holding costs and backorder costs per time unit when using the considered policy. The simulation study shows that cost savings around 1-4 percent can be expected for most system configurations. However, there were cases where savings were as high as 5 percent, as well as cases where the policy performed worse than First Come-First Serve. The study also shows that the highest cost savings are found in systems with relatively low demand, few retailers, short transportation times and a short time interval between shipments.

Using mathematical models with the purpose to understand and store knowlegde about a system is not a new field in science with early contributions dated back to, e.g., Kepler’s laws of planetary motion. The aim is to obtain such a comprehensive predictive and quantitative knowledge about a phenomenon so that mathematical expressions or models can be used to forecast every relevant detail about that phenomenon. Such models can be used for reducing pollutions from car engines; prevent aviation incidents; or developing new therapeutic drugs. Models used to forecast, or predict, the behavior of a system are refered to predictive models. For such, the estimation problem aims to find one model and is well known and can be handeled by using standard methods for global nonlinear optimization. Descriptive models are used to obtain and store quantitative knowledge of system. Estimation of descriptive models has not been much described by the literature so far; instead the methods used for predictive models have beed applied. Rather than finding one particular model, the parameter estimation for descriptive models aims to find every model that contains descriptive information about the system. Thus, the parameter estimation problem for descriptive models can not be stated as a standard optimization problem. The main objective for this thesis is to propose methods for estimation of descriptive models. This is made by using methods for nonlinear optimization including both new and existing theory.

QC 20100505