"Best Fit" Algorithm Request && Teach A Man To Fish
-
It's similar to job scheduling, where the blocks are "jobs" (length of job = length of block) and the layers of the wall would represent the "machines" (number of layers = number of machines)
Wow: Looks like my question is akin to smacking a wasp nest with a cricket bat. Glad to see it sparked some convo. So with what I found that was suggested by Harold and Luc, it seems like I could get away with just a simple priority list and just do the fat jobs first. There are no dependencies (job x has to be done before job y), so there's nothing stopping me from doing the jobs in any order. But I'm not sold that this is the way to achieve the quickest completion time. I might be wrong but there might be some cases where this wouldn't work. So I'll have to look around a little more--fortunately the links and ideas given were a good step toward what I was looking for.
-
Wow: Looks like my question is akin to smacking a wasp nest with a cricket bat. Glad to see it sparked some convo. So with what I found that was suggested by Harold and Luc, it seems like I could get away with just a simple priority list and just do the fat jobs first. There are no dependencies (job x has to be done before job y), so there's nothing stopping me from doing the jobs in any order. But I'm not sold that this is the way to achieve the quickest completion time. I might be wrong but there might be some cases where this wouldn't work. So I'll have to look around a little more--fortunately the links and ideas given were a good step toward what I was looking for.
fishing season ain't over yet. :laugh:
Luc Pattyn [Forum Guidelines] [Why QA sucks] [My Articles]
Prolific encyclopedia fixture proof-reader browser patron addict?
We all depend on the beast below.
-
Wow: Looks like my question is akin to smacking a wasp nest with a cricket bat. Glad to see it sparked some convo. So with what I found that was suggested by Harold and Luc, it seems like I could get away with just a simple priority list and just do the fat jobs first. There are no dependencies (job x has to be done before job y), so there's nothing stopping me from doing the jobs in any order. But I'm not sold that this is the way to achieve the quickest completion time. I might be wrong but there might be some cases where this wouldn't work. So I'll have to look around a little more--fortunately the links and ideas given were a good step toward what I was looking for.
Here is a simple example where biggest job first does not yield the optimum: two machines; five jobs: 3,3,2,2,2 :)
Luc Pattyn [Forum Guidelines] [Why QA sucks] [My Articles]
Prolific encyclopedia fixture proof-reader browser patron addict?
We all depend on the beast below.
-
Wow: Looks like my question is akin to smacking a wasp nest with a cricket bat. Glad to see it sparked some convo. So with what I found that was suggested by Harold and Luc, it seems like I could get away with just a simple priority list and just do the fat jobs first. There are no dependencies (job x has to be done before job y), so there's nothing stopping me from doing the jobs in any order. But I'm not sold that this is the way to achieve the quickest completion time. I might be wrong but there might be some cases where this wouldn't work. So I'll have to look around a little more--fortunately the links and ideas given were a good step toward what I was looking for.
What will be the typical size of the instances of the problem that you want to solve? For up to about 20 jobs solving the problem optimally with branch and bound is still doable.. Otherwise, it seems that in practice it is usual to use a genetic algorithm or simulated annealing - both have a tweakable time/quality trade-off and without too much trickery you can make it so that the result is guaranteed to be no worse than that of the greedy algorithm.
-
What will be the typical size of the instances of the problem that you want to solve? For up to about 20 jobs solving the problem optimally with branch and bound is still doable.. Otherwise, it seems that in practice it is usual to use a genetic algorithm or simulated annealing - both have a tweakable time/quality trade-off and without too much trickery you can make it so that the result is guaranteed to be no worse than that of the greedy algorithm.
Eh... maybe 50 jobs. And the number of jobs keeps on growing too...
-
Eh... maybe 50 jobs. And the number of jobs keeps on growing too...
IMO the more jobs the more "biggest job first" gets nearer to the optimal solution. :)
Luc Pattyn [Forum Guidelines] [Why QA sucks] [My Articles]
Prolific encyclopedia fixture proof-reader browser patron addict?
We all depend on the beast below.
-
IMO the more jobs the more "biggest job first" gets nearer to the optimal solution. :)
Luc Pattyn [Forum Guidelines] [Why QA sucks] [My Articles]
Prolific encyclopedia fixture proof-reader browser patron addict?
We all depend on the beast below.
-
Eh... maybe 50 jobs. And the number of jobs keeps on growing too...
Ok with the code I gave earlier that would take more than a million years :) With a larger number of jobs, the greedy algorithm comes closer to the optimal solution, and there is a semi-greedy algorithm that is always* at least as good as the simple greedy algorithm but usually better: 1) Let
sbe the sum of all job-lengths and letboundbe(s+m-1)/m(wheremis the number of machines) 2) For each job in descending order (by length), assign it to the first machine where it wouldn't cause the sum of the lengths of the jobs assigned to that machine so far to exceedbound, if there is no such machine mark the job as "non scheduled". 3) If there are no jobs marked "non scheduled", return the schedule. 4) Otherwise, take the length (mlength) of the schedule of the machine with the shortest schedule, and take the length (jlength) of the smallest job. 5) Change theboundtobound+(jlength-(bound-mlength))(IOW, make it so that you could add the smallest job to the smallest schedule without exceeding thebound) 6) Make all jobs non-marked and go back to step 2. It is, of course, slower than the usual greedy approach, but (usually, at least) very fast compared to the optimal approach. It always terminates, becausejlength-(bound-mlength)can not be zero. If it were, that job would have been scheduled in step 2, so it wouldn't be the smallest "non scheduled" job. So theboundwill grow until everything fits (potentially in a sub-optimal way). * I have no proof, but after a large number of random tests I still had no disproof. But you could always run the usual greedy algorithm as well and take the best result, it takes essentially no time anyway. edit: I didn't make this up myself, btw.modified on Monday, April 19, 2010 7:26 PM
-
Wow: Looks like my question is akin to smacking a wasp nest with a cricket bat. Glad to see it sparked some convo. So with what I found that was suggested by Harold and Luc, it seems like I could get away with just a simple priority list and just do the fat jobs first. There are no dependencies (job x has to be done before job y), so there's nothing stopping me from doing the jobs in any order. But I'm not sold that this is the way to achieve the quickest completion time. I might be wrong but there might be some cases where this wouldn't work. So I'll have to look around a little more--fortunately the links and ideas given were a good step toward what I was looking for.
An aerosol of solvent is my first choice for a wasps nest. No Smoking. No Electric. etc Tadeusz Westawic An ounce of Clever is worth a pound of Experience.
-
All, I'm in need of an algorithm that I have no idea about comparing it to other algorithms. Imagine if you had a set of wooden blocks, all the same thickness but differing in lengths. The goal is to stack all of the blocks in such a way that the total length of this "wall" is the shortest length possible. There would be a different result depending on if you stack the wall 2, 3, 4, or N blocks high. The wall doesn't have to be perfectly straight on both sides either. Not sure what this is even similar to, and would appreciate some guidance. I'd also appreciate knowing where some of you look for information about algs, because it seems like I can never find a comprehensive site containing the names, applications and descriptions of common or more obscure ones. If any of you want to give up your sources, your secrets are moderately safe with me :) Thanks, Michael Fritzius
Hello All, I was just stopping-by to make a rare post and I poked into this thread. In my mind I think of these kinds of problems as 'least energy state' problems. These very often correlate to conditions in analog setttings. By thinking one's way forth-and-back through analog-digital conversions, some unnoticed feature of the problem often presents itself. Your analogue thougtht-picture of blocks in a tall wall is an example. I imagined myself with a large appliance box and spheres of varying diameter representing the jobs. With spheres in the box I shake the box, stop, note the arrangement of spheres, and repeat. Anyone else with a thought picture? Tadeusz Westawic An ounce of Clever is worth a pound of Experience.
-
your problem seems somewhat similar to the Knapsack problem[^], and Wikipedia (or Google) are a good place to start your search. :)
Luc Pattyn [Forum Guidelines] [Why QA sucks] [My Articles]
Prolific encyclopedia fixture proof-reader browser patron addict?
We all depend on the beast below.
Yes, I agree with you