Re: [school-discuss] A plan for automatic schedule building and scheduling

[Manuel Gutierrez Algaba <algaba@gmx.net>]

To write such a system is kinda trivial in a programming language such as 
Clips, you set the rules, you set a constraint that re-fires new facts when 
constraints are not needed. At the end you have some "optimization" process.
DNA and school schedules are different things. 

Another options is doing it with cellullar automata, creating several 
automatas ( the classes), each cell comprising another cellullar automata ( 
the children) , again setting rules for student transfer, satisfaction... 

I don't think much about genetic algorithms. They're nice for articles in 
magazines and for Stanford projects. Other technologies, namely neural 
networks, have been proven useful.

Trying prolog would be interesting too. Sometimes it's incredible what can 
come up from a set of rules and an initial fact. 

If you still feel with forces, try this: cellullar automata with prolog-ish 
genetic code. Maybe the program will be useless, but your article may appear 
in Dr. Dobb's. 

El Sáb 19 Abr 2003 14:37, James Smyth escribió:
> First a comment on open source; I know that programmers writing commercial
> scheduling programs frequent this list, I've talked to one. I believe that
> this should be an open source project. It should be developed as a stand
> alone engine that can be utilized by developers of both open source
> administrative systems and commercial systems. I am willing to work with
> anyone who shares this vision. I would not approve (although there is
> nothing I can do about it) of anyone taking this start and adding good
> ideas in secret to it. If you have a good idea please share it with the
> rest of us.
>
>
>
> In more than 20 years of programming I have found one truth, everything
> that fundamentally shapes programming is stolen. Most of it is stolen from
> Nature. So when I look for a solution to the problem of building and
> scheduling a master schedule I look to nature. Evolution is nature's
> problem solver, but how does it work? What are the hallmarks of its work?
>
>
>
> Evolution starts with DNA and makes random changes in the DNA. The
> resulting organism needs only to pass a simple test to be successful.
>
>
>
> ·       It must be able to procreate, which of course implies that it is
> alive.
>
>
>
> Simply being alive is not enough (at least for long). This could be
> described as make a change and test strategy.
>
>
>
> What are the hallmarks of evolution?
>
>
>
> ·       It operates over a long period of time
>
> ·       It operates on a massively parallel scale. There is not much
> communication going on. Very few of the objects (creatures) it creates
> interact with each other. For all we know it could make the same mistakes
> and cover the same ground millions of times.
>
> ·       It produces unexpected results. I remember an evolutionary program
> written at Stanford many years ago. Its goal was to produce an organism
> capable of moving. The different computer creatures it came up with where
> totally unpredicted.
>
> ·       It has a simple binary rule structure (live or die). Living could
> also be akin to learning, since it starts the next iteration with a new
> smarter base.
>
> ·       Changes in the environment some how drive it. Most of the time we
> are not evolving, evolution is not doing much useful. But change the
> environment and evolution kicks in to gear, making changes, filling niches.
>
> ·       The vast majority of its changes are negative (to put it politely)
> and fail.
>
> ·       It builds on success; its successes are the templates for the next
> generation.
>
> ·       ?
>
>
>
> Which of the above can we use?
>
>
>
>   a.. "Long period of time", we may only have a month or two for running.
> Good thing computers are fast. b.. "Massively parallel scale", this we
> need. The more CPU cycles the better. Of course our massively parallel
> might involve a couple of hundred entities (computers) vs natures billions.
> Since there will be communication that prevents the computers from working
> on the same part of the problem we will eliminate the making of the same
> mistake or going over the same ground over and over and thereby cut down
> the time period required. c.. "Unexpected results". This largely a factor
> of the randomness and scale of evolution and it greatly increases the
> amount of time required. For at least the first generation, I believe we
> will have to eliminate the random portion and therefore the unexpected
> results. d.. "Changes in the Environment", I think we will see the same
> here. The master schedule the second year will look remarkable like the
> first year and it should. Change for no reason just upsets people. But if
> there is a major change in the environment (new school, layoffs, change to
> block scheduling etc) this should really kick into its own. e.. "Builds on
> success" we are going to create some life first (master schedules that work
> to some degree) and build on that.
>
>
> What are the hallmarks of a good master schedule?
>
>
>
>   a.. Courses should be taught in the least number of rooms, by the least
> number of teachers and require the least number of sections. b.. Sections
> should be evenly balanced; each section should have about the same number
> of students as other sections of the course. Each section should have a
> consistent ratio of males to females. c.. Teachers should work a consistent
> number of periods per day in line with the contract. d.. Each meeting time
> of a course should be on a different day unless that are more meeting times
> than the master schedule rotation (how many school days pass before the
> schedule repeats, typical 5 or 10). In such cases the number of times a
> course meets on the same day should be minimized. e.. Courses should be
> taught in rooms designed for the course.
>   f.. Courses should be taught by qualified (certified) teachers in the
> subject. g.. Class sizes should be at or below the constraint size.
>   h.. Teachers should teach all their class in a single room.
>   i.. ?
>
>
> At the end of a scheduling process there is always what I call a "playing
> god" phase. Here someone (normal the principal) makes the hard choices to
> get the school scheduled. In some schools it might involve 1 or 2 students
> in larger schools it might be 5%. What kind of decisions does he/she make?
> These will be the basis for our schedule mutations. By having these
> directed mutations vs. natures random ones, we will cut down the CPU cycles
> necessary.
>
>
>
>   a.. Exceed the seat count for a section.
>   b.. Exceed the seat count for a room.
>   c.. Make teachers teach in multiple rooms. Do this by seniority?
>   d.. Teach a class in the wrong type of room. English in a chem. Lab?
>   e.. Have a teacher teach a course they don't normally teach or worst case
> is not certified to teach. f.. Hire a new teacher.
>   g.. Substitute a course a student has not requested for one that can't be
> scheduled. First try an alternative or closely related course (music for
> band) or one that fills the same graduation requirement. h.. Have a class
> meet more than once a day even if the rotation does not require it. i.. ?
>
>
> Here then is my general plan:
>
>
>
>   1.. Generate every non-constraint violating master schedule. The
> algorithm must allow them to be generated by number so I can tell computer
> #1 to generate and check the 1st 1000 scheduled and computer #2 the next
> etc. 2.. The program must operate as a screen saver so I can run it on all
> computers and get every extra CPU cycle possible without bothering other
> users. I figure an average computer in a school is only operated 6-7 hours
> per day, giving me 18 hours of CPU time. 3.. Schedule each of these master
> schedules against the course requests and report the status (master
> schedule # and scheduling percentage) to the server. The server will insure
> that all schedules are checked. 4.. Take the top 100-200-300 (what is a
> good live or die metric beside percent scheduled?) or what ever schedules
> and start mutating them by doing what the principal would do as describe
> above. Before this whole thing the school would rate how onerous each of
> the possible mutations was. 5.. Print a summary of the best results with a
> list of mutations and let principal pick the best.

---
mga