4

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.

Improve this question
6
  • How are you going to handle dependencies between tasks? It's no good to schedule a take puppy to the vet task before the buy a puppy task.
    – FrustratedWithFormsDesigner
    Mar 1, 2012 at 17:03
  • Is cross posting a problem? Are you really saying that all the questions in all the sub stacks are really distinct and different? Well, regardless.. its your vote. So I cannot care less. If you have to close.. so be it!
    – Jay
    Mar 1, 2012 at 21:29
  • 3
    @AJ. Yes, cross posting is discouraged. The different sites are designed to be independent and non-duplicate in their coverage. Much deliberation goes into this at Area 51.
    – Kris Harper
    Mar 2, 2012 at 2:38
  • johndcook.com/blog/2012/03/02/life-off-the-clock
    – Job
    Mar 3, 2012 at 18:03
  • For some, managing time does not necessarily lead to rigid regimentation. Rather, it is a way to organize a finite commodity. If there are 'x' things to do in a life that lasts 'y' years, then knowing which 'x' to spend your 'y' on, becomes rather important.
    – Jay
    Mar 3, 2012 at 18:08

4 Answers 4

Reset to default
4

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.

Improve this answer
2
  • I don't want to be getting into fine details of a typical task. The way I envision it, the tasks themselves would be described at a fairly abstract level. So something like 'order book' -> 'wait for it to arrive' -> 'read book' would simply be 'get book to read'. And once I've read the book, the task gets ticked off as completed and requires no more scheduling. The task that is blocked can be manually marked as being blocked. Instead of time remaining I believe it be better to put tasks in different queues depending on whether it is a short, medium or long term task and schedule accordingly..
    – Jay
    Mar 1, 2012 at 21:33
  • I plan on using a command line UI to begin with. I was also considering a REPL. So the user can use it, work on his tasks and then quit.. I apologize for another comment. but the character limit restriction is too constricting.
    – Jay
    Mar 1, 2012 at 21:37
0

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.

Improve this answer
-1

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"

Improve this answer
1
  • 1
    I don't think there is any real benefit to using exact duration for tasks that operate on our time scale. Besides, it is difficult to represent the duration down to a single number. I think it would be better to represent the duration as short, medium or long term. The earliest start time would be the 'due date' itself. I'm think of using a flag to mark a task as being doable even before the due date...
    – Jay
    Mar 1, 2012 at 21:44
-2

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.

Improve this answer
4
  • The primary factor in EDF is the deadline. But I want an algorithm that optimizes for deadline of the task, time available for me to complete the task and the staleness of the task itself. Staleness is a measure of how long I haven't given attention to a certain task..
    – Jay
    Mar 4, 2012 at 11:14
  • Then you have to define WHAT METRIC do you want to optimize. You need to assign weights to these criteria so that each task is represented by a single number, and then you simply put them in a priority queue and pop them one by one. (Actually, you don't even need to reduce the criteria to a single number, you can devise a total ordering over the triples and use that as the heap criterion.)
    – zvrba
    Mar 4, 2012 at 11:30
  • 2
    Could you please elaborate what you mean when you say "you can devise a total ordering over the triples and use that as the heap criterion"...?
    – Jay
    Mar 6, 2012 at 19:19
  • Devise a way of deciding when (p1,t1,d1) < (p2,t2,d2). (Or greater than, whatever.) Heaps are briefly described here: en.wikipedia.org/wiki/Heap_(data_structure) and properties of total ordering are listed here: en.wikipedia.org/wiki/Total_order
    – zvrba
    Mar 6, 2012 at 21:13

Not the answer you're looking for? Browse other questions tagged or ask your own question.