Schedule tasks from a weighted list with time frame constraints

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:

• Sort the task list based on priority (t*lg(t))

• 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)).

• 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)

• 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, s

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.

StackExchange Computer Science Q#47901, answer score: 2