?
Solved

Brute Force Algorithm for Scheduling Events

Posted on 2003-03-28
9
Medium Priority
?
691 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
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
The new generation of project management tools

With monday.com’s project management tool, you can see what everyone on your team is working in a single glance. Its intuitive dashboards are customizable, so you can create systems that work for you.

 
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

Never miss a deadline with monday.com

The revolutionary project management tool is here!   Plan visually with a single glance and make sure your projects get done.

Question has a verified solution.

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

This article will inform Clients about common and important expectations from the freelancers (Experts) who are looking at your Gig.
The SignAloud Glove is capable of translating American Sign Language signs into text and audio.
Six Sigma Control Plans
Loops Section Overview

601 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