<p>This thesis presents a grey-box model of the temperature and moisture content for each layer of the multi-ply paperboard inside the drying section of a paper mill. The distribution of the moisture inside the board is an important variable for the board quality, but is unfortunately not measured on-line. The main goal of this work is a model that predicts the moisture evolution during the drying, to be used by operators and process engineers as an estimation of the unmeasurable variables inside the drying section.</p><p>Drying of carton board is a complex and nonlinear process. The physical phenomena are not entirely understood and the drying depends on a number of unknown parameters and unmodelled or unmeasurable features. The grey-box modelling approach, which consists in using the available measurements to estimate the unknown disturbances, is therefore a suitable approach for modelling the drying section.</p><p>A major problem encountered with the modelling of the drying section is the lack of measurements to validate the model. Consequently, the correctness and uniqueness of the estimated variables and parameters are not guaranteed. We therefore carry out observability and identifiability analyses and the results suggest that the selected model structure is observable and identifiable under the assumption that specific measurements are available. Based on this analysis, static measurements in the drying section are carried out to identify the parameters of the model. The parameters are identified using one data set and the results are validated with other data sets.</p><p>We finally simulate the model dynamics to investigate if predicting the final board properties on-line is feasible. Since only the final board temperature and moisture content are measured on-line, the variables and parameters are neither observable nor identifiable. We therefore regard the predictions as an approximation of the estimated variables. The semiphysical model is complemented with a nonlinear Kalman filter to estimate the unmeasured inputs and the unmodelled disturbances. Data simulations show a good prediction of the final board temperature and moisture content at the end of the drying section. The model could therefore possibly be used by operators and process engineers as an indicator of the board temperature and moisture inside the drying section.</p>

<p>The well-known Dijkstra's algorithm uses weights to determine the shortest path. The focus here is instead on the opposite problem, does there exist weights for a certain set of shortest paths? OSPF (Open Shortest Path First) is one of several possible protocols that determines how routers will send data in a network like the internet. Network operators would however like to have some control of how the traffic is routed, and being able to determine the weights, which would lead to the desired shortest paths to be used, would be a help in this task.The first part of this thesis is a mathematical explanation of the problem with a lot of examples to make it easier to understand. The focus here is on trying to combine several routing patterns into one, so that the result will be fewer, but more fully spanned, routing patterns, and it can e.g. be shown that there can't exist a common set of weights if two routing patterns can't be combined.The second part is a program that can be used to make several tests and changes to a set of routing patterns. It has a polynomial implementation of a function that can combine routing patterns. The examples that I used to combine routing patterns, showed that this will increase the likelihood of finding and significantly speed up the computation of a “valid cycle”.</p> / Egentligen 30p/45hp, men det fanns inte som alternativ.

QC 20101206

For workplaces with a preference or need for staffing around the clock, employees commonly work in shifts, which are work sessions that span different parts of the day. The scheduling of these shifts is a multi-objective optimization problem with both hard and soft constraints. The reduction in the available workforce when employees go on vacation makes the problem especially constrained. We describe a method that uses a genetic algorithm to generate shift schedules, for teams of employees and time periods with vacations. The method supports a staffing demand that can be met with one of multiple combinations of shifts. The genetic algorithm features specialized crossovers, together with a repair step aimed at maintaining staffing that fulfils the staffing requirements. A software implementation of the method is evaluated on three real-life problem instances. For two of them, it can produce schedules that are feasible, but subpar to those constructed manually by an experienced personnel scheduling professional. Several ideas to improve the program are presented.

