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
