Category Archives: Optimization

Using column generation to minimize production waste

Minimizing production waste can result in significant cost savings. However, calculating just the right production configuration can be a tedious task.

Let’s take the example of a firm which delivers sheet metal. The sheets it delivers are all of the same width but can differ in length. The raw material used by the company are metal sheets of 3 meters wide by 20 meters long. Clients can order any length metal sheets (as long as it doesn’t exceed 20 meters).

Let’s say there is demand for the following lengths of sheet metal (all are 3 meters wide). The number of demands are denoted in the next line. E.g. for 40 items of length 6 have to be produced, 5 items of length 9 have to be produced and so on.

items_demands
Continue reading →

December 11, 2012Permalink Leave a comment

Genetic algorithms: a simple R example

Genetic algorithm is a search heuristic. GAs can generate a vast number of possible model solutions and use these to evolve towards an approximation of the best solution of the model. Hereby it mimics evolution in nature.

GA generates a population, the individuals in this population (often called chromosomes) have a given state. Once the population is generated, the state of these individuals is evaluated and graded on their value. The best individuals are then taken and crossed-over – in order to hopefully generate 'better' offspring – to form the new population. In some cases the best individuals in the population are preserved in order to guarantee 'good individuals' in the new generation (this is called elitism).

The GA site by Marek Obitko has a great tutorial for people with no previous knowledge on the subject.

To explain the example I will use my version of the Knapsack problem.

You are going to spend a month in the wilderness. You’re taking a backpack with you, however, the maximum weight it can carry is 20 kilograms. You have a number of survival items available, each with its own number of “survival points”. You’re objective is to maximize the number of survival points.

Continue reading →

August 1, 2012Permalink 22 Comments

Estimating required hospital bed capacity

Estimating required hospital bed capacity requires a thorough analysis. There are a lot of ways of approaching a capacity requirement problem, but I think we can agree that a simple spreadsheet analysis just won't cut it.

The approach described in this post makes use of discrete-event simulation and, just to clarify, makes abstraction from a lot of variables which should be taken into consideration in a real-life analysis.

To explain the approach, the following case will be used:

An emergency department of a small regional hospital receives complains about its emergency admission capacity. After investigation of its admission data it becomes clear that their service level is not up to par with that of other hospitals. Therefore, plans for the redesign of the emergency department and an investment in its emergency bed capacity are presented. The plan proposes a new bed capacity of 12 beds (coming from a previous of 10 beds). The Chief of Medicine wants to know what the effect of this investment will be on their emergency admission service level.

The emergency department has recorded data on the interarrival times of patients that are admitted (or should be admitted) to an emergency bed. The following graph shows the interarrival distribution (triangular: mode=5, min=.1, max=12):

plot of chunk unnamed-chunk-1

Continue reading →

July 23, 2012Permalink Leave a comment

Linear programming in R: an lpSolveAPI example

First of all, a shout out to R-bloggers for adding my feed to their website!

Linear programming is a valuable instrument when it comes to decision making. This post shows how R in conjunction with the lpSolveAPI package, can be used to build a linear programming model and to analyse its results.

The lpSolveAPI package provides a complete implementation of the lp_solve API.

The example case;

A trading company is looking for a way to maximize profit per transportation of their goods. The company has a train available with 3 wagons. When stocking the wagons they can choose between 4 types of cargo, each with its own specifications. How much of each cargo type should be loaded on which wagon in order to maximize profit?

Continue reading →

July 14, 2012Permalink 11 Comments