Is there a scheduling algorithm that optimizes for "maker's schedules"?

Question

You may be familiar with Paul Graham's essay, "Maker's Schedule, Manager's Schedule". The crux of the essay is that for creative and technical professionals, meetings are anathema to productivity, because they tend to lead to "schedule fragmentation", breaking up free time into chunks that are too small to acquire the focus needed to solve difficult problems.

In my firm we've seen significant benefits by minimizing the amount of disruption caused, but the brute-force algorithm we use to decide schedules is not sophisticated enough to handle scheduling large groups of people well. (*)

What I'm looking for is if there's are any well-known algorithms which minimize this productivity disruption, among a group of N makers and managers.

In our model,

• There are N people.
• Each person p_i is either a maker (Mk) or a manager (Mg).
• Each person has a schedule s_i.
• Everyone's schedule is H hours long.
• A schedule consists of a series of non-overlapping intervals s_i = [h₁, ..., h_j].
• An interval is either free or busy. Two adjacent free intervals are equivalent to a single free interval that spans both.
• A maker's productivity is maximized when the number of free intervals is minimized.
• A manager's productivity is maximized when the total length of free intervals is maximized.

Notice that if there are no meetings, both the makers and the managers experience optimum productivity. If meetings must be scheduled, then makers prefer that meetings happen back-to-back, while managers don't care where the meeting goes. Note that because all disruptions are treated as equally harmful to makers, there's no difference between a meeting that lasts 1 second and a meeting that lasts 3 hours if it segments the available free time.

The problem is to decide how to schedule M different meetings involving arbitrary numbers of the N people, where each person in a given meeting must place a busy interval into their schedule such that it doesn't overlap with any other busy interval. For each meeting M_t the start time for the busy interval must be the same for all parties.

Does an algorithm exist to solve this problem or one similar to it? My first thought was that this looks really similar to defragmentation (minimize number of distinct chunks), and there are a lot of algorithms about that. But defragmentation doesn't have much to do with scheduling. Thoughts?

---

(*) Practically speaking this is not really a problem, because it's rare that we have meetings with more than ~5 people at once, so the space of possibilities is small.

Answer 1

This problem looks hard enough to be NP, but I think it admits some decent approximations.

In particular, I think you can probably manage reasonably well with a meeting size optimization, where you optimally place the largest meeting (in terms of the number of makers who must attend, since they are the ones you're trying not to disrupt), and then do so successively with smaller meetings. To break ties in smaller meetings of the same length, you could weight the meetings by the meeting-load of the makers asked to participate (so that you will get a chance to optimize over them and not make their lives too much worse).

Now you've broken the problem down to schedule a single meeting, since any already-scheduled meeting will effectively just reduce a person's schedule to shorter. And the solution is pretty straightforward: the optimal solution is the one aligned with a maximal number of edges of schedules of makers such that everyone can make that time. You should be able to solve this problem even with brute force in something like O((k+g)*k*n) where k is the number of makers, g the number of managers, and n the typical number of intervals in a maker's schedule.

The only problem would be if this straightforward approach would lead to meetings that couldn't be satisfied. In this case, you could boost the priority of that meeting by one or more slots and try again.

Answer 2

I remember implementing something very similar to your problem with A* search algorithm. You will easily find several implementation of the algorithm available but in order to apply it to the scheduling problem you will have to construct distance and heuristic functions based on your model and split continuous time into chunks.

Answer 3

A good approximation for this can be had by the use of a Genetic algorithm.

Write a function to create 1000 sample random schedules assigning makers and managers randomly.

Write another function (fitness function) that assigns demerits to schedules with problems (people working at the same time, not enough makers, not enough managers, someone not worked enough, someone worked too much).

foreach schedule assign calculate fitness keeping a reference to the lowest scoring (best) schedule.

while (best schedule > minimum fitness value)
    foreach schedule s in population of schedules
        foreach time slot
           if (random < .5)
               choose value from best schedule
           else
               choose value from schedule s
           end if
       end foreach
       score schedule s with fitness function
    end foreach
end while

While this method will not produce an optimal schedule and has the possibility of finding local minimums. It will always produce a schedule and you can always add more constraints to the fitness function for any conditions you don't want to see. This type of algorithm can handle many different types of constraint satisifaction problems.

I have personally used a similar algorithm to schedule my Wifes Co-Op preschool for the entire year in about two hours on my laptop.

Answer 4

Try taking a look at Simulated Annealing. It's similar to Genetic Algorithms as Jeremy E describes, but instead of randomly generating your starting set of schedules you start with some valid but non optimal schedule. The idea is to generate some "neighbor" of the original schedule by randomly shuffling around some meeting times, then testing fitness before iterating.

S' = Starting Schedule
S = S'    
while( Fitness( S ) < Minimum Fitness ) 
{
    NS = Neighbor( S )
    if( Fitness( NS ) > Fitness( F ) )
    {
         S = NS
    }
}
Return( S )

Instead of testing against some minimum fitness level, you could also specify a set number of iterations so you could deterministically tell when the program would finish executing.

The thing about this algorithm is the final result tends to look like the starting state, so if you wanted to weight say a large meeting (in terms of size of makers) early in the day, you could do so.