3
$\begingroup$

I want to solve the following scheduling problem: We have $N$ resources and $\binom{N}{2}$ tasks, such that every task requires exactly two resources and every pair of resources is required by exactly one task. The number of resources $N$ and the durations $t_i$ of each task are the input. Output is smallest possible $T$ and a list of starting times $T_i$ for each task, such that

  • $T_i \geq 0$ for each $i$.
  • If tasks $i$ and $j$ share a resource, then either $T_i+t_i \leq T_j$ or $T_j + t_j \leq T_i$.
  • $T_i + t_i \leq T$ for each $i$.

Is there a practical algorithm for this, let's say for $N \leq 10$? We can assume that the durations are integers, let's say at most $200$.

A more general case of the scheduling problem would be one where each task is allowed to use any number of resources there is no constraint on how many tasks use each resource. However, I couldn't find even that problem anywhere.


Example input with $6$ resources (A,B,C,D,E,F): The number in row $i$ column $j$ is the duration of the task that requires resources $i$ and $j$. $$ \begin{array}{rrrrrrr} & B & C & D & E & F \\ A & 112 & 2 & 2 & 2 & 2 \\ B & & 2 & 2 & 2 & 2\\ C & & & 40 & 38 & 38 \\ D & & & & 38 & 38 \\ E & & & & & 40 \end{array} $$

Example output: total duration $124$ and schedule as follows: $$ \begin{array}{rrr} \text{start} & \text{end} & \text{task} \\ 0 & 2 & B-F \\ 0 & 2 & A-D \\ 2 & 4 & B-C \\ 2 & 4 & A-E \\ 4 & 6 & A-F \\ 4 & 6 & D-B \\ 6 & 118 & A-B \\ 6 & 44 & C-F \\ 6 & 44 & D-E \\ 44 & 84 & C-D \\ 44 & 84 & E-F \\ 84 & 122 & C-E \\ 84 & 122 & D-F \\ 122 & 124 & A-C \\ 122 & 124 & B-E \end{array} $$


Background: Our chess club organized a small one-evening tournament with the following idea:

  • There are $N$ players, and everyone plays against everyone exactly once.
  • Each player is given a budget of, say 60 minutes, which he allocates to all his $N-1$ games before the tournament. For example, he may decide to have 20 minutes against player A, 30 minutes against player B, 5 minutes against player C and 5 minutes against player D. For practical purposes, everyone has to allocate at least one minute against each player.

The maximum duration of the game A vs B is the time A allocated against B plus the time B allocated against A. We want to finish the tournament as quickly as possible, assuming all time is used in each game. Multiple games can be played at the same time but "rounds" are not needed, so games can start whenever two players are free, and it does not matter if player A plays 3 games before player B finishes his first game.


My ideas: I settled for a genetic algorithm where an individual is an ordered list of the $\binom{N}{2}$ games. A list corresponds to a schedule which is made by going through the games in the list and scheduling each game as early as possible. The initial population is taken from randomized standard round-robin pairing tables. Sometimes the genetic algorithm finds a solution that is better than one obtained by standard round-robin tables, but it's hard to say if the best solution found is actually best possible or not, so I'd prefer an exact algorithm.

A trivial lower bound for the duration of the tournament is the sum of lengths of games of a player (which may vary from player to player if everyone decides to allocate more time against a certain player), but that lower bound is not always achievable.


Variations: An interesting variation occurs if we take into account that games may end early. When a game ends, the ending time is entered to a computer which then calculates a new schedule for the remaining games, possibly ending earlier than the previous schedule. I guess this can be done by scheduling the remaining games using the same algorithm used for the whole tournament. However, while it is no problem if the initial scheduling takes a minute or two, as there are other things to do before the start of the tournament, but it would be nice to have the schedules appear very quickly if the algorithm is run in the middle of the tournament, so nobody has to wait for that.

$\endgroup$
  • $\begingroup$ 1. I don't understand the problem. What is the input to your algorithm? What is the output? Is it the algorithm's job to choose the budget for each player? Or is each player's time budgets supplied as input to the algorithm? 2. It seems like the answer is that the tournament will always take a total of exactly $60N$ minutes to play all games. What am I missing? Are some games played in parallel? If so, what are the rules on which games can be played in parallel? Is it just "if the players don't overlap, the two games can be played in parallel"? $\endgroup$ – D.W. Dec 27 '14 at 2:04
  • 1
    $\begingroup$ 3. This looks like a job scheduling problem. Have you looked at job shop scheduling? 4. It sounds like maybe you are looking for an algorithm for the following task: given an undirected graph $G$, find a collection of matchings whose union is all of $G$, and minimize the sum of the weights of the matchings, where the weight of each matching is the maximum weight of any edge in the matching. A greedy algorithm might give a reasonable approximation. $\endgroup$ – D.W. Dec 27 '14 at 2:10
  • $\begingroup$ @D.W. I edited the question to make it probably more clear. If not: 1. Game durations are the input, talking about budgets etc. are unnecessary background, which some people apparently want me to give in SE questions. 2. Yes, games can be played in parallel. A player can have at most one game running at a time. 3. I looked at job shop scheduling, but did not find anything with resources. 4. I think that would be finding a schedule for a normal tournament with rounds (i.e. round 1 where each player plays their first game, round 2 where each player plays their second game etc.). $\endgroup$ – JiK Dec 27 '14 at 8:51
1
$\begingroup$

Another option is using an SMT (SAT modulo theories) solver such as Z3 or MathSAT. The constraints you give are a boolean combination of constraints in linear arithmetic, which is one of the bread-and-butter theories for these tools. The formula you would hand to the solver is essentially what you wrote:

$\varphi := \bigwedge_i(T_i\ge 0 \wedge T_i+t_i\le T) \wedge \bigwedge_{i<j}(T_i+t_i\le T_j \vee T_j+t_j\le T_i)$.

Note that doing it this way, you still have to try different values for $T$ (SMT solvers check satisfiability, they don't directly allow you to specify an objective to be minimized). In principle, you could encode the minimality requirement into additional constraints (using boolean algebra transformations and Farkas' lemma), but this complicates things a bit.

$\endgroup$
0
$\begingroup$

You could find a schedule using a SAT solver.

We have ${N \choose 2}$ games. Let $\ell_g$ denote the length of game $g$.

Let's formulate this as a SAT instance. For each game $g$ and each time $t$, we have a variable $x_{g,t}$ that is true if game $g$ starts at time $t$, and a variable $y_{g,t}$ that is true if game $g$ is ongoing at time $t$. Note that if $g$ starts at time $t$, then it will end at time $t+\ell_g$, so we have

$$x_{g,t} \implies (y_{g,t} \land y_{g,t+1} \land \dots \land y_{g,t+\ell_g-1}).$$

Now for each pair of games $g,g'$ that share a player in common, we add a constraint that indicates that $g,g'$ should not be ongoing at the same time. We can do this by adding a clause of the form

$$(\neg y_{g,t} \lor \neg y_{g',t})$$

for each $t$ and each such pair of games $g,g'$.

Finally, suppose we'd like to know if is possible to finish the tournament by time $T$. We can enforce this by adding a clause of the form

$$(x_{g,0} \lor x_{g,1} \lor \dots \lor x_{g,T-\ell_g})$$

for each game $g$.

Feed this set of clauses to a SAT solver, and see whether they are all simultaneously satisfiable. If they are, then you have a schedule that finishes within $T$ units of time (the satisfying assignment immediately gives you a schedule for your tournament).

Our last job is to minimize $T$. We can do this by binary search, repeatedly invoking the SAT solver until we find the smallest value of $T$ for which you can find a valid schedule.

Given the effectiveness of modern SAT solvers, I suspect this might be reasonably effective if the number of players in your club is not too large. But the only way to find out for sure is to implement it and see. (If this is not effective, there are probably approximation algorithms you could use to get an approximately-optimal schedule -- but start here, as if this approach works, it will give you an exactly optimal schedule, and without requiring too much deep thought on your part.)

$\endgroup$
  • $\begingroup$ You could also use an SMT solver, which can handle the arithmetic constraints directly. $\endgroup$ – Klaus Draeger Jan 26 '15 at 13:46
  • $\begingroup$ @KlausDraeger, fascinating! I don't know enough about SMT solvers to see immediately how to do that -- would you like to add an answer, or edit mine, to show the details? Thank you for the helpful comment! $\endgroup$ – D.W. Jan 26 '15 at 19:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.