Sunday, July 27, 2008

Grad Math - Those Super Scandinavians

Tore EngsetThis summer's (2008) graduate course was Mathematical Modeling. There was something suspicious about the enrollment -- the course was filled to capacity with 25 students. Reason? The teacher was considered an easy grader.

The course required a presentation on a math modeling topic of one's own choosing. At the very start of the course I chose the "floating license problem" which has to do with determining how many floating (concurrent) licenses to purchase for a community of users. The floating license model is one of many ways that commercial software is licensed. The idea is that you don't have to buy every user a license. You buy a few with the knowledge that at peak usage some users may have to wait to obtain a license to use the software.


Agner Erlang
Now this may sound like a modern problem because this form of licensing is at most 40 years old. However the problem is a classic one from queuing theory and was solved when the first telephone systems were being built in the early twentieth century. The research was published by Agner Erlang (1917) and Tore Engset (1918). Erlang was Danish; Engset was Norwegian.


I picked this topic for two reasons: to get credit at school and to get credit at work. At work my department manages licenses for software development tools and some of the licenses are of the floating variety. Since I had no idea where to start I did a literature search and came up with a fantastic hit in IEEE Transactions on Software Engineering -- "Determining the Proper Number and Price of Software Licenses" -- written by five Finns at the University of Turku in Finland. The theory and applications were all there in the paper.

Now my fellow students were content to regurgitate the papers on topics that they found interesting. I decided to go a mile farther and reproduce the results of the authors. In the paper they presented analytic results for different combinations of users and licenses. They also described a software simulation they performed to reinforce the analytic results.

So there you have it. I decided to implement a simulation using Mathematica. Mathematica is a symbolic math package that is partly responsible for bringing me back to higher mathematics. Here's what I had to go by (the "requirements" if you will) from the Finnish paper:

The generation of the requests is done separately for each user by reserving the given number of nonoverlapped intervals from the set of working hours. This is done by choosing the starting times randomly and then by checking whether the service intervals obtained in this way overlap. If there are overlapping intervals, the simulation generates a new set of intervals...

Here is my schedule generating function written in Mathmatica:


GenerateSchedule[p_, l_, u_]:= Module[{duplicates,randTimes,schedule,j},
duplicates = True;
While [duplicates == True,
randTimes = RandomChoice[Range[1,p],RandomChoice[Range[l,u]]];
duplicates = (Length[Union[randTimes]] < Length[randTimes]);
];
schedule = Table[0, {p}];
Do[schedule[[j]] = 1, {j, randTimes}];
schedule
]

The meaning of the parameters:
p - number of time units for the schedule
l - lower limit for the # requests during the time period
u - upper limit for the # requests during the time period



Here is a sample schedule for 10 minutes with 4 license requests:


minute12345678910
use0110010010


Back to class. On the last session of class everyone did their presentations. Most of the presentations did not involve the use of any math tools. A couple did use Microsoft Excel and one used Minitab. So I guess I won with Mathematica.

2 comments:

Anonymous said...

Is the paper that you mentioned ("Determining the Proper Number and Price of Software Licenses") the same as this one: "Determining the Proper Number of Software Licenses" available at:

http://www.tucs.fi/publications/techreports/TR535.ps.gz

?
I'm thinking about buying the article that you mentioned, but if it is equal to this free online copy (which I think is the first edition of the article), I don't need tou buy it!

My email is duranjaya@gmail.com

Thank you!

Anonymous said...

I email the original PDF file to duranjaya@gmail.com. If you didn't get it maybe your mail filter blocked it.

Rock