Mission Impossible? Why Optimizing a Schedule is So Difficult

Imagine a set of islands with mountainous terrains. There are cliffs and crevasses, rivers and ravines all over these islands. Your goal is to find the highest point on these islands. Using an app on your cell phone, you enter the coordinates of a point and it returns the elevation at that point. After you find a location with a fairly high point, you try another location nearby and you wind up in a gully–or even in the water! There is not much information gained from results of your previous trials to suggest what your next trial should be, so you’re stuck with searching in an almost random fashion.

Searching for an optimal schedule is a search much like this.

In a previous BLOG (http://www.schedulingdoneright.com/whats-a-good-schedule/ ), I described a sequential process for generating a good schedule. In essence, the process is:

• Look at the activities one at a time;
• For each activity, find all the possible times and resource combinations that satisfy all of the constraints;
• Score each of the possibilities;
• Select the possibility with the highest score.

This simple sequential procedure mimics how human schedulers do their job. However, the procedure is short-sighted because you can make early decisions that make later decisions inferior. The procedure may even eliminate possibilities that are part of an optimal solution.

• What if you picked the wrong order in which to consider the activities?
• How many different processing sequences would you have to try to make sure that one of them led to the optimal schedule?
• What if you selected resources that used up the possibilities for other activities you haven’t considered yet?

A little contemplation makes it clear that the variations on this process are numerous. This is called the combinatorial explosion. It arises in any problem that has alternative decisions embedded in it. Scheduling is one of those problems.

But scheduling is even more complicated than just making choices about alternatives. Activity start times, resource availability times and resources assignment times are everywhere in the scheduling problem. And time is a continuous variable. (See my blog on time as a continuum,  http://www.schedulingdoneright.com/time-is-a-continuum/) . That is, scheduling requires selecting values for variables that can have only specific values (discrete variables) and selecting values for times that can have any values (continuous variables). These two types of variables are tied together–meaning that the values you select for one type strongly influence the values that need to be selected for the other. Attempts to break the problem into two pieces–one with all continuous variables, and the other with all discrete values–have been unsuccessful. This is at the heart of why creating an optimal schedule is so darn difficult.

Without going down the rabbit hole of optimization techniques, let me say that there are many ways to address continuous-variable problems, and other ways to address discrete-variable problems. There are a few techniques that treat both, but they are impractical to use repeatedly, and they don’t scale up well to realistically-sized problems because of their complicated set-up requirements and long run times.

So the best you can do for day-to-day applications is to run through the sequential process I described earlier. Here are a few ideas to make the decisions smarter so that you get the best outcome.

• Find a smart way to determine the sequence you use to process the activities one-at-a-time.
• Use a “look-ahead” logic that makes current decisions that preserve the possibilities for later decisions.
• When a conflict is detected, find intelligent ways to backtrack in the sequential process in order to change a previous decision before proceeding.

Does your scheduling application handle both kinds of variables? Does it use intelligent local decision making?

How do you optimize your scheduling processes? Let me know in the comments section. Need more help? Call me.