|
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
|
|
|
|
|
your problem seems somewhat similar to the Knapsack problem[^], and Wikipedia (or Google) are a good place to start your search.
|
|
|
|
|
|
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)
|
|
|
|
|
Are there some good algorithms following this approach?
I have been working in this area and would love to learn more.
|
|
|
|
|
IIRC Integer Linear Programming can solve it optimally, but everyone seems to use heuristic algorithms because solving an ILP problem is too slow for them. But ILP is not an algorithm but a way of specifying a problem. You can solve it with Branch and Bound (I may give it a try and see how slow it would really be).
It's quite annoying to search for good information about job scheduling with full in-advance knowledge - most papers about job scheduling deal with the online version and/or throw in some extra unknowns and restrictions.
|
|
|
|
|
harold aptroot wrote: veryone seems to use heuristic algorithms because solving an ILP problem is too slow for them
This is exactly what i found. Further, all algorithms that are created in this area are more of customized or proprietary.
Job Scheduling is a major and vast topic and solving it by usage of rectangles, is breaking down the problem into smaller problem. I hope to see such algorithms...
|
|
|
|
|
Time for some code!
This code is clearly crap, I just wrote it quickly in a console app to see whether it would work. It calculates the optimal solution with a simple branch and bound algorithm (without any tricks that can make it faster) - all cases that I tested worked.
For anything above 16 jobs it becomes really really slow. As a quick guestimate, the time complexity is about O(m^j) where m is the number of machines and j is the number of jobs.
static int[] Schedule(int[] jobs, int machines)
{
int[] targets = new int[jobs.Length];
int[] lengths = new int[machines];
_bestFoundScore = int.MaxValue;
_bestSolution = null;
_schedule(jobs, targets, 0, lengths);
return _bestSolution;
}
static int _bestFoundScore = int.MaxValue;
static int[] _bestSolution = null;
static void _schedule(int[] jobs, int[] targets, int index, int[] lengths)
{
if (index == jobs.Length)
{
int max = 0;
for (int j = 0; j < lengths.Length; j++)
if (lengths[j] > max)
max = lengths[j];
if (max >= _bestFoundScore)
return;
_bestFoundScore = max;
int[] res = new int[targets.Length];
Array.Copy(targets, res, res.Length);
_bestSolution = res;
}
else
{
for (int i = 0; i < lengths.Length; i++)
{
targets[index] = i + 1;
lengths[i] += jobs[index];
int max = 0;
for (int j = 0; j < lengths.Length; j++)
if (lengths[j] > max)
max = lengths[j];
if (max < _bestFoundScore)
{
_schedule(jobs, targets, index + 1, lengths);
}
targets[index] = 0;
lengths[i] -= jobs[index];
}
}
}
Edit: but I don't think using rectangles will help at all - if anything, it will just make it harder without having any benefits. The problem would still be the same, but you'd have "the width of a rectangle" instead of just "some integer or float" which is really just the same thing.
modified on Sunday, April 18, 2010 8:44 AM
|
|
|
|
|
Hey Harold,
Thanks for the code. This piece of code is basically an implementation of nested recursions. Usually, algorithms have been developed to use some shortcuts in order to achieve the optimum.
harold aptroot wrote: For anything above 16 jobs it becomes really really slow
It will get even slower if you add the type of jobs, type of machines, duration of job, efficiencies and duration of machine operation. I wonder what speed would be then.
The idea of rectangles is not to complicate the problem but to be able to see the problem differently.
Consider solving a maze from within the maze or sitting on the top of it. The perspective makes the whole of the difference. And hence the rectangle example. Another benefit is to represent the scheduling graphically and allow manual placement of pieces into a box of available resources.
Lets share in case we come across something. I have been trying to find something useful for a long time. When I saw your comment, I got optimistic
Cheers.
|
|
|
|
|
It has one shortcut - as soon as a partial solution becomes worse than the currently-best-found solution it bails out and starts on the next partial solution.
I tried adding a greedy approximation so it could discard more partial results in the beginning when it hasn't found a good potential solution yet, but on random problem instances with m=3 and j=20 it only helped slightly more than a third of a percentage on average (which is basically nothing)
|
|
|
|
|
buddy. we both know that nested recursions will ultimately be slow and they have one inherent problem "SCALING". you can't scale them. They are only good for small problems.
|
|
|
|
|
Yea I know, do you know anything better though?
4.5 seconds (in release mode) on average for m=3 j=20, btw (with that naive implementation)
|
|
|
|
|
Oh. I totally appreciate the effort. The fact is that you created a working code in a nick of time.
However it is not an algorithm that we both are looking for. Because it cannot be scaled to real life problems. However fast you make it. With every single increase in job or machine, the time will double up.
I work with a range of around 500+ machines and around 1000 jobs to be allocated. And then there are multiple variations and factors to calculate the duration.
May be we can collaborate and work on an algorithm. I am very interested in working on it with a set objective and deliverables. If we succeed, its gonna be a huge success.
What say?
Som
|
|
|
|
|
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. 
|
|
|
|
|
Here is a simple example where biggest job first does not yield the optimum:
two machines; five jobs: 3,3,2,2,2
|
|
|
|
|
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...
|
|
|
|
|
IMO the more jobs the more "biggest job first" gets nearer to the optimal solution.
|
|
|
|
|
Luc Pattyn wrote: IMO the more jobs the more "biggest job first" gets nearer to the optimal solution
I vote for "pays most". 
The wonderful thing about the Darwin Awards is that everyone wins, especially the members of the audience.
|
|
|
|
|
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 s be the sum of all job-lengths and let bound be (s+m-1)/m (where m is 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 exceed bound, 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 the bound to bound+(jlength-(bound-mlength)) (IOW, make it so that you could add the smallest job to the smallest schedule without exceeding the bound)
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, because jlength-(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 the bound will 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
|
|
|
|
|
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.
|
|
|
|
|
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.
|
|
|
|
|
Need C# codez urgentzzzzz!!!!!
Not really, I have code. However, I am after some advice: under embedded .NET, is this better implemented under event-driven code or in a more linear fashion with the dreaded Application.DoEvents()? An event-driven implementation looks a bit of a brain-f*** IMO...
|
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
