2

Problem:

Given a set of recurring tasks, and knowing how long each take will take and how often they must recur, create a schedule that most evenly spreads out the time to do the tasks.

For example, I have to "run antivirus", "defragment hard drive", and "update computer" every 2 days, I have to "update hardware", "clean internals" every 3 days, and I have to "replace hard drive", "replace graphics card", "replace cpu" every 5 days. Each chore takes a certain amount of time, in minutes.

Given this information, what days in the month should I do each chore?

Attempts:

I have "solved" this problem twice, but each solution will take over 1 million years to compute.

First algorithm I used generated all possible "days", ie, every combination of tasks that could be run. Then, for every possible combination of days in a month, I checked the month to see if it fit the constraints (tasks run every x days, day is evenly spread). This is the most naive approach and would have taken python longer than the age of the universe to check.

The algorithm I'm currently running would also work. It generated every possible "day plan" across the month for each task, ie, I could run a every-5-day task starting on the 1st, 2nd, 3rd, 4th or 5th. Then, for every combination of every day plan, I add up the day plans to form a month plan. I then sum up the times of each task in every day of that month to see how it fares. This algorithm must run through 1e14 combinations, which might be possible if written in a compiled languages and executed in parallel across a huge cluster for a few days...

Summary

I would like to know if there's a better way to do this. To summarize, I have some tasks, that must recur every x days, and want to spread them across a given month so that each day is filled with the same amount of time on these tasks.

Thank you.

DanRedux
  • 9,119
  • 6
  • 23
  • 41
  • 1
    Sounds like scheduling problem... http://stackoverflow.com/questions/2162397/are-all-scheduling-problems-np-hard – Cheruvian Jul 07 '14 at 04:05
  • Could one apply GA algos here? – James Mills Jul 07 '14 at 04:07
  • @user1594030 Yep, that's exactly it. So it's a whole field and I'm going to have to dig deep to find good algorithms, hmm? Dang. – DanRedux Jul 07 '14 at 04:08
  • Usually you can defeat NPHard problems by defining better rules, or just fudging it. But computers will work too hard and be too literal if you ask it for a BEST solution. – Cheruvian Jul 07 '14 at 04:09
  • Scheduling is hard like the knapsack problem is hard, but this isn't about finding an optimum scheduling, per se. This sort of optimization seems fuzzier. – David Ehrmann Jul 07 '14 at 04:11
  • This involvement of months causes a problem to me thinking about this, can you assume every month is 30 days? – asimes Jul 07 '14 at 04:15
  • Yes, sorry, every month is 28 days in my problem. Any extra days would be unscheduled days. – DanRedux Jul 07 '14 at 04:24

2 Answers2

0

My first stab at this is recognizing this schedule will be periodic, so determine what the schedule period is (the LCM of all the periods). From there, you can think of everything like a Gantt chart. For each task, you need to pick a phase offset that maximizes the distance between start times across tasks. I'm not sure you can compute it algebraically, but you could run gradient descent on it.

David Ehrmann
  • 7,366
  • 2
  • 31
  • 40
0

You could try out some local search algorithms (e.g. hill-climbing, simulated annealing).

Basically you start out with a candidate solution (random assignment of tasks), evaluate it (you'll need to come up with an evaluation function) and then check each of the neighbor states' values and move to the one with the highest value. The neighbor states could be all states in which one of the tasks is moved one day to the future or past. You repeat this until there is no more improvement of the states value.

Now you should have found a local maximum of the evaluation function which is probably not yet the optimal solution. However since the algorithm is very fast, you can repeat it very often with varying starting assignments and find a good solution anyway. You can "soften" the greediness of the algorithm by including random steps as well.

cbg
  • 68
  • 3
  • What is the best way to find the global maximum? While local maximum's are useful and I have a good fitness metric, I would eventually like to find the global maximum. – DanRedux Jul 07 '14 at 16:10
  • Local search can also find the global maximum, of course, it's just not guaranteed (well, for t -> infinity it is). It's possible that you'll find the global maximum right away, but it depends a lot on the "fitness landscape" of the actual problem. But for very hard problems, where enumeration or other approaches aren't feasible, a good solution is much better than none at all. Plus, it's easy to implement and really fast. – cbg Jul 08 '14 at 07:40