# Scheduling Algorithm that Maximizes Gaps Between Participants’ Appearances

I’m currently tackling a programming challenge to schedule a series of “performances” (a set of dancers together on a stage for a period of time, concretely) that each involve a set of “participants” (the set of dancers who form the group for a performance). Each performance involves some subset of all the participants, and each participant is in some subset of all the performances. The mapping of performances to their participants and participants to their performances is easily determined. Performances occur in a particular order, back-to-back, but there is no concern of specific start/end times… the goal is simply to come up with a linear ordering of them.

The goal is to generate an ordered schedule of performances that maximizes the minimum gap between performances for all participants. For context, the idea is that each dancer wants as much time as possible after a given performance to change costumes or otherwise prepare for their next performance. One wants everybody to have “as much time as possible” to prepare between performances, and we may as well stipulate that it be fair and we seek schedules where all participants have at least N breaks (a “break” is a performance that occurs in the schedule in which the given participant on a break is not involved) between their performances, where N is the maximum feasible gap for the given problem space. The algorithm would ideally generate a list of all optimal schedules (or if necessary to solve it effectively, one optimal schedule would be OK) such that all participants have at least N breaks between their performances, maximizing N.

I’ve attempted this using a brute force, recursive approach, but the complexity is so high that I believe a smarter approach is necessary. With, for example, ~85 performances and ~500 participants, the algorithm required hundreds of millions of iterations and barely made a dent in the solution (perhaps the complexity is O(n!m), where n is the number of performances and m is the number of participants?). I’m curious if an efficient algorithm can be devised or if the problem is NP-complete? I can come up with certain optimizations such as pre-calculating what performances cannot follow what others, but I don’t think they change the order of complexity and so are unlikely to solve the problem.

Thanks in advance for any advice you can provide or pointers to established algorithms / similar problems that will help me solve this.

I've solved scheduling problems like this in the past with a simulated annealing approach.

1. Define your objective function to be "sum(1 / gap) for all gaps for all performers". This is pretty close to your "maximin" objective function while still retaining some knowledge of the full distribution of gaps.
3. Swap performances at random and accept the change in accordance with the normal simulated annealing criteria (always if it reduces the objective function, with a decreasing probability with time if it increases the objective function)

Will this get you the absolute minimum for the objective function? No. Will it be "good enough"? Probably.

You may need to play with the power of minus one in the objective function.

• Thank you Philip, this algorithm is fascinating and I'm so glad you introduced me to it. I've been having a blast tinkering with it (changing the objective function, performing temperature resets, occasionally randomizing or resetting to the best known configuration...) and have had lots of success so far achieving good solutions. Plenty left to tune but this is a fantastic launching point. Thank you!! Feb 23 at 21:38

Yes, this sounds very much like the kind of problem that would require O(n! ⋅ m) time to find an optimal solution.

When trying to find an optimal solution, some algorithm construction techniques might help here:

• Pruning known suboptimal solutions. Keep track of the best known solution. If you are currently constructing an alternative solution, and the alternative cannot improve over the known best, you can stop pursuing it and can continue with the next alternative.

If you are construction solutions in a breadth-first manner, you can also prioritize continue constructing the best known solutions. A well-known application of this technique is the Dijkstra shortest-path search.

Further prioritization may become possible if you don't just evaluate partial solutions based on their current score, but on their best achievable score. This can be determined by a heuristic. To continue referencing the shortest-path problem, A* uses this technique. However, this requires careful consideration whether the heuristic used is admissible.

Here, a (presumably admissible) heuristic for the best achievable minimum gap size would be the number of remaining performances divided by the number of remaining performances of the most-active performer.

• Symmetry. A detail of your problem is that schedules are equally good read forwards and backwards. This can perhaps be exploited.

• Memoization and dynamic programming. If the algorithm has a recursive or iterative structure, it may be necessary to repeatedly evaluate a solution for the same state. Here, if we construct schedules in order, this state would consist of the set of yet-unscheduled performances, and a table showing the time of the last performance for each participant. Sometimes, a time–memory tradeoff can be useful, where we avoid repeated evaluation by caching the results of evaluating each state.

However, rather often it is not necessary to find an optimal solution. A good-enough solution might be sufficient, and can often be constructed much more cheaply. Some techniques that could be useful:

• Heuristics. Even if a heuristic is not admissible, it might still be useful in practice. A non-admissible solution might not guarantee that it will find the optimal solution, but it could still lead to a good-enough solution.

• Greedy algorithms. Greedy algorithms tend to perform fairly well in practice. These algorithms are based on the heuristic of choosing the locally best option at each step, in the hopes of this option also being the global best.

However, this particular scheduling problem might lead a naive greedy algorithm to find some of the worst possible solutions: while it could maximize the minimum gap at the beginning, the fewer remaining options only allow much smaller gaps near the end.

• Local optimization. Sometimes, a set of local transformations can be applied that are guaranteed to improve a candidate solution (but not guaranteed to find the optimum solution via repeated application). For example, such local optimizations could involve swapping two performances in the schedule.

• Random sampling. If you cannot evaluate all potential solutions, randomly sampling some of them can be useful. These need not be uniformly random. The distribution that you sample from can be informed by some heuristic. Randomly sampled solutions are especially useful as a starting point for local optimization.

• Anytime algorithms. An anytime algorithm will quickly find a candidate solution (that fulfils all constraints), but will find better solutions the longer it runs. It can be stopped at any time to get the current-best solution. This allows users to decide how much computation resources they want to invest into finding a better solution.

Here, I think a good-enough algorithm can be constructed as follows:

• We have a heuristic that gives us an upper bound for the minimum gap size (dividing remaining performances by the most active participant's remaining performances). We also have a lower bound: the gap size would be zero if one participant's performances occur back to back.
• Given a minimum gap size, we can create a greedy algorithm that tries to assemble a schedule honouring that gap size. The larger the gap size, the more difficult it is to find a solution, but the more alternatives we can prune during the search. The smaller the gap size, the easier it is to find at least one solution.
• We can now find a good (but maybe not best) solution by running a binary search over gap sizes. If our greedy algorithm finds a solution for that gap size, we have a new lower bound. If it fails to find a solution, that is a new upper bound (exclusive).

The inner greedy algorithm would create schedules by selecting one performance at a time. This requires that we have a concept of the “best” performance at that time. The next performance must satisfy the minimum gap size constraint. Of these, we should prioritize selecting performances where the participants have more remaining performances. After selecting the next performance, we recursively invoke the greedy algorithm to create a schedule over the remaining performances. If that fails, we re-try with the second-best next performance, and so on. We might limit the number of re-tries to avoid expensive searches. For example, an algorithm that dynamically allocates the available evaluation budget to the recursive cases might look like:

``````class Time(int): pass

class Participant: pass

class Performance:
participant: set[Participant]

def bounded_greedy_search(
performances: set[Performance],
last_performance_time: dict[Participant, Time],
remaining_performances: dict[Participant, int],
time: Time,
budget: int,
mingap: int,
) -> list[Performance]:
if not performances:  # base case
return []

def performance_is_permissible(candidate: Performance) -> bool:
"""Whether the performance can be scheduled at this time."""
for p in candidate.participants:
if last_performance_time[p] + mingap > time:
return False
return True

def performance_priority(candidate: Performance) -> int:
"""Performances with lower priority should be attempted first."""
return -max(remaining_performances[p] for p in c.participants)

candidates = sorted(
filter(performances, performance_is_permissible),
key=performance_priority,
)

for c in candidates:
# consume budget for this candidate
budget -= 1

# do we have enough budget for further evaluation?
candidate_budget = len(performances) - 1
surplus_budget = budget - candidate_budget
if surplus_budget < 0:
return None

# allocate half the surplus budget (rounded up) to this candidate
candidate_budget += surplus_budget - surplus_budget // 2
budget -= candidate_budget

# adjust state for the call
performances -= c
saved_last_performance_time = {}
for p in c.participants:
saved_last_performance_time = last_performance_time[p]
last_performance_time[p] = time
remaining_performances[p] -= 1

solution = bounded_greedy_search(
performances - candidate,
last_performance_time,
remaining_performances,
Time(time + 1),
budget=candidate_budget,
mingap=mingap,
)

# restore state so that another candidate can be tried
performances += c
last_performance_time.update(saved_last_performance_time)
for p in c.participants:
remaining_performances[p] += 1

# did we get a solution for this candidate?
if solution is not None:
return [*solution, c]

# no solution was found
return None
``````
• Thank you so much for all of the excellent suggestions! I used some of these techniques to try to narrow the solution space, but it's still far too expensive to explore most possibilities. I had a bit of difficulty implementing the budgeting approach effectively so I am currently working with the simulated annealing strategy recommended by Philip Kendall instead, but this is all really valuable insight into the problem and helps immensely. Very much appreciated, thank you!! Feb 23 at 21:36