Genomförandet av en sårbarhetsanalys syftar till att identifiera svaga delar av ett system för att på effektivaste sätt förebygga och åtgärda eventuella brister i systemet. Ett sätt att identifiera de svaga delarna är att simulera olika scenarier genom att använda en matematisk modell. I den här studien byggs en matematisk modell upp med hjälp av optimeringslära, en gren inom matematiken som används för att hitta ett optimalt värde till en funktion under vissa begränsande villkor. Optimeringslära lämpar sig väl for att studera flöden, så som till exempel Stockholms kollektivtrafik. Stockholms kollektivtrafik kan ses som ett flöde av resenärer som så snabbt som möjligt vill ta sig från en punkt till en annan under begränsade villkor i form av utrymme, tid och förbindelser. Stockholms kollektivtrafik förenklas till ett system bestående av 34 noder, sammanlänkade genom SL:s spårtrafik Och stombusslinjer. Normalt trafikflöde simuleras och används som referensfall För fyra olika scenarier med begränsningar i trafiken. De fyra scenarierna är: • Kapacitetsbegränsningar på sträckan mellan Slussen och T-Centralen • Kapacitetsbegränsningar på sträckan mellan Skanstull och Gullmarsplan • Kapacitetsbegränsningar på sträckan mellan Fridhemsplan och Alvik • Inga fungerande tvärförbindelser Resultatet från simuleringarna visar att Stockholms kollektivtrafik generellt har bra resiliens men att systemet är väldigt beroende av T-Centralen och Stockholm Central som en stor del av resenärerna passerar. Efter känslighetsanalys dras slutsatsen att den matematiska modellen genererar trovärdiga resultat och optimeringslära visar sig vara ett bra verktyg vid sårbarhetsanalys av flöden. / The purpose of performing a vulnerability analysis is to identify security deficiencies in a system and to reduce the risk of harmful events in an efficient manner. One way to identify vulnerabilities is to simulate different scenarios by using a mathematical model. In this study an optimization model is used, which means that an optimal value is found for a function under some certain limiting constraints. Optimization is a good choice when dealing with flow problems, such as the public transportation system in Stockholm. The public transportation system in Stockholm can be viewed as a flow of travelers that want to move as quickly as possible from one place to another while constrained by limited capacity, time and connections. The public transportation system is simplified into 34 nodes, connected through the major routes, in form of commuter trains, subways, trams and buses. Normal traffic flow is simulated and used as a reference for  our scenarios with certain limitations in the traffic flow. The four different scenarios are: • Capacity limitations between Slussen and T-Centralen • Capacity limitations between Skanstull and Gullmarsplan • Capacity limitations between Fridhemsplan and Alvik • Non working transverse route. The simulation results prove that the Stockholm public transportation system has good resilience. However, the system is very dependent on the specific nodes T-Centralen and Stockholm Central, through which an extensive number of travelers pass by each day. A sensitivity analysis is performed on the result to ensure that the mathematical model generates credible results, and optimization theory proves to be a good tool for investigating the vulnerability of flows. / <p>www.ima.kth.se</p>

<p>Within telecommunication and routing of traffic in IP-networks a protocol named“Open Shortest Path First” (OSPF) is widely used. This means that a server dealswith the routing over a network with given weights by calculating shortest paths touse for routing. If we assume that a desired traffic pattern is given the problem isto find out if it is possible to set the weights so that the desired traffic pattern is apart of a shortest path graph. In this thesis we assume that it is a unique shortestpath. To search for weights that solve the problem leads to a complex LP-model. Analternative is to search in the LP-dual under certain restrictions. These solutions tothe LP-dual are called conflicts and a conflict means that there exists no weights sothat the desired traffic pattern is obtained. The goal of this thesis is to study, classifyand search for conflicts. An algorithm has been developed that finds some kind ofconflicts in polynomial time with respect to the size of the graph.</p> / <p>Inom telekommunikation och ruttning av datatrafik i IP-nätverk så används oftaett protokoll som kallas “Open Shortest Path First” (OSPF). Det innebär att enserver sköter ruttningen över ett nätverk genom att utifrån givna bågkostnaderberäkna billigaste vägar som används för ruttningen. Frågeställningen utgårfrån att vi har ett önskat ruttningsschema och vi vill ta reda på om det gåratt sätta bågkostnader så att det önskade ruttningsschemat ingår i en billigasteväg-graf. I det här examensarbetet splittas inte trafik utan varje billigaste vägär unik mellan två noder. Att söka efter bågkostnader som löser problemet geren krävande LP-modell och ett alternativ är att utgå från LP-dualen undervissa restriktioner. Dessa lösningar till LP-dualen benämns konflikter och enkonflikt motsvarar att det inte finns några bågkostnader så att det önskaderuttningsschemat fås. Målet med examensarbetet är att studera, klassificeraoch söka efter konflikter. En algoritm har tagits fram som hittar vissa typer avsådana konflikter i polynomiell tid, sett till storleken på grafen.</p>

Within telecommunication and routing of traffic in IP-networks a protocol named“Open Shortest Path First” (OSPF) is widely used. This means that a server dealswith the routing over a network with given weights by calculating shortest paths touse for routing. If we assume that a desired traffic pattern is given the problem isto find out if it is possible to set the weights so that the desired traffic pattern is apart of a shortest path graph. In this thesis we assume that it is a unique shortestpath. To search for weights that solve the problem leads to a complex LP-model. Analternative is to search in the LP-dual under certain restrictions. These solutions tothe LP-dual are called conflicts and a conflict means that there exists no weights sothat the desired traffic pattern is obtained. The goal of this thesis is to study, classifyand search for conflicts. An algorithm has been developed that finds some kind ofconflicts in polynomial time with respect to the size of the graph. / Inom telekommunikation och ruttning av datatrafik i IP-nätverk så används oftaett protokoll som kallas “Open Shortest Path First” (OSPF). Det innebär att enserver sköter ruttningen över ett nätverk genom att utifrån givna bågkostnaderberäkna billigaste vägar som används för ruttningen. Frågeställningen utgårfrån att vi har ett önskat ruttningsschema och vi vill ta reda på om det gåratt sätta bågkostnader så att det önskade ruttningsschemat ingår i en billigasteväg-graf. I det här examensarbetet splittas inte trafik utan varje billigaste vägär unik mellan två noder. Att söka efter bågkostnader som löser problemet geren krävande LP-modell och ett alternativ är att utgå från LP-dualen undervissa restriktioner. Dessa lösningar till LP-dualen benämns konflikter och enkonflikt motsvarar att det inte finns några bågkostnader så att det önskaderuttningsschemat fås. Målet med examensarbetet är att studera, klassificeraoch söka efter konflikter. En algoritm har tagits fram som hittar vissa typer avsådana konflikter i polynomiell tid, sett till storleken på grafen.

The scope of this thesis is modelling and solving large-scale planning problems in the supply chain within the forest industry. Five research papers are included, the first three of which focus on the modelling, and the last two on the solution methods. All problems included are tactical multi-commodity problems expressed as mixed integer programming (MIP) models. The work has been done in collaboration with two Swedish companies within the forest industry. In Paper I, a problem concerning the supply chain of forest fuel for Sydved Energileveranser AB is modelled and solved. We study the problem of deciding when and where forest residues are to be converted into wood chips, and how the residues and chips are to be transported and stored in order to satisfy energy demand at heating plants. The company has long-term contracts with forest owners and saw mills. Decisions in the model include whether or not additional harvest areas and saw mills are to be contracted and which terminals to use. The planning horizon is one year and monthly time periods are used. Papers II--V are based on planning problems at Södra Cell AB. The planning horizon is normally one year. Papers II--III consider only one time period. In Paper II the supply chain from pulp mills to customers is modelled and the combined problem of deciding terminal locations and which ship routes to use is studied. Shipping vessels chartered on short or long term are used to transport products to terminals in Europe. From each terminal, the products are transported to customers by truck, train, or a combination of both. In addition, trains and trucks can be used for transports directly to customers from mills. In Paper III the entire supply chain, from harvest areas to customers, is considered. Decisions included are transportation of raw materials, production mix, the distribution of pulp products, and the selection of potential orders and their quantities at customers. The ship routes are considered as flow links. In Papers IV--V the problems in Papers II--III are combined into one model and several time periods are used. Lagrangian heuristics based on Lagrangian decomposition are used as solution methods in both papers. In Paper IV, the approach leads to subproblems for each time period, whereas in Paper V, another approach that results in subproblems for different parts of the supply chain is developed. All models are based on real data from the companies. The models are detailed and describe the problems accurately. The solution methods are developed such that the solution time is kept within practical limits. Results from Papers II--III have been used by Södra Cell AB to support the change of the terminal structure as well as in budget planning. / Denna avhandling presenterar matematiska modeller och lösningsmetoder för optimering av olika logistikproblem inom skogsindustrin. Vi studerar försörjningskedjor för skogsbränsle och massaproduker, och beaktar den årliga planeringen i syfte att optimera flödet. Det första problemet behandlar skogsbränsle och är ett samarbete med Sydved Energileveranser AB. Råmaterial i form av grenar och toppar från avverkningsplatser ska flisas och transporteras till värmeverk, eventuellt via terminaler. Det finns möjlighet att flisa både i skogen och på terminaler. Biprodukter från sågverk kan också användas som råmaterial. Vid behov kan utbudet av råmaterial utökas genom att fler avverkningsplatser och sågverk kontrakteras. Värmeverken har en efterfrågan, angiven i kWh per månad, som ska uppfyllas. Exempel på beslut som ska tas är var flisning ska ske, om nya avverkningsplatser ska kontrakteras, var lagring ska ske, samt hur och när skogsbränslet ska transporteras. Nästföljande problem behandlar massaprodukter och är ett samarbete med Södra Cell AB. Olika sorters massaved från skogen och biprodukter från sågverk utgör råmaterial för produktion av massaprodukter. Råmaterialet transporteras till massabruk för tillverkning enligt specificerade recept. De färdiga produkterna transporteras sedan med fartyg till terminaler i Europa. Från terminalerna transporteras produkterna vidare till pappersbruk, vilka är företagets slutkunder. Massaprodukterna transporteras i vissa fall med lastbil eller tåg direkt från massabruken till kunderna. Efterfrågan är angiven inom vissa gränser i olika order. Vissa order är fasta, vilket innebär att dess efterfrågan måste uppfyllas, medan andra order är fria. Exempel på beslut som ska tas är vilka bruk olika produkter ska produceras på, hur många och vilka terminaler som ska användas, samt hur transporterna ska utföras för att ge bästa resultat. Utifrån ovanstående beskrivningar har matematiska modeller formulerats. Ge-nom att lösa dessa kan vi få svar på logistik- och transportfrågorna och ett optimalt flöde kan hittas. För att lösa modellerna har kommersiell programvara använts. Heuristiker och mer avancerade optimeringsmetoder har också utvecklats i syfte att producera bra lösningar snabbare. / Article 4 was a manuscript entitled "Solving a multi-period supply chain problem for a pulp industry using Lagrangian heuristics based on time periods" at the time of the thesis defence.

QC 20100601

In this thesis, optimization approaches for intensity-modulated radiation therapy are developed and evaluated with focus on numerical efficiency and treatment delivery aspects. The first two papers deal with strategies for solving fluence map optimization problems efficiently while avoiding solutions with jagged fluence profiles. The last two papers concern optimization of step-and-shoot parameters with emphasis on generating treatment plans that can be delivered efficiently and accurately. In the first paper, the problem dimension of a fluence map optimization problem is reduced through a spectral decomposition of the Hessian of the objective function. The weights of the eigenvectors corresponding to the p largest eigenvalues are introduced as optimization variables, and the impact on the solution of varying p is studied. Including only a few eigenvector weights results in faster initial decrease of the objective value, but with an inferior solution, compared to optimization of the bixel weights. An approach combining eigenvector weights and bixel weights produces improved solutions, but at the expense of the pre-computational time for the spectral decomposition. So-called iterative regularization is performed on fluence map optimization problems in the second paper. The idea is to find regular solutions by utilizing an optimization method that is able to find near-optimal solutions with non-jagged fluence profiles in few iterations. The suitability of a quasi-Newton sequential quadratic programming method is demonstrated by comparing the treatment quality of deliverable step-and-shoot plans, generated through leaf sequencing with a fixed number of segments, for different number of bixel-weight iterations. A conclusion is that over-optimization of the fluence map optimization problem prior to leaf sequencing should be avoided. An approach for dynamically generating multileaf collimator segments using a column generation approach combined with optimization of segment shapes and weights is presented in the third paper. Numerical results demonstrate that the adjustment of leaf positions improves the plan quality and that satisfactory treatment plans are found with few segments. The method provides a tool for exploring the trade-off between plan quality and treatment complexity by generating a sequence of deliverable plans of increasing quality. The final paper is devoted to understanding the ability of the column generation approach in the third paper to find near-optimal solutions with very few columns compared to the problem dimension. The impact of different restrictions on the generated columns is studied, both in terms of numerical behaviour and convergence properties. A bound on the two-norm of the columns results in the conjugate-gradient method. Numerical results indicate that the appealing properties of the conjugate-gradient method on ill-conditioned problems are inherited in the column generation approach of the third paper. / QC 20100709