Sorting tasks to assign

Sorting tasks to assign

I've got a problem that I don't know where to start. I'd realy appreciate some help.

The problem:

I have several T task that must be done in D days by just 1 employee (let's forget using several resources right now). Each task can be done in some times (not all tasks can be done all time). e.g.: If my employee starts working at 8 o'clock and one task is "call a client". Maybe the client office opens at 9 o'clock.

Also each task has a duration (really estimated). It is supposed that the D days are enough to do all task.

I've to sort the tasks to the employee. e.g.: at monday 8:00 do task 7, then at 9:30 starts with task 2. In the example task 7 duration would be 1 and a half hour.

Thanks for the help!

Diego

PD: If someone has a way to make this and it is not an algorithm never minds, please answer and I'll manage to think the algorithm. I just don't know how to face the problem.

Edit Would Project be usefull?

Edit 2 Tasks / Jobs dependency is NOT required

Answer by mb14 for Sorting tasks to assign

Your problem is a part of operations research problems. This topic has been massively studied and there is no simple algorithm from that. Those kind of scheduling problem are usually non-polynomial, so basically you have to try every combinations, but you can cut-off when a constraint is broken. I.e there is not need to try all the combinations starting by call the client a 8:00 if you know that you can not do it before 9:00.

So google stuff about operations research and constraint programming algorithms and combinatorial optimization.

Answer by Dialecticus for Sorting tasks to assign

You need to find out what is the input for your algorithm. Part of the input is list of tasks with duration for every task. Each task also has requirements:

• number of participants (currently always 1, but if that can change you need to think about it early)
• time periods that the task can be performed (currently time of day, but it can also be day of week, or even day of month)
• participants can have their own requirements (like working hours, but it could be something more)
• task can depend on some other task or tasks to be completed first

There could be more requirements. To discover what more you need you should try to solve some concrete problems by hand. While you try some more requirements may be discovered. Whatever the requirements are your algorithm should try to satisfy them in similar fashion like you did it by hand: one requirement at the time, and if some collide then trace back and try different route. Algorithm should start from most restrictive requirements first.

Answer by Patrick for Sorting tasks to assign

You can solve these kind of problems using constraint programming, provided the number of elements is not too big.

Take a look at ECLiPSe (see http://eclipseclp.org/).

Answer by Christian Severin for Sorting tasks to assign

If this is a "little part of an app" you might want to renegotiate with the client: Job shop scheduling is NP-complete (vulgo: gets real difficult real quickly with increasing complexity).
Some points to ponder:

• you need to assign some sort of "capacity" to the days, marking time intervals when some sort of task is possible (work start and work end of your employee, opening hours of other offices, etc.)
• you need to tell the different tasks (or jobs, as they are called) what sort of capacities they require, and for how long: tools needed, people to be reached, etc.
• you might need some sort of directional relationship between, say, job 17 ("call office XYZ and ask for cost estimate") and job 18 ("forward cost estimate to boss"): job 17 must be done before job 18 can be started.

When you google for "job shop scheduling" you'll come across more scientific papers than you'll ever want to read for a "little part of an app"...

(Disclosure: I work for a company that offers different tools to do just this sort of thing.)

Answer by Geoffrey De Smet for Sorting tasks to assign

Here's yet another library for these kind of problems: Drools Planner (open source, java).

Note that it solves all the requirements (=constraints) together, because especially if you have hard and soft constraints, you'll find that it's usually possible to solve all hard constraints, but impossible to solve all soft constraints (you still want to minimize them as much as possible).

Fatal error: Call to a member function getElementsByTagName() on a non-object in D:\XAMPP INSTALLASTION\xampp\htdocs\endunpratama9i\www-stackoverflow-info-proses.php on line 72