Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: Notesfiles $Revision: 1.7.0.10 $; site ti-csl
Path: utzoo!watmath!clyde!cbosgd!ihnp4!inuxc!pur-ee!uiucdcs!convex!ti-csl!tgralewi
From: tgralewi@ti-csl
Newsgroups: net.puzzle
Subject: Re: Orphaned Response
Message-ID: <13800001@ti-csl>
Date: Fri, 28-Feb-86 11:33:00 EST
Article-I.D.: ti-csl.13800001
Posted: Fri Feb 28 11:33:00 1986
Date-Received: Tue, 4-Mar-86 04:47:42 EST
References: <266@aero.ARPA>
Lines: 38
Nf-ID: #R:aero.ARPA:266:ti-csl:13800001:000:1848
Nf-From: ti-csl!tgralewi    Feb 28 10:33:00 1986


In my days as an under graduate I was required to create a general solution
to the "scheduling problem" as previously stated.

  As previously stated the solution is non trivial, the one we (my class) did
consisted of a general set of constraints and lists of people and the hours
and days each person could work.  The final solution was written in LISP
(not my favorite language but ideal for this kind of problem).  The program
took as input a set of lists containing the afore mentioned information and
basicaly used itteration (by recursion and list pruning) to try every possible
combination until one fit all the constraints.
  The program took the first possible worker that could fill the next slot open
and removed him from the lists and called itself with the new lists and
new time slots, if the returned value was unsuccessful the next person was
selected, etc.
  The program was not trivial (about 20 or 30 pages of LISP) and slow (of the
5 or so programs that actualy worked they took from 1 to 24 hours to run).
The data we used to test the system was something of the form:

   8 employees
   4 week repeated schedule
   Each must have 3 two day weekends and 1 three day weekend
   No person may work 2 shifts without at least 2 shifts gap
   whenever possible a person must not change shifts (1st, 2nd, or 3rd)
     more than twice in one shedule
   Personal vacations may be added in and need to be scheduled
     (this was the reason for a program instead of just a fixed schedule)
   No more than 40 hours per person per week
   2 people on each shift

   There were also some constraints about adding half days etc, but I don't
remember them.

Just my 2 cents worth (looks more like about $.36 but it's only worth $.02)

Discalimer? (I disclaim having a disclaimer)

Return address? (I am still trying to figure that one out)