Schedule tasks from a weighted list with time frame constraints

Question

I'm attempting to create an automatic scheduler from a list of tasks I have available. Here are the key points:

• Each task has been given a priority beforehand and the algorithm should try to maximize the total 'priority points' it can get from the tasks it schedules.
• There should be no overlap between any tasks.
• Each task might have several time constraints.

Here's an example:

$$ \begin{array}{c|c|c|c} \text{Task} & \text{Duration (min)} & \text{Time Frames} & \text{Priority} \\ \hline \text{Read a book} & 80 & \text{5:00pm-8:00pm} & 2 \\ \text{Go to the store} & 45 & \text{5:00pm-7:00pm} & 5 \\ \text{Eat popcorn} & 15 & \text{6:00pm-8:00pm} & 1 \\ \text{Ask the internet} & 25 & \text{5:00pm-6:00pm,7:00pm-8:00pm} & 8 \\ \text{Exercise} & 60 & \text{5:00pm-7:00pm} & 6 \end{array} $$

And a schedule it could make would be (each character is 5 mins): | 5:00-6:00 | 6:00-7:00 | 7:00-8:00 | | Store || Exercise | |Ask||E| | Which scores a total of 20 points (which I believe is the maximum in this example)

I realize this problem may be NP-Hard so, because of the nature of this project, the solution doesn't need to be optimal.

What I've come up with so far is something like the following:

1. Sort the task list based on priority (t*lg(t))
2. Find each 'block' of time, divided on each time frame boundary of the tasks (t) and store in a set. Then sort the set (f*lg(f)).
3. For every block, attempt to place a task, starting with the highest priority, at the earliest point available in the block. Repeat until there is no room for any task in the block. (t)
4. Extend the end of the block to the end of the next block and repeat 3. If no task can fit into the earliest point, move the earliest point to the beginning of the next block used for the beginning. (For instance, block 1 is filled as much as possible, so it is expanded to the beginning of block 1 to the end of block 2. No tasks can start at the beginning of the remaining space between blocks 1 and 2, so it moves the beginning of the active block up to the beginning of block 2).
5. Repeat 4 until there are no more blocks. (f)

Total: f*t + f*lg(f) + t*lg(t)

This greedy algorithm doesn't seem ideal and it will certainly fail horribly in some scenarios (such as a 60 min, high priority task from 1:00-3:00, and a lower priority task from 1:00-2:00). What is the best way to approach this problem?

Answer 1

This smells like it's probably NP-hard, but for the number of tasks you are likely to have in real life, there are reasonable algorithms to compute the best solution.

For instance, you could solve this using integer linear programming. Take the LCM of all durations, so that each task takes an integer number of time slots (in your example, the LCM is 15 minutes, so each slot is 15 minutes long). Now introduce zero-or-one variables $x_{i,j}$, with the intended meaning that $x_{i,j}=1$ if your schedule starts doing task $i$ at time slot $j$. You can add linear inequalities to require that no two tasks be scheduled at an overlapping time (e.g., $x_{i,j}+x_{i',j}\le 1$ and so on), and linear inequalities to require that each task be performed within its allowable time frame (e.g., $x_{i,j}+x_{i,j+1}+\dots +x_{i,j'} \le 1$; $x_{i,j''}=0$ for all other $j''$). Finally, introduce an objective function that captures the total score of your solution, $\sum_{i,j} c_i x_{i,j}$, where $c_i$ is the priority of $i$.

Finally, solve this ILP using an off-the-shelf ILP solver. I expect that in practice, with a reasonable number of tasks this will often find an exact optimal solution. And even if the number of tasks is too many to find an exact solution, many ILP solvers have a mode of operation that will tell them to output the best solution they found so far after (say) 5 minutes of CPU time.

Answer 2

I'd be inclined to punt the problem to an integer linear programming problem solver. (Note that many solvers will take a timeout argument that'll return the best solution they've found so far if/when the timeout triggers)

Encode each task as a rational (or potentially integer, depending) for the time of the start of the task and a boolean for if the task is going to be done, with appropriate bounds constraints predicated on if the task is going to be done (note that when you have multiple possible time slots for a task you'll need to encode the bounds as "at least one of these time slots are valid").

Then for each pair of distinct tasks add a constraint that either the first task starts after the second one finishes or vice versa.