Looking for an algorithm
-
more hoping. :) BW
If you're not part of the solution, you're part of the precipitate.
-- Steven Wrightbrianwelsch wrote:
more hoping.
ahhhh... vain hope, greatest and most deadly of the demons unleashed by Pandora. ;P _________________________ Asu no koto o ieba, tenjo de nezumi ga warau. Talk about things of tomorrow and the mice in the ceiling laugh. (Japanese Proverb)
-
Nick's profile is here[^]. If you read it, you find out he's been programming a long time and well beyond the need to post homework questions. Homework questions are typically posted with a statement of a problem and a demand, not a politely phrased request but a demand, for source code, and BTW they must have it by tomorrow or they'll flunk. Nick's original post was nothing like that. Cut him some slack.
Software Zen:
delete this;I only gave my impression of his post and thus a posit about why it may have received so many 1 votes. Personally I don't care if his question was homework or not, but obviously it does to a lot of other folks who, like myself, don't reveiw the profile of every one who posts in the lounge. So, while we're cutting slack here...
“Profanity is the attempt of a lazy and feeble mind to express itself forcefully”
-
Lol. I should have known. :D David
ok, this is way too funny... I never thought Dave would have remembered my site! Nick, I am going to be hit and miss online tonight (one of my servers had a motherboard melt (ok, not melt but it may as well have)... try to catch me on IM anyway. We may be able to come up with a solution or draw from the schedule from another feis (Chicago or Cleveland perhaps). Andrew Andrew Bryan
-
brianwelsch wrote:
Check his profile. Not likely a homework question.
You aren't honestly expecting everyone not to jump to conclusions and vote rashly? :omg: _________________________ Asu no koto o ieba, tenjo de nezumi ga warau. Talk about things of tomorrow and the mice in the ceiling laugh. (Japanese Proverb)
Or maybe not everyone looks as the profiles of every last poster in the world. I sure don't. Jeremy Falcon
-
I've been "selected" to come up with a schedule of dance competitions. Not something I was expecting... Has anybody seen an algorithm that will allow to do to different weighted combinations into buckets? Here's an example: I've got 3 buckets (Stages actually) Competition 1: 3 Entries Competition 2: 4 Entries Competition 3: 2 Entries Competition 4: 1 Entry Competition 5: 2 Entries So the buckets would end up looking like this: B1: C1+C4 = 4 Entries B2: C2 = 4 Entries B3: C3+C5 = 4 Entries The idea is that each stage gets the same number of competitors so they all finish at the same time. Thanks for any help. Nick This are my own opinions. You know the rest..... -- modified at 22:46 Saturday 13th May, 2006
I probably don’t understand all the parameters and constraints of Feis scheduling well enough so this is probably too simplistic but with regard to a brute force method, doesn’t the solution resemble a game of Tetris? In Excel, each of the 8 stages is a column and you add to cells the values 1 through 1220 representing the competitor. For example, competitor 111 has 3 entries so on Stage 3 there might be three rows containing 111. Perhaps as you continue adding competitors to stages an algorithm will come to mind that can be implemented in an Excel macro. If not, you would still have time to fill in the cells by hand.
-
I probably don’t understand all the parameters and constraints of Feis scheduling well enough so this is probably too simplistic but with regard to a brute force method, doesn’t the solution resemble a game of Tetris? In Excel, each of the 8 stages is a column and you add to cells the values 1 through 1220 representing the competitor. For example, competitor 111 has 3 entries so on Stage 3 there might be three rows containing 111. Perhaps as you continue adding competitors to stages an algorithm will come to mind that can be implemented in an Excel macro. If not, you would still have time to fill in the cells by hand.
deltaseq0 wrote:
In Excel, each of the 8 stages is a column and you add to cells the values 1 through 1220 representing the competitor. For example, competitor 111 has 3 entries so on Stage 3 there might be three rows containing 111.
Actually, I'm going to do something very similar to that. As I add a competition, I figure out which bucket has the fewest competitors in it, and just put it in there. The next competition will find the bucket with the smallest competitor count and add it, etc. This definitely wont provide the most effecient stage scheduling, but at least it's a start. If I had more time, like next year's feis, I'd probably look into a schedule where different scenarios are examined to determine what would be the most effecient. As it stands right now, there are about 80 different competitions where the competitors are split up into. Each competition is actually just designator for each kid's age. (They might have 3 different dance types, but we want all of the beginnner, age 5s to dance together on the same stage, so they don't have to move from stage to stage, kids tend to get lost when that happens, talk about parents yelling). I'll let ya know how it comes out. Nick This are my own opinions. You know the rest.....
-
I've been "selected" to come up with a schedule of dance competitions. Not something I was expecting... Has anybody seen an algorithm that will allow to do to different weighted combinations into buckets? Here's an example: I've got 3 buckets (Stages actually) Competition 1: 3 Entries Competition 2: 4 Entries Competition 3: 2 Entries Competition 4: 1 Entry Competition 5: 2 Entries So the buckets would end up looking like this: B1: C1+C4 = 4 Entries B2: C2 = 4 Entries B3: C3+C5 = 4 Entries The idea is that each stage gets the same number of competitors so they all finish at the same time. Thanks for any help. Nick This are my own opinions. You know the rest..... -- modified at 22:46 Saturday 13th May, 2006
Generally, Your problem is the same as if You had a chess competition. So, You can use some of algorithms which will generate pairs of variations of 2nd class, for n predefined members. Remark: the number of members must be even (that is, any of members has its own 'pair'). If You're interesting in the solution of the chess competition, I can send it to You; although it comes in the MS-DOS-environment C, I suppose it will be good enough for You. Regards, Dejan Senic, Belgrade
-
leppie wrote:
Unless you have a few 1000 competitions to sort, go with brute force. You are descibing a non-'NLP complete' problem IIRC. Think university classroom/exam scheduling.
1220 Competitors this year actually, on 8 stages to be exact. I was thrown into this scheduling thing at the last minute.. Not fun. I forgot all about those classroom scheduling kind of CS problems. I guess it has been a few years ago since I messed with them.. This are my own opinions. You know the rest.....
Dear Nick, It seems that your problem belongs to the class of machine scheduling problems, a well-known area of Operations Research. Suppose each competition has to take place at one stage and cannot be intterupted by another competition (non-preemptive scheduling). Moreover, I assume that the number of competitions is not very large (say max 10 or 15). If one of these assumptions is wrong, please let me know. Let's introduce some notation: * you have s stages, * there are m different competitions, * n competitors want to take part. In terms of machine scheduling, the stages are the machines and the jobs are the competitions (using the first assumption). Your objective is to minimize the overall completion time (which is the maximum completion time of the stages). Now, you can aggregate the n competitors resulting in m jobs, each competion gets the number of competitors in this competition as duration. The problem breaks down to scheduling m jobs with different durations on s machines. This could be done by a greedy heuristic: schedule the largest unscheduled competition at the stage with the earliest (current) completion time and repeat until all competitions are scheduled. Enumerating the schedules is also an option because the number of jobs is relatively small (using the second assumption). Of course, there is a trade-off between the number of stages and the completion time. Moreover, different durations of competitors in different competitions can be incorporated easily. In that case, the duration of each competition becomes a weighted sum. With a bit more effort, you could be able to incorporate precedence constraints if you like (schedule competiton i before competition j). In case you would like to schedule all competitors individually, the problem becomes intractable and I would advise to see if the greedy heuristic described above can be of any help. I hope this helps. By searching "machine scheduling" in Google, you will probably find a wealth of information. Kind regards, Talentink
-
Dear Nick, It seems that your problem belongs to the class of machine scheduling problems, a well-known area of Operations Research. Suppose each competition has to take place at one stage and cannot be intterupted by another competition (non-preemptive scheduling). Moreover, I assume that the number of competitions is not very large (say max 10 or 15). If one of these assumptions is wrong, please let me know. Let's introduce some notation: * you have s stages, * there are m different competitions, * n competitors want to take part. In terms of machine scheduling, the stages are the machines and the jobs are the competitions (using the first assumption). Your objective is to minimize the overall completion time (which is the maximum completion time of the stages). Now, you can aggregate the n competitors resulting in m jobs, each competion gets the number of competitors in this competition as duration. The problem breaks down to scheduling m jobs with different durations on s machines. This could be done by a greedy heuristic: schedule the largest unscheduled competition at the stage with the earliest (current) completion time and repeat until all competitions are scheduled. Enumerating the schedules is also an option because the number of jobs is relatively small (using the second assumption). Of course, there is a trade-off between the number of stages and the completion time. Moreover, different durations of competitors in different competitions can be incorporated easily. In that case, the duration of each competition becomes a weighted sum. With a bit more effort, you could be able to incorporate precedence constraints if you like (schedule competiton i before competition j). In case you would like to schedule all competitors individually, the problem becomes intractable and I would advise to see if the greedy heuristic described above can be of any help. I hope this helps. By searching "machine scheduling" in Google, you will probably find a wealth of information. Kind regards, Talentink
competitions is not very large (say max 10 or 15). Actually, about 90 competitions, we keep the overall competitor to competition count down, we split the competitions accordingly. Assume the competitions are already split... Your objective is to minimize the overall completion time (which is the maximum completion time of the stages). Yep, the longer this takes, the longer it takes to get to the adult beverages. Honestly, the parents get testy after about 10 hours at the venue. I would do. (And have and I'm not even a dancing parent. By searching "machine scheduling" in Google, you will probably find a wealth of information. I'll definitely do that! Thanks, Nick This are my own opinions. You know the rest.....
-
competitions is not very large (say max 10 or 15). Actually, about 90 competitions, we keep the overall competitor to competition count down, we split the competitions accordingly. Assume the competitions are already split... Your objective is to minimize the overall completion time (which is the maximum completion time of the stages). Yep, the longer this takes, the longer it takes to get to the adult beverages. Honestly, the parents get testy after about 10 hours at the venue. I would do. (And have and I'm not even a dancing parent. By searching "machine scheduling" in Google, you will probably find a wealth of information. I'll definitely do that! Thanks, Nick This are my own opinions. You know the rest.....
-
Hi Nick, 90 competitions is quite a lot. I would advise to try the greedy heuristic. It should not be that difficult to get first results... Good luck! Talentink
Nick, Hopefully this link will provide you with the algorithm you ask for. http://www.columbia.edu/~js1353/pubs/ss-soda99.pdf[^]