Beefy Boxes and Bandwidth Generously Provided by pair Networks
No such thing as a small change
 
PerlMonks  

comment on

( #3333=superdoc: print w/replies, xml ) Need Help??
Hi, two longish comments since I got excited googling. Found what one school uses.

1. I'm not sure it's ethical to give "flexible" people more weight. It is a lottery, and the choices are based on what classes they are physically able to attend. 2nd, 3rd choices are decisions based on the scenario on what if I fail to get my wish, which is different from being flexible.

So I think you should try to get everyone their first choices and see which courses are oversubscribed. Then run a lottery for the busy courses. People who lose the lottery get second choice if possible, and if they have no other choices they get either no course, a random choice, or a list of remaining courses for which they can apply.

Another possibility is you can leave a few seats in busy courses free and decide in a second round who to put into them based on other considerations.

I also think it might be a good idea to try and develop other considerations to reduce the number of people vying for a popular course, such as their year in college, their academic credentials, their major, etc. I am not at all for it but if you want female engineers there's that too.

2. A voice spoke to me and said "simulated annealing". Which I always thought would be interesting to investigate but never had a reason. It is another way to solve these things, and there is a related algorithm called the Metropolis algorithm (google annealing and scheduling). It is based on a slowly cooling metal that crystallizes with minimum energy disparities and tunnels out of local minima, and is useful for traveling salesman type problems. In other words if you can model this in terms of energy and geometrical relationships this might be a good one. But it seems hard to me to see what is going on and hard to ensure human considerations like the above.

Incidentally I was googling (school scheduling algorithm) and then added the term "annealing". Turns out that is what Syracuse University used, I just found out, for their NP hard timetabling problem. (See the PDF) They are mixing in some neurons too, it is pretty serious stuff. They are calling certain classes "high cost" and looking for scheduling conflicts, etc. which is more than what you need. So you will have to model differently or use a subset of what they do. As noted on p. 16 of the pdf, it includes student preferences.

Some good news perhaps is that the GNU Scientific Library has a simulated annealing function def called gsl_siman_solve which might be usable from the Perl module Math::GSL::Sf. There are other perl annealing modules (search cpan) and it turns out the Perl Mongers world map used an Inline::C annealing routine (until a year ago) (in Image::WorldMap to keep labels from overlapping) too! (See bottom for link about the algorithm used now,) Bioperl also uses it. You might like to check out Algorithm::Evolutionary which provides both annealing and roulette wheels. Anyway this looks like a very useful thing to have in Perl for a lot of things so I would like to learn how to use it better.

FWIW I also found an overview of scheduling algorithms, this is an exciting (to me anyway) area that is well researched, and aside from annealing I understand "list-based" algorithms are used to manage limited resources however this was in the context of chip development.

Anyway this may be overkill but I think if you have more restrictions then simulated annealing is a) the only way to stay sane, b) competitive with other heuristics (so they say), and c) going to give you close to the best possible results. Oh and it takes a looong time to run so you will be happy about that part maybe. The pdf mentions a comparison between graph coloring (as a fast heuristic) instead of a rule-based preprocessor, which sounds like what someone mentioned earlier.

Other links:
NIST Algorithm dictionary and entry on Fisher Yates Shuffle used now in Image::WorldMap pure perl replacement for Inline::C (so annealing or a simplification of it)
1 (quotation about annealing)
Nice explanation of Simulated Annealing with simple algorithm, found through NIST
2 (descriptions of algorithms for chips)
3 (more googling)
4 Tabu search in spanish school


In reply to Re: [OT] simple algorithm for assigning students to class sections by mattr
in thread [OT] simple algorithm for assigning students to class sections by hossman

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":



  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.
  • Log In?
    Username:
    Password:

    What's my password?
    Create A New User
    Chatterbox?
    and the web crawler heard nothing...

    How do I use this? | Other CB clients
    Other Users?
    Others browsing the Monastery: (6)
    As of 2021-01-16 12:13 GMT
    Sections?
    Information?
    Find Nodes?
    Leftovers?
      Voting Booth?
      Notices?