Is there a scheduling algorithm that optimizes for "maker's schedules"?
- by John Feminella
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 pi is either a maker (Mk) or a manager (Mg).
Each person has a schedule si.
Everyone's schedule is H hours long.
A schedule consists of a series of non-overlapping intervals si = [h1, ..., hj].
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 Mt 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.
