Solved

# Brute Force Algorithm for Scheduling Events

Posted on 2003-03-28
Medium Priority
691 Views
You're given an array that contained a series of tasks, the time the tasks completes and the time the task begins.  How can you efficiently determine which events to schedule if you were trying to schedule events for the most time possible.  Obviously begin and end times cannot conflict.
0
Question by:DragXSlay

LVL 1

Expert Comment

ID: 8228291
That depends.  When is your assignment due?
0

LVL 2

Author Comment

ID: 8228322
I could tell you that it's not an assignment, but it's not worth my time and you wouldn't believe that anyway.  I could explain what exactly I'm working on, but that also isn't worth my time.  So I'd like to thank you for taking the time out of your life to post something so utterly useless to both of us.  Hopefully you feel better about yourself and can move forward now.
0

LVL 1

Expert Comment

ID: 8228353
Please pardon the joviality.  It sounds a lot like an assignment I had in college.

If your software isn't under a running time constraint, here is a cool way to do it.  Use a genetic algorithm.

What you want is a "pool", which can be an array or heap of "organisms".  Each organism (in your case) would be an a sequence of bits, one for each task, and each bit could be turned on or off, meaning it would be included in the set.

You will want a function that tests the "fitness" of each organism, which basically is efficient your schedule is.

You can fill you pool with randomly created organisms, and then go through rounds of "mating".  When two organisms mate, they create a new organism who has a random combination of the parents "genes".  When each round is finished, you can test all the organisms, rank them by fitness, and kick out the least fit from the pool.  Once your new generations stop producing better results (maybe based on the most fit member of the pool), you break out.

This algorithm has the benefit of producing many good results, but it can take a while to run.
0

LVL 11

Expert Comment

ID: 8228545
DragXSlay, i am not sure i understood the problem correctly!, how many processors are we talking abt here. if it is just 1.. wouldn't a simple sort on the starting times work and eliminating the overlapping end time work?

+pratap

0

LVL 8

Expert Comment

ID: 8229014
>>>DragXSlay, i am not sure i understood the problem correctly
need to use brute force algorithm eliminates the sorting- solution.

0

Expert Comment

ID: 8235625
If I understand your problem correctly, you have an "Operation Research" problem. You have a bunch of over-lapping tasks and you are trying to pick out the most optimum set depending on your optimising function. I used to do this 20 years ago, so I can't help you with the algorithm, but you should be able to get some literature on "Operation Research"
Sparticus1701, your solution is interesting, although non-deterministic. You have to run a lot of simulations to pick out "good" solutions to implement. However I am not supprised, as complex scheduling problems ends up as n-degree differential equations in mathematics without any solutions!
0

LVL 1

Expert Comment

ID: 8238750
You are correct.  We recently implemented this algorithm on a project.  If you can imagine the problem in three dimensions, where two axes were two "genes", and the z axis is how good the combination is, then genetic is wonderful at finding solutions if the surface has multiple peaks, and not just one.

I think that oftentimes it is not a single schedule that is best, but multiple that are the same or near.  Genetic has the benefit of finding them all.
0

Expert Comment

ID: 8320256
Dear expert(s),

A request has been made to close this Q in CS:
http://www.experts-exchange.com/Community_Support/CleanUp/Q_20583318.html

Without a response in 72 hrs, a moderator will finalize this question by:

- Saving this Q as a PAQ and refunding the points to the questionner

Thank you.

modulo

Community Support Moderator
Experts Exchange
0

Accepted Solution

modulo earned 0 total points
ID: 8332479
Saving this Q as a PAQ and refunding the points to the questionner

modulo

Community Support Moderator
Experts Exchange
0

## Featured Post

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question