Scheduling Zoo

November 21, 2008

The blog is about 20 days old and as part of the blog entries, I would like to share some OR websites from time to time.  These will be tagged as “Useful OR websites”.elephant

The first one of these entries is… the Scheduling Zoo.  I was looking for the computational complexity of different scheduling problems for my research and came across this website.  The Scheduling Zoo is a searchable bibliography on the complexity of scheduling problems by Peter Brucker and Sigrid Knust and the website is maintained by Christoph Duerr.

At the zoo, you pick your environment (e.g., single machine, job shop, etc.), then, the problem characteristics (e.g., precedence constraints or not) and the objective function (e.g., minimize makespan, minimize the number of late jobs, etc.) then it returns the known complexity results along with the related problems, their complexity and references for each!   Given the elephantine literature on scheduling it is a pretty neat, specialized bibliography search website.  You can find a related website here.

They collect statistics on the searches. Turns out:

* The most popular objective function is to minimize makespan (1936 searches when I looked) followed by a distant second, to minimize the sum of completion times (517 searches).

* The most popular machine environment is single machine scheduling (1362 searches) followed by parallel machine scheduling with identical machines (665)

* And, the two most popular variants are “release times” (1505 searches) and “precedence constraints” (1038).


Update on: “Election Results: OR Wins…”

November 17, 2008

On election night, I had my TV, several news websites and the website of the election prediction model of Sheldon Jacobson and colleagues on (the website has been updated since), comparing the model’s predictions to the actual election results as the numbers were coming in…   I had to sleep at some point, so, it ended abruptly  (see the original entry).

It has been a while, but I wanted to write a quick update on how the model performed. You can find the details at the website but here’s a synopsis:

” Our model predicted 50 of the 51 states (including the District of Columbia).

The Strong Democrat Swing scenario was the closest to the actual results . . .

All of these states, except Indiana, were correctly predicted. . . From these results, Indiana was the most difficult state to predict, closely followed by Missouri. “

Yes, OR indeed won…  Also, take a look at the cartogram, a map in which the sizes of states are rescaled according to their population, in Mike Trick’s blog entry.

LP Rocks!

November 11, 2008

This semester I am teaching Linear Programming (LP).  This year, we have students from many different backgrounds and departments taking the class, which I think is great news for our field. The more we make OR accessible to other fields, the better.  Anyway, this year I decided to do something different and wanted to show the students all the different uses of linear programming in real life. So, I searched INFORMS journals + more for applications of LP.  Even though many real-world problems involve nonlinearities and integer decision variables, the list of applications of LP turned out to be pretty impressive. Take a look:

∙  This is an application in health-care:

Remeijn, H., Ahuja, R., Dempsey, J. and A. Kumar, “A New Linear Programming Approach to Radiation Therapy Treatment Planning Problems,”  Operations Research, 54(2): 201-216, 2006.

∙  This is an application in alternative energy (specifically wind energy). I came across this while reading GreenOR.  Here’s the original entry on it.   This application has been developed by the US National Renewable Energy Laboratory (NREL) to determine the expansion of wind electric generation and transmission capacity. It passes information from a Geographic Information System (GIS) into a linear program.

Here’s the link to the Wind Deployment System (WinDS) model and link to the LP model.

∙  This application is in finance:

Chalermkraivuth, K. C., Bollapragada, S., Clark, M. C., Deaton, J., Kiaer, L., Murdzek, J.P., Neeves, W., Scholz, B.J. and D. Toledano,  “GE Asset Management, Genworth Financial, and GE Insurance Use a Sequential-Linear-Programming Algorithm to Optimize Portfolios,”  Interfaces, 35: 370 – 380, September-October 2005.

∙  This application is in data mining (classification, statistics):

Eva K. Lee, Richard J. Gallagher, David A. Patterson,  “A Linear Programming Approach to Discriminant Analysis with a Reserved-Judgment Region,”  INFORMS Journal on Computing, 15(1): pp. 23–41, 2003.

∙  And, this is an application in Sports:

I. Horowitz, “Aggregating Expert Ratings Using Preference-Neutral Weights: The Case of the College Football Polls,” Interfaces, 34(4): 314–320, July–August 2004.

There are many more of course, but the above sample alone makes a strong case for the versatility and power of LP.

Election Results: OR wins…

November 5, 2008

Now that the election results (or, estimates) are in, I was curious to see how the election prediction model of Sheldon H. Jacobson along with co-authors Steven E. Rigdon, Edward C. Sewell and Christopher J. Rigdon has performed.  OR bloggers Micheal Trick and Laura McLay wrote about this in their blogs earlier.  If you are not familiar with it, here is a link to their website and here is a link to their paper that explains the model. From their paper:

It uses a Bayesian estimation approach that incorporates polling data, including the effect of third party candidates and undecided voters, as input to a dynamic programming algorithm … to build the probability distribution of the total number of Electoral College votes for each candidate.

Their results were last updated on Tuesday, Nov 4th, using the latest polling data. Of course, the model is as correct as the polling data that is given as an input to the model. However, take a look at this:

11:45pm AZ time: Obama has 338 and McCain has 159 electoral votes.  The prediction model has 338 Safe Electoral Votes for Obama and 157 Safe Electoral Votes for McCain. They define “safe” when they predict the candidate has a 0.85 chance or better for winning.  Montana, Missouri, Indiana and N. Carolina still not decided. In the prediction model, these are the states that are not “safe” along with N. Dakota.

12:15am AZ time: Indiana goes Blue… Hmm… Their model tends to Red… (the only time it does not match)

—>> Can’t wait to see the final results. . .

INFORMS Computing Society Student Paper Competition

November 2, 2008

This year, Guanghui Lan took the ICS Student Paper Award for his paper titled “Efficient Methods for Stochastic Composite Optimization”.

Last year’s winner was Amit Partani on his paper titled “Adaptive Jackknife Estimators for Stochastic Programming”.

Both papers deal with stochastic optimization, which is great news for the future of the field.

Microchip Embedded Cactus

November 1, 2008

Saguaro Cacti in Tucson

One of the greatest perks of living in AZ is to experience the wonderful saguaro cacti everyday.

I read this in Time the other day:

“National Park Service officials will soon embed microchips in Arizona’s signature saguaro cactus plants to deter thieves who dig them up and sell them to landscapers and nurseries. The microchips, which are inserted with a syringe, will help authorities identify stolen plants.”

Apparently, they sell for about $1,000 each.  Talking about microchips, there is substantial research on effective use of RFID chips in OR/MS, for instance, for inventory tracking and control.

Hello world!

November 1, 2008

Quoting Mike Trick:

Like everyone and their dog, I have a blog

I’ve been reading so many blogs these days (mainly on OR), decided to start one…