Visualizing the Ryan-Foster Rule

In a previous post, I described a system for scheduling shifts to workers that was state of the art. It still is for large problems (small problems can be solved exactly with integer programming). The fixing rule to obtain integer solutions is sometimes called the Ryan-Foster rule [1] and this post will explore how this rule can be visualized.

Recall that the fixing works works not by fixing an entire column (the whole roster for one worker), but by fixing individual shifts to individual workers that already are close to 1 in the fractional solution. When summing over all columns for one worker, each shift will end up assigned to that worker between 0 and 1.

It looks like this. This is from instance 9 from these benchmarks:

Instance9-A

The x-axis shows the iteration number during column generation. Every line is a possible shift. The grayscale shows the fractional assignment of the shift to the worker. Red means that the shift has been fixed to 1. The blue column is the integer solution.

In the first iterations, everything is very unclear. Slowly, as the optimization progresses, the solution becomes more integral until it is time to start fixing.

Some workers have their solution earlier in the process:

Instance9-J

And some later:

Instance9-AE

A Larger Example

Here is instance 19 from the same benchmark set:

Instance19-AInstance19-ABInstance19-AL

Usefulness

I think these plots give some actionable insights. Right now, the column generation LP proceeds until there is very little improvement each iteration. Only then is shift fixed to workers. But these plots show that many shifts stay very close to 1 for a long time util they are fixed. Fixing these shifts earlier would speed things up (pricing becomes faster), hopefully without making the wrong decision.

  1. Ryan, David M., and Brian A. Foster. “An integer programming approach to scheduling.” Computer scheduling of public transport urban passenger vehicle and crew scheduling (1981): 269-280.
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s