Algorithm for scheduling a set of real life tasks that are input by the user

Question

I am trying to write some code to schedule a set of real life tasks that are input by the user. These tasks are stored in an SQLite database. And at the moment, the only parameters I am taking into consideration are the,

The project to which a task belongs to --> p 
The name of the task itself --> t
And the due date for this task --> d

The project and due date parameters are optional. But assuming that the user will always input at least the task name and due date for every task.. I was wondering if it is possible to schedule the set of tasks using a scheduler like the Completely Fair Scheduler (CFS) for example. I realize that the CFS was written for scheduling tasks with much finer granularity (nanoseconds) than the set of tasks being proposed for this purpose... But I realized that it might be possible and maybe more efficient if I can modify it to work with tasks that are on the same time scale as our perception of time.

A typical entry in the database would be in the format (p, t, d). 'p' is optional. Here are a few examples:

(_, 'Call home', 29/2/2012)
(Work, 'Meet boss', 14/3/2012)
(Work, 'Ask for raise', 18/3/2012)
(_, 'Book tickets', 10/3/2012)
(Work, 'Quit', 14/4/2012)
(Personal, 'Get botox injections', 10/3/2012)
(Personal, 'Get breast implants', 10/10/2012)
(_, 'Dad bday', 7/10/2012)

Here is a situation to consider. I would like to wake up in the morning. Run this "yet to be coded" algorithm on the set of tasks.. like the ones given above.. and I would like to receive a schedule for the rest of day, that maximizes throughput. At a later stage, I would like to pass arguments to this algorithms that would allow me to control the scheduler to return a set of tasks depending on my current situation. Like if I am at work, I want to be able to pass arguments to the algorithm, to ask it to only return tasks that can be completed at work..

I hope I am able to convey the gist of it. I understand that the due date alone is not sufficient to schedule tasks using the CFS for example... but if there are other parameters that I should consider, please do let me know. And any suggestions for the kind of scheduling algorithm to employ would be helpful.

Answer 1

This is something I've long desired as well. But a kernel scheduler only has to decide what task to run right now, not when in the future to run other tasks. So those schedulers may help you with part of the problem, but there is a lot more here than they solve. And they have a key bit of information you aren't keeping; namely if a task is blocked or not. (Actually, the kernel is going to track process states, I'm over simplifying here.) You're going to need to know what a task is blocking on so that the user can tell you if the task is unblocked.

If you want to be able to schedule out your day, you're going to have to include an estimate of the time remaining for a task.

You'll want to tie task dependencies into it as well. And that's not even getting into scheduling things with external events like 'order book' -> 'wait for it to arrive' -> 'read book' prior to ordering the book.

I think you're going to find that the problem gets deep quickly, and that having a well-thought-through and always with you UI is going to be critical.

Answer 2

Okay, I've given some thought to it. This is how I imagine to accomplish it..

Assuming there is a set of tasks..where each task has,

A deadline
Time taken for completion
Time spent on the task so far

I intend to represent those set of tasks as a genetic chromosome. Each chromosome will be encoded with an arbitrary number of tasks. The fitness of each chromosome will be determined by a fitness function that rewards chromosomes that have a set of tasks nearing the deadline and still incomplete. It also rewards tasks that haven't been given any attention in the recent past.

The fitness function punishes those tasks whose deadline is far away and those tasks that have had far more access to my attention (assuming I am the CPU) in the recent past.

My understanding is that.. the consequence of performing the above steps is that after a few generations it might be possible to arrive at a chromosome which has a set of tasks that is...

• nearing its deadline
• hasn't been given attention in the recent past
• have the greatest probability of being completed in the given time (What I mean by this is that, if I ask the algo to give me a schedule for 3 hours then the winning chromosome must contain tasks that can be accomplished in that time frame)

Could someone please comment on my approach? Do you think it might work? I don't intend to take into consideration the dependencies between various tasks at the moment. I would like to get a bare functioning prototype to a working stage, after which I can recursively improve the algorithm...

Thanks.

Answer 3

In order to find a somewhat optimal order of your task, you should at least include the parameters earliest start time and duration. Provided you have these time windows, you can further define a time window for each project. By default, the project time window could be the whole day.

Consider for example the section "Work": if it lies between 8 o'clock and 17 o'clock your application can filter all tasks that lie between the time span. If you want to schedule a whole day, you have to write an algorithm, that tries to find a solution in which no time windows violations occur. You can even build in an optimization criterion like: ,,minimize the distance between the actual start time of a task and its earliest start time"

Answer 4

How about just making it simple: earliest deadline first (EDF) scheduling. It's been well-researched and has a simple theory behind it that also lets you compute utilization and feasibility.