A note on linear programming algorithm design
P. B. M. Roes · Communications of the ACM · 1966
Section preferences (for specific instructors, times or timesharing with girl friends) are ignored."We do it this way because of the computer," would be the explanation.An answer to these problems can be obtained by enlarging the data base--the master class schedule.As student section requests are edited, perhaps during a card-totape conversion, it is a simple matter to tally the number of requests for each section.The section list can then include in addition to the number of seats available the number of requests to be processed.We can compute, for each section, a value p defined by no. of seats available p = min (1, ).no. of requests remaining Processing a student's list of sections desired proceeds in the following way: A random number r between 0 and 1 is compared to the p-value of the first section requested.If r p the other sections of the same course are tested one at a time for conflicts with sections already assigned to the student and the requests remaining in his list.If no conflicts occur and the corresponding p-value is greater than that associated with the section requested, then the section requested is replaced by the section tested.This continues until all sections of the course have been similarly examined.The conflict-free section with the largest p-value is thus assigned.(It may be the section requested.)The next request in the list is then examined until completion.It will still be necessary to "close" sections if all available seats have been assigned.When this happens it be-Communications of the ACM Volume 9 / Number 5 /