?
Solved

Brute Force Algorithm for Scheduling Events

Posted on 2003-03-28
9
Medium Priority
?
680 Views
Last Modified: 2011-09-20
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
Comment
Question by:DragXSlay
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
9 Comments
 
LVL 1

Expert Comment

by:sparticus1701
ID: 8228291
That depends.  When is your assignment due?
0
 
LVL 2

Author Comment

by:DragXSlay
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

by:sparticus1701
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
Industry Leaders: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
LVL 11

Expert Comment

by:pratap_r
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?

please clarify..

+pratap

0
 
LVL 8

Expert Comment

by:akshayxx
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

by:kiamchong
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

by:sparticus1701
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

by:modulo
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

When you agree or disagree, please add a comment here.

Thank you.

modulo

Community Support Moderator
Experts Exchange
0
 

Accepted Solution

by:
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

Get 15 Days FREE Full-Featured Trial

Benefit from a mission critical IT monitoring with Monitis Premium or get it FREE for your entry level monitoring needs.
-Over 200,000 users
-More than 300,000 websites monitored
-Used in 197 countries
-Recommended by 98% of users

Question has a verified solution.

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

In this post we will learn how to make Android Gesture Tutorial and give different functionality whenever a user Touch or Scroll android screen.
Q&A with Course Creator, Mark Lassoff, on the importance of HTML5 in the career of a modern-day developer.
An introduction to basic programming syntax in Java by creating a simple program. Viewers can follow the tutorial as they create their first class in Java. Definitions and explanations about each element are given to help prepare viewers for future …
Viewers will learn how to properly install Eclipse with the necessary JDK, and will take a look at an introductory Java program. Download Eclipse installation zip file: Extract files from zip file: Download and install JDK 8: Open Eclipse and …
Suggested Courses

741 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question