Collaborative Research Proj 2
Collaborative Research Proj 2 MCS 7033
Popular in Course
Popular in Math
This 0 page Class Notes was uploaded by Miss Marquis Wilderman on Sunday November 1, 2015. The Class Notes belongs to MCS 7033 at Greater Lawrence Technical School taught by Staff in Fall. Since its upload, it has received 22 views. For similar materials see /class/233385/mcs-7033-greater-lawrence-technical-school in Math at Greater Lawrence Technical School.
Reviews for Collaborative Research Proj 2
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 11/01/15
Development of University Timetabling System By Using Evolution Strategies and Simulated Annealing Endi Wu EDS PLM Solutions Troy MI USA Endiwuugscom Submitted to Dr ChanJim Chung LTUjlICS Department in partial fulfillment of the requirements for MCS 7033 Collaborative Research Project 11 class in Fall 2001 1 System Input Format There are two les needed to create for scheduling One is teacher schedule le that includes time slots room available and teacher s preference for the class The other is student survey data that includes time preferred by student for classes The structure of two les as follows Teacher schedule le T0 T1 T2 T3 3 C0 C1 C2 C3 T0 C4 T1 gt Student survey le gt Student ID 501 T1 1C1 T0 201 T2 3C1 T1 4C2T1 503 T0 6C4T1 I Class ID Time slots available Rooms available at one time slot Class taught time means can be taught at any time otherwise this class can be taught at only that speci c time gt Preferable Time 2 Algorithm Timetabling is the assignment of time slots to a set of events subject to constraints on these assignments The NPcomplete classes and time slots that bring highest score is a constraint satisfaction problem after evaluating student preferable time Here I introduce two algorithms with different kinds of constraints to optimize the score 21 Evolutionary Algorithm 1 plus 1 Basic algorithm is initialize one schedule using this schedule to generate another schedule by random method compare two schedule higher score schedule will survive and generate next schedule until no generate can be produced During the reproducing a legal schedule needs to be found such that no room is expected to accommodate more than one class at a time The constraints for this problem can be hard strict or generous 21 Strict rule Strict constraints are usually constraints that physically cannot be violated This includes events that must not overlap in time such as 0 Class must be taught by the specified time appointed by professor One class taught by only one time Algorithm Scheduleparentlnitialize schedule init flle For genl to Maximum generation do Schedulechild generateScheduleparent While HardConstraintSchedulechild return ture If ScoreSchedulechild lt ScoreScheduleparent Scheduleparent Schdulechild End for 212 Generous rule Generous constraints are usually constraints that can be violated in certain range Because sometime illegal schedule will be adjusted to good result Algorithm Scheduleparent Initialize schedule init file For genl to Maximum generation SchedulechildgenerateScheduleparent if GeneralConstraintSchedulechild If ScoreSchedulechild lt ScoreScheduleparent Scheduleparent Schdulechild EndIF EndIF Else IfInRange Scheduleparent Schdulechild EndIF Else Continues EndFor 22 Simulated Annealing The 39 39 J quot SA r J uses the M r quot Algorithm but varies the temperature parameter T from a high value system at melting point to a low value system at freezing point The full SA procedure for minimization is then as follows for maximization set EE Initialize T Generate random con guration X 01d WHILE T gt T min DO FORiltoNc DO generate new con guration X new calculate new energy E new calculate VE E new 7 E and IF VE lt 0 or random lt prob e 39VET THEN X old X new E old E new END IF END FOR reduce T END WHILE Where N e is the number of random changes in con guration at each temperature and is chosen so that the con guration has reached a minimum energy state for the current temperature The variable random is a randomly generated number in the range 01 22 Strict rule Algorithm Initialize T Generate random con guration X 01d WHILE T gt T min DO FORiltoNc DO generate new con guration X new IF HighContraintX new IF inRange X old X new continues calculate new score E new calculate VE E new 7 E and IF VE lt 0 or random lt prob e 39VET THEN X old X new E old E new END IF END FOR reduce T END WHILE 222 Generous rule Algorithm Initialize T Generate random con guration X and WHILE T gt T min DO FORiltoNc DO generate new con guration X new IF HighContraintX new Break ENDIF ELSE calculate new score E new calculate VE E new 7 E 01d IF VE lt 0 or random lt prob e 39VET THEN X old X new E old E new END IF END FOR reduce T END WHILE 3 Sample Result Sample Result Include Large number of classes 1 EC Strict with 150 classes 2760 preferable time 2 EC Generous with 150 classes 2760 preferable time 3 SA Strict with 150 classes 2760 preferable time 4 SA Generous with 150 classes 2760 preferable time Picture only Medium number of classes 5 SA Strict with 150 classes 1337 preferable time 6 SA Generous with 150 classes 1337 preferable time 7 EC Strict with 150 classes 1337 preferable time 8 EC Generous with 150 classes 1337 preferable time Picture only Small number of classes 9 EC Strict with 2 classes 43 preferable time 10 EC Generous with 2 classes 43 preferable time 11 SA Strict with 2 classes 43 preferable time 12 SA Generous with 2 classes 43 preferable time Picture final class assignment using program and manpower mama some uu 15mm an Genevauun 1 Evolution Computation Strict 150 classes total score 443 ml l acme uu 15mm nu Genevauun 2 Evolution Computation Generous 150 classes total score 433 u u I same uu 2n Hempevamr 3 Simulated Annealing Stricg 150 classes total score 383 W 39 h Scum W 95 39 2n Uempevamy 4 Simulated Annealing Generous 150 classes total score 396 mama some 75 2n rampevamr 5 Simulated Annealing Stricg 75 classes total score 312 u u I same 75 2n rampeva 6 Simulated Annealing Generous 75 classes total score 312 mama Scum 75m 339 75mm u Genevatmn 7 Evolution Computation Strict 75 classes total score 339 W 39 Tammi Scum 75m 351 75mm u Genevauun 8 Evolution Computation Generous 75 classes total score 351 mama some 2 2n zann Genevauun 9 Evolution Computation Strict 2 classes total score 20 guusmedulu u u u m mi some 2U 2U mun Genevatmn 10 Evolution Computation Generous 2 classes total score 20 in I Scuveh m 2n Uempevam 11 Simulated Annealing Strict 2 classes total score 20 12 Simulated Annealing Generous 2 classes total score 20 Student Survey File Teacher Schedule File 0 C0 T0 T0 T1 T2 1C0 T1 2 2 C0 T2 C0 3 C0 T2 C1 4C0 T2 5 C0 T2 6 C0 T2 7C0 T2 8 C0 T0 9 C0 T0 10 C0 T2 11 C0 T0 12 C0 T1 13 C0 T2 14 C0 T0 15 C0 T2 16 C0 T0 17 C0 T1 18 C0 T1 19 C0 T2 20 C0 T1 21 C1 T1 22 C1 T1 23 C1 T2 24 C1 T2 25 C1 T0 26 C1 T1 27 C1 T2 28 C1 T0 29 C1 T1 30 C1 T1 31 C1 T2 32 C1 T1 33 C1 T0 34 C1 T1 35 C1 T0 36 C1 T1 37 C1 T0 38 C1 T1 39 C1 T1 40 C1 T2 41 C1 T2 42 C1 T2 Class Assignment using program 1 EC Strict with 2 classes 43 preferable time Result C0 T2 C1 T1 Score 20 2 EC Generous with 2 classes 43 preferable time Result C0 T2 C1 T1 Score 20 3 SA Strict with 2 classes 43 preferable time Result C0 T2 C1 T1 Score 20 4 SA Generous with 2 classes 43 preferable time Result C0 T2 C1 T1 Score 20
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'