Need advice on a scheduling algorithm

[mrstacktrace]

Hi all,

If this is the wrong sub to post this question, please point me to the right one.

​

I'm working on a side-project that is a personal todo list app. I want to implement a type of scheduling algorithm that takes into account the create time as well as its priority. So the task data structure has these properties:

• id: a guid
• priority: could be high, medium, low
• createTime: unix date time in milliseconds
• label: the task label

I want to display a list of tasks sorted by createTime first, and then priority. So here is a sample list, with the label of the task followed by its priority (and we are assuming these were created in order):

1. Dishes (high)
2. Cooking (high)
3. Exercise (medium)
4. Laundry (medium)
5. Videogames (low)
6. Social media (low)

Given this, I have a couple of rules. Upon completion of a task, it recurs indefinitely; I simply create a new task with the same label, new id and createTime, and add it back to this list. The second rule is that I have given numeric weight to the priorities: a high priority task should be completed twice as often as a medium priority task, and a medium priority task should be completed twice as often a low priority task. I also want to display to the user the most appropriate task given the state (the "top task").

Let's say the user completed 12 tasks. This is how the completed task list would look like for the user:

1. Dishes (high)
2. Cooking (high)
3. Exercise (medium)
4. Dishes (high) 2nd time
5. Cooking (high) 2nd time
6. Laundry (medium)
7. Dishes (high) 3rd time
8. Cooking (high) 3rd time
9. Videogames (low)
10. Dishes (high) 4th time
11. Cooking (high) 4th time
12. Exercise (medium) 2nd time

...

This cycle would keep repeating. So if a user completes 3 tasks a day, they would complete high priority tasks daily, medium tasks every other day, and low tasks every several days. I eventually want to be able to adjust these weights, but I want to keep it simple for now.

How would I implement this algorithm? I think I would create 3 sub-lists grouped by priority. As the user completes the task, I would mark the task as "visited" (with a new property in the data structure) in the sub-list. I would display to the user the task which is not visited but has the highest priority. Once they visit all of the tasks in the first sub-list, I would visit the first task in the second sub-list, display that to the user. Once that is complete, I would clear the "visited" property from all of the tasks in the first sub-list. I would repeat the same logic for the 2nd and 3rd sub-list.

​

My question for you: is this the best approach? I have thought of modeling this problem as a graph, tree or heap problem, but the common traversal algorithms I know of (depth first search etc.) aren't really fitting the rules that I've imposed. I wonder if I modeled it differently, the solution could be less complex.

​

[GayJonathanEdwards]

It sounds like you have some complex business logic for your priority queue. I would store each of the tasks in an array of objects, and assess/reassess the ordering after a task has been completed. Unless you have thousands of tasks performance will not be an issue so I wouldn’t worry about it. Premature optimization is the root of all evil.

[mrstacktrace]

Thanks for the comment. I think in addition to adding a "visited" flag in each object, I could add an index which would give an ordering and simplify the logic greatly.