|
I have a set of machines, let's call them A,B,C,...etc and a bunch of tasks let's call them 1,2,3,...an so on. Now my machines aren't terribly reliable and often it may be the case that say A can do tasks 1 & 3, but can't do task 2, so obviously I shouldn't have it do task 2. Also each machine can only be assigned one task, so A can do 1 or 3, but not both. So let's say for example I have this:
A can do 1 & 3
B can do 1, 2 & 3
C can only do 3
The solution is obvious, A does 1, B does 2 and C does 3. This is fairly trivial for the case of only 3 machines and 3 tasks, but my real problem has 30 machines and potentially 30 tasks.
Is there an algorithm that handles these types of problems that somebody can point me in the direction of. It would need to suggest a solution (it's not necessary the case that any one solution would be better than another) or let me know that there is no solution and I need to fix my machines.
All I need is a nudge in the right direction.
Cheers!
|
|
|
|
|
Hungarian algorithm[^] maybe?
---- I don't care what you consider witty, but at least I do not blather on posting nonsense like Jim Crafton.-- Stringcheese, humbled by Crafton's ability to string together multiple sentences
|
|
|
|
|
Thanks, I'll check it out.
|
|
|
|
|
Hello,
I work for a steel fabrication plant and am faced with a problem I cannot solve. Hopefully the gang over here at Code Project can help me out a little...
First, let me define the terms I will use (a crash course in steel purchasing):
-Mill Order: simply an order of material placed to the steel mill
-Beams: should be self explanatory, but I want to cover their dimensioning:
-a beam has three dimensions, they are as follows; nominal flange depth (aka width), pounds per foot (weight), and length.
Sample: 10x15x9'-0" ( I should note here that the length property for each beam in the program is defined as the number
of 1/16ths of an inch that make up the length. ->
For the sample, the length would be 1728 (1728/16)/12=9).)
-Hundred Weight (or CWT): is the price of the beam per 100lbs. This is usually around $40-$50
-Standard Size: any beam length 30ft-65ft in increments of 5ft.
-Non-Standard Size: any beam of any length in increments of 6in. There is an extra charge of $0.25/cwt for non-standard beams.
-Bundle Requirements: a standard size 10x15 beam is sold in bundles of 3. If you need 5, you must buy 2 bundles and inventory
the extra.
a non-standard size 10x15 must meet at least one bundle requirement. So, if you need 4, they will sell you
4. But if you need 2, you must buy 3 and inventory the extra.
The bundle requirements change with each flange depth and weight.
Ok. Now to the logic bit...
I am given a list of all the beams for a job to order from the mill. Obviously I do not want to order every beam as is. I need to nest the beams into the mill order to optimize the amount of money being spent. If you do not know what I mean by "nest", let me explain: If I have 6 beams whose dimesions are 10x15x20', instead of ordering the beams without nesting and incuring a charge of $0.25/cwt for the non-standard length, I want to nest those 6 beams into 1 40' bundle.
This is the part that is difficult. I cannot seem to find a logic process to optimize all standard sizes vs. non-standard sizes vs. bundle requiremnts vs. pricing. If I could see a step by step process, or just have an idea of where to start, I would probably be able to begin serious development on the program.
I want to make it VERY CLEAR at this point that I am NOT asking anyone to do this for me. All I am looking for is a point in the right direction or something of that nature. I DO NOT WANT SOURCE FROM ANY LANGUAGE.
Thank you in advance for your time and input,
-David
|
|
|
|
|
I think I might be able to help. Before we start, I have two observations:
[1] I take it that ordering the beams in a manner that is not suited to the design will result in someone at the site cutting / trimming / grinding each beam ordered to the beam design specs. If so, there are personnel charges, equipment usage, temporary storage locations, etc... that are costs to the company to make that happen. I do not see those costs in your description, and I wonder if sometimes the cost of buying a non-standard size/bundle is actually cheaper. I will ignore this complexity for now.
[2] Clearly, the problem is overwhelming you as it has too many parameters to jostle at once. A good problem solving strategy in such cases is to relax a few of the paramaters and get a solution for the relaxed problem. For example, I would start off assuming you are always ordering beams of the same nominal flange depth and the same pounds per foot. The examples discussed almost suggest you are indeed making this assumption, but I want to be clear. I would like to start here and steer you to a solution. Once we find a solution for this relaxed problem, we will add back one of the constraints and see what changes. We will then continue to iterativley add back in all the constraints until the original problem is solved. Is this approach ok?
HossFly
|
|
|
|
|
HossFly,
First of all, I cannot tell you how much I appreciate a timely and professional response. Such things are a rarity among most forums and message boards.
To address your first point raised; all cutting, grinding, welding, etc. is done by us in our shop. So the ammount of "shop hours" is billed seperately to the job. But that is a very good point I had not thought of.
As for your second point, yes, the problem is overwhelming me. I had thought of letting some of the parameters lie dormant for a short while, but it seems that every element of the problem is so closely related to the other - I am not quite sure of which parameters to drop. But I do like your recommendation of using the same beam size. I will try that and see if I can get a chunk of the problem diagrammed.
My biggest problem right now, is that I cannot seem to even write out on paper how this process works.
Thank you for your response,
-David
|
|
|
|
|
Alright, we can break the problem down even further. I do intend to honor your request and not provide source or solution, but rather help you attack the problem. Here is a suggested course.
Problem1:
[1] Assume nominal flange depth and pounds per foot are fixed.
[2] Assume there is only one standard size, and it is 30 ft.
Problem2:
[1] Assume Problem 1, but now allow for 30 ft or 35 ft standard sizes.
I think once you solve Problem1, and especially after you solve Problem2, you will understand how the 30-65 feet increments are impacting your solution. Let me know how that goes.
HossFly
|
|
|
|
|
I think you might be able to get a long way by using a multiple knapsack algorithm. The knapsack problem is to select a combination of N items with weights {Wi} to fill a knapsack with capacity K. The multiple knapsack problem tries to fill M knapsacks with capacities {Kj} from the N weights {Wi}. In your case the knapsacks are the available beamlengths. So if for one beam size the available beamlength is 20' and you need lengths {10', 6', 8', 12', 15', 2', 5', 7', 8'} then you need 73' of beam, so try to fill 4 knapsacks of 20'. If the algorithm fails, try to fill 5 etc...
One standard multiple knapsack code is http://www.netlib.org/toms/632[^].
Once you know how many beams you need you can then cope with bundling.
-- modified at 2:22 Saturday 22nd September, 2007
The multiple knapsack algorithm also allows you to include arbitrary beam lengths in your own inventory. So for the example given, if you had a 14' length of beam on hand, you could try to solve for 4 knapsacks {14, 20, 20, 20} and if this didn't work then add an additional 20' knapsack. This way you will continually use up your inventory
Peter
"Until the invention of the computer, the machine gun was the device that enabled humans to make the most mistakes in the smallest amount of time."
|
|
|
|
|
A request was made to give no source code, and it was requested in BOLD. Yet you gave a link to an algorithm and source. Incredible.
|
|
|
|
|
HossFly,
Thank you for helping me break down the problem like that. That was help much needed.
I think I have a good chunk figured out. I used one length and worked out how to nest the beams into that length with respect to bundling. It seems to be working very well, on paper. Right now, I input the beam(s) to be nested, and I nest them into lengths of 65', 60', 55', 50', 45', 40', 35', and 30' (all the standard lengths) one at a time. Each of the standard lengths is a function and returns two values; the total number of bundles (after making sure the beam meets the bundle requirements), and the amount of drop (unused portions of the beam(s) I am nesting into). Then I sort out which function returns the least amount of drop (as this will be the cheapest and most productive solution).
I think my next step is to do the same but for non-standard lengths (my only problem here is that I do not know how to round the lengths into even 6in. incriments). That way I can compare standard and non-standard prices. After that it's just a simple task of designing a report to output to the user.
But I still have questions about this method's efficency and/or actual optimization. Is there a test of some kind that you know of that can provide evidence for this? If not, don't worry about it.
Thank you again for breaking it down like that. I wish I had thought of that, but I guess that's why God didn't put me on the Earth by myself.
-David
|
|
|
|
|
Alright, we are getting closer. The next suggested steps would be:
Problem3:
[1] Assume nominal flange depth and pounds per foot are fixed.
[2] Assume there are only only non-standard sizes.
Problem4:
[1] Assume nominal flange depth and pounds per foot are fixed.
[2] Assume there is one standard size (e.g., 30') and non-standard sizes.
After you solve Problem4 you will then have unraveled another aspect of your algortihm (how the standard and non-standard sizes impact the logic.)
The big picture ...
I have often been in need of a niche-like algorithm similar in complexity to yours. I cannot count the times I have been frustratingly lost and on my own as well. My intent was not to give you fish, but rather share with you how I have caught several fish. You have used that now to (almost) catch your own fish, and that is very rewarding.
Sometimes you may not catch your fish, but by applying good problem solving skills (e.g., break down, relaxing conditions, combining sub-optimal sub-solutions, etc...), you gain the knowledge and understanding needed to realize what aspect of someone else's solution might work for you.
You will soon have your own algorithm. Not only that, you will have a deeper understanding of the mechanics of your problem. Having an algorithm is one thing - an optimal algorithm is another. Being able to analyze optimality requires intimacy with the problem. You are gaining this intimacy as well.
The standard means to measure optimality is to do a flop count (floating point operations). Some folk measure a "flop" as one addition and one multiplication. The idea is to then count the flops in your algorithm.
A good example is Matrix-Vector multiplication. To multiply an n-by-n matrix by a an n-vector would require roughly n^2 flops. Sometimes your matrix may have special properties (e.g., cyclic) and there are algorithms out there that can do the work in far less than n^2 flops.
I would suggest at least an attempt to count flops. This is a very difficult aspect of algorithm construction. Once you have completed your algorithm, and have been over the entire process with diligence, you will then be in a position to analyze the good/bad of a previous post about a possible alternative algorithm for you. I leave it to you to weigh the good and bad of that algorithm.
Best Regards,
HossFly
|
|
|
|
|
I suggested that a well-known algorithm may be applicable, and from the posting I guessed that the OP would not be aware that tried and tested source code was available - so I posted a link to one. It would be silly for a professional programmer to try to solve the multiple knapsack problem without at least considering the standard codes. Get offended if you like - it's your blood pressure.
From re-reading the original post, the fact that the standard lengths are not fixed but come in increments of 5' means that the multiple knapsack is not optimal. It would give you an efficient way of quickly testing different bundles - e.g. if you need 73' as in my example, you could try your inventory plus 3 lengths of 25', 3 of 30' and see if a solution existed.
If the number of lengths is small then the problem can be efficiently solved with an exhaustive search, but the complexity quickly escalates as the number of lengths increases.
Peter
"Until the invention of the computer, the machine gun was the device that enabled humans to make the most mistakes in the smallest amount of time."
|
|
|
|
|
Hey everyone,
I've been working on a bit of code that will calculate the time difference (hours/minutes) between two times, but only include business hours in that calculation. I have an iterative solution that works alright as long as "work hours" start and end on even hour boundaries. I could get the minute calculation to work by decreasing the size of my iterative step from hours to minutes, but it seems to me there must be a better way.
I've tried a couple of methods, and done some research on the problem, but haven't been able to come up with anything that really satisfies me. Any ideas?
Again, the problem in essence: calculate the amount of time (down to minutes) between two arbitrary date-times, counting only an arbitrary set of "working hours." All without simply looping over every minute in between start and end.
Don't sweat too much: at this point, it's more of an intellectual exercise than a practical necessity.
--
Chris Wilson
|
|
|
|
|
Convert the times into minutes after an arbitrary starting point.
Calculate the number of minutes the employee worked without taking non working periods into account.
Do an overlap test between period worked and the each sequential non work period. IF there's an overlap subtract the amount from the total.
--
If you view money as inherently evil, I view it as my duty to assist in making you more virtuous.
|
|
|
|
|
Hello,
I must calculate the lateral acceleration of a vehicle ( auto / motorbike ) using the data from a gps. can you help me? How information I have only the speed, which is the corrected formula?
Thanks
|
|
|
|
|
assume that you have 3 points: (X1,Y1)[sampled at time T1], (X2,X2)[sampled at time T2] and (X3,Y3)[sampled at time T3]
let semplify the problem: Y1=0; Y2=0.
Then, if there is null lateral acceleration Y3 must be =0, if not compute it as
a=Y3/(T^2) where T is the time difference T3-T2
If Y1 and Y2 are different from 0 then you have only to estimate the linear path and compute the lateral offset gained at the point 3. Divide it by T^2 again.
I hope
Russell
|
|
|
|
|
Back to 1st year physics:
Velocity (speed) = delta (change in) position over time
Acceleration = delta velocity over time
single point iterative solutions are innacurate without exact position, and gps does not give you exact position, but it will give you a noisy approximation:
newvelocityx = (newpositionx - oldpositionx)/sampletime
newaccelerationx = (newvelocityx - oldvelocityx)/sampletime
http://230nsc1.phy-astr.gsu.edu/hbase/mot.html[^]
The better way is to filter the data, especially from a GPS simultaneously with calculating the velocity. but then you get into a whole new field of calculations. The correct formula is the one that matches your data and your need. There are many ways to solve this, so many formulas.
_________________________
Asu no koto o ieba, tenjo de nezumi ga warau.
Talk about things of tomorrow and the mice in the ceiling laugh. (Japanese Proverb)
|
|
|
|
|
can you help me with example?
Alex
|
|
|
|
|
AlexB47 wrote: can you help me with example?
Kalman filters
Alpha Beta Gamma Filters (sometimes called improved Alpha Beta Filters)
if real-time is not a problem, then you can go with least-squares curve fit and similar constructs.
You're talking about extracting 2nd order functions from noisy data if all you have is GPS.
_________________________
Asu no koto o ieba, tenjo de nezumi ga warau.
Talk about things of tomorrow and the mice in the ceiling laugh. (Japanese Proverb)
|
|
|
|
|
Hi, i am currently doing a project that require my .net website to be able to make some medical diagnosis given a set of symptoms.
Is neural network the way to go?
or shld i try other stuff like prolog?
if neural network is the way to go, how can i go about doing it?
is matlab the correct tool to use?
pls help
thks alot
|
|
|
|
|
This is an Expert System.
Try using one of the languages like Lisp
But I dont know how to use them in the web.
|
|
|
|
|
Hi,
i understand tt matlab sw has a neural network toolkit that enable developers to simply train the nodes and use the network.
and we can simply interface the create program file by means of com
it tt really possible ?
tt means i dun have to do much coding?
|
|
|
|
|
I'm not entirely sure what to even Google for this particular algorithm, so any insight would be much appreciated.
The following is the problem I need to solve:
Say I have a list of many raw items, with some repeats (the number doesn't matter, just assume it's more than three or 4. It could be several hundred, it could be 5).
I have ANOTHER list of possible combinations of those items. We'll call these recipes. Each recipe can be created out of 3 of the other items.
The algorithm I need to create will do the following:
* Determine which recipes can be created out of the list of raw items.
* Determine the OPTIMAL combination of recipes. That is, I want to minimize the number of remaining items.
Yes, I could do this the brute force way - if I wanted my program to run all night. I KNOW there are implementations of this algorithm that will run in mere seconds.
It has been 6 years since I took my CS class on algorithms, so I no longer remember what this is called. Doesn't it have something to do with Hamiltonians? Consequently, it's hard to search Google for it 
If you remember what this is and/or can point me the right direction, I'd appreciate it!
More Info
This is a problem I've set for myself simply to re-develop these skills. This is not homework or work, I just want to figure out how to do it.
Also, this actually IS a way to figure out how to make real food recipes. I have a game I play where I can get lots and lots of raw ingredients, and I can make recipes out of those ingredients. I've gotten sick of referring back to the list of recipes, so I wanted to make a program that will do the crunching for me. I figured this would be a perfect opportunity to use to remind myself how to solve these types of problems.
The early bird who catches the worm works for someone who comes in late and owns the worm farm. -- Travis McGee
|
|
|
|
|
You might be looking for the Simplex algorithm. I think the restriction is that the combinations have to be linear to be able to use it. I'm assuming that since it's called "linear optimization". 
Save an endangered species. The American Engineer.
|
|
|
|
|
That's it!
Thanks!
I don't know if this problem is even solvable - seems so simple, but then, so does the Traveling Salesman. I suspect this problem is probably NP if it doesn't have sufficient initial conditions. But at least I know where to look now 
The early bird who catches the worm works for someone who comes in late and owns the worm farm. -- Travis McGee
|
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
