Ứng dụng thuật toán mô phỏng luyện kim (Simulated Annealing) xây dựng chương trình quản lý ký túc xá đại học Bách Khoa

trình saép xeáp phoøng maø trong phoøng toàn taïi nhöõng sinh vieân thích nghe nhaïc vaø nhöõng sinh vieân khoâng thích nghe nhaïc ôû chung. Loãi naøy ñöôïc tính nhö sau: min(soá sinh vieân thích nghe nhaïc, soá sinh vieân khoâng thích nghe nhaïc )* ERROR_MUSIC. Hoïc khuya: Loãi naøy sinh ra khi trong quaù trình saép xeáp phoøng maø xaûy ra tình traïng trong phoøng coù nhöõng sinh vieân hoïc khuya vaø khoâng thích hoïc khuya ôû chung. Loãi naøy ñöôïc tính nhö sau: min(soá sinh vieân hoïc khuya, soá sinh vieân khoâng hoïc khuya)* ERR_STUDY_LATE. Chôi game: Loãi naøy sinh ra khi saép xeáp phoøng maø trong phoøng toàn taïi nhöõng sinh vieân thích chôi game vaø nhöõng sinh vieân khoâng thích chôi game ñöôïc xeáp ôû chung. Loãi naøy ñöôïc tính nhö sau: min(soá sinh vieân thích chôi game , soá sinh vieân khoâng thích chôi game ) * ERROR_PLAY_GAME. Theå thao: Loãi naøy xaûy ra khi saép xeáp phoøng maø trong phoøng coù nhöõng sinh vieân thích chôi theå thao vaø nhöõng sinh vieân khoâng thích chôi theå thao ôû chung. Loãi naøy ñöôïc tính: min(soá sinh vieân thích chôi theå thao , soá sinh vieân khoâng thích chôi theå thao ) * ERROR_SPORT. Huùt thuoác: Loãi naøy xaûy ra khi trong quaù trình saép xeáp phoøng cho sinh vieân, trong phoøng coù nhöõng sinh vieân huùt thuoác vaø nhöõng sinh vieân khoâng huùt thuoác ôû chung. Loãi naøy ñöôïc tính nhö sau: min(soá sinh vieân huùt thuoác , soá sinh vieân khoâng huùt thuoác) * ERR_SMOKING. Baïn thaân ôû cuøng phoøng: Loãi naøy sinh ra trong khi saép xeáp phoøng cho töøng sinh vieân, ngöôøi baïn maø sinh vieân naøy ñaêng kyù ôû chung khoâng khoâng ñöôïc xeáp cuøng phoøng vôùi sinh vieân nhö yeâu caàu. Loãi naøy ñöôïc tính nhö sau: ERR_FRIEND * #soá sinh vieân khoâng thoaû maõn. Baïn cuøng khoa: Khoa cuûa phoøng ñöôïc xaùc ñònh theo soá ñoâng caùc sinh vieân ôû phoøng ñoù. Vaø loãi naøy sinh ra khi moät phoøng xeáp toaøn caùc sinh vieân cuøng khoa khoâng ñöôïc thoûa maõn. Loãi naøy ñöôïc tính nhö sau: #soá sinh vieân khaùc khoa * ERR_DIFF_DEPART. Baïn cuøng queâ: Queâ quaùn cuûa caùc sinh vieân trong moãi phoøng ñöôïc xaùc ñònh theo soá ñoâng caùc sinh vieân ôû phoøng ñoù. Loãi naøy sinh ra khi toàn taïi moät phoøng coù caùc sinh vieân queâ quaùn khaùc nhau. Cuï theå, loãi naøy ñöôïc tính nhö sau: #soá sinh vieân khoâng cuøng queâ * ERR_DIFF_HOMETOWN. Baïn cuøng khoaù hoïc: Khoùa hoïc ñöôïc tính theo khoaù hoïc cuûa soá ñoâng sinh vieân trong phoøng. Loãi naøy sinh ra khi coù caùc sinh vieân khaùc khoùa ôû chung moät phoøng. Cuï theå, loãi naøy ñöôïc tính nhö sau: #soá sinh vieân khoâng cuøng khoaù hoïc * ERR_DIFF_YEAR. Baïn cuøng tuoåi: Tuoåi cuûa sinh vieân trong moãi phoøng ñöôïc xaùc ñinh theo tuoåi cuûa soá ñoâng sinh vieân trong phoøng. Loãi naøy sinh ra khi coù caùc sinh vieân khoâng cuøng tuoåi soáng chung moät phoøng. Loã naøy ñöôïc tính nhö sau: #soá sinh vieân khoâng cuøng tuoåi * ERR_AGE. Toùm laïi, baûng lieät keâ tieâu chí caùc raøng buoäc ñöôïc duøng trong luaän vaên vaø giaù trò chi phí hay ñoä öu tieân ñeå tính chi phí cho caùc tieâu chí naøy ñöôïc trình baøy nhö sau: Baûng 3-1: Toång keát caùc loaïi raøng buoäc meàm cho baøi toaùn xeáp phoøng Teân raøng buoäc Moâ taû Giaù trò ERR_DORM Loãi khi sinh vieân choïn daõy nhaø maø khoâng ñöôïc thoaû maõn 10 ERR_ROOM Loãi khi sinh vieân choïn loaïi phoøng maø khoâng ñöôïc thoaû maõn 10 ERR_BED Loãi khi sinh vieân choïn taàng cuûa giöôøng maø khoâng ñöôïc thoaû maõn 7 ERR_PRICE Loãi khi sinh vieân choïn giaù thueâ maø khoâng ñöôïc thoaû maõn 15 ERR_FLOOR Loãi khi sinh vieân choïn taàng ñeå ôû maø khoâng ñöôïc thoaõ maõn 12 ERR_MUSIC Loãi khi sinh vieân thích nghe nhaïc ñöôïc xeáp trong phoøng khoâng thích nghe nhaïc hoaëc ngöôïc laïi 5 ERR_STUDY_LATE Loãi khi sinh vieân thích hoïc khuya ñöôïc xeáp trong phoøng khoâng thích hoïc khuya hoaëc ngöôïc laïi 3 ERR_PLAY_GAME Loãi khi sinh vieân thích chôi game ñöôïc xeáp trong phoøng khoâng thích chôi game hoaëc ngöôïc laïi 7 ERR_SPORT Loãi khi sinh vieân thích chôi theå thao ñöôïc xeáp trong phoøng khoâng thích chôi theå thao hoaëc ngöôïc laïi. 3 ERR_SMOKING Loãi khi sinh vieân thích huùt thuoác ñöôïc xeáp trong phoøng khoâng huùt thuoác hoaëc ngöôïc laïi. 20 ERR_FRIEND Loãi khi sinh vieân choïn baïn thaân ôû cuøng phoøng nhöng khoâng ñöôïc thoaõ maõn. 8 ERR_DIFF_DEPART Loãi khi sinh vieân khaùc khoa ôû cuøng phoøng vôùi nhau. 4 ERR_DIFF_HTOWN Loãi khi sinh vieân coù queâ quaùn khaùc nhau ôû cuøng phoøng vôùi nhau 4 ERR_DIFF_YEAR Loãi khi sinh vieân ôû caùc naêm hoïc khaùc nhau ñöôïc xeáp cuøng phoøng vôùi nhau. 4 ERR_AGE Loãi khi caùc sinh vieân khoâng cuøng tuoåi ñöôïc xeáp cuøng phoøng vôùi nhau 4 ERR_SAME_ROOM Loãi khi sinh vieân xin ñoåi phoøng nhöng ñöôïc xeáp laïi phoøng cuõ. 50 ERR_PARTIAL_FILL Loãi khi xeáp sinh vieân vaøo phoøng khoâng ñaày. 10 3.2 Haøm muïc tieâu Ñeå tieán haønh toái öu baøi toaùn xeáp phoøng, chuùng ta caàn phaûi coù moät tieâu chí ñeå ñaùnh giaù xem traïng thaùi hieän taïi cuûa heä thoáng coù toát hay khoâng hay noùi cuï theå hôn, coù bao nhieâu yeâu caàu cuûa caùc sinh vieân khoâng ñöôïc thoaû maõn. Trong luaän vaên naøy, haøm muïc tieâu f ñöôïc ñònh nghóa laø toång caùc yeâu caàu khoâng ñöôïc thoaû maõn cuûa taát caû caùc sinh vieân. 3.2.1 Giôùi thieäu veà haøm muïc tieâu Haøm muïc tieâu duøng cho heä thoáng ñöôïc ñònh nghóa laø moät aùnh xaï f treân mieàn trò laø taäp hôïp caùc sinh vieân vaø caùc phoøng, giöôøng coù trong kyù tuùc xaù. Moät traïng thaùi cuûa döõ lieäu laø moät caùch saép xeáp caùc sinh vieân vaøo caùc giöôøng theo caùch cuï theå naøo ñoù. Aùnh xaï f chuyeån töø moät traïng thaùi döõ lieäu sang moät soá nguyeân khoâng aâm ñöôïc goïi laø ñieåm cuûa traïng thaùi ñoù. Neáu ñieåm naøy baèng 0 thì ta ñaït ñöôïc traïng thaùi lyù töôûng, ôû traïng thaùi naøy, moïi yeâu caàu cuûa taát caû caùc sinh vieân ñeàu ñöôïc thoaû maõn. Khôûi ñaàu töø moät traïng thaùi baát kyø naøo ñoù, chuùng ta coá gaéng caûi thieän traïng thaùi naøy sang caùc traïng thaùi laân caän baèng caùch choïn moät sinh vieân ngaãu nhieân baát kyø, chuùng ta coá gaéng chuyeån sinh vieân naøy sang moät giöôøng ñöôïc choïn ngaãu nhieân khaùc. 3.2.2 Coâng thöùc xaùc ñònh haøm muïc tieâu Haøm muïc tieâu ñöôïc ñònh nghóa nhö sau: f(e) =(slw(s) RSerrj(e,s) + RSerrj(e,s)) + (slw(s) SSerrj(e,s,r) + SSerrj(e,s,r)) Trong ñoù caùc thoâng soá coù yù nghóa nhö sau: e: chæ traïng thaùi xeáp phoøng hieän taïi. m: soá sinh vieân. n: soá phoøng. t: soá sinh vieân trong töøng phoøng. slw: laø chæ soá öu tieân daønh cho sinh vieân laâu naêm trong kyù tuùc xaù vaø sinh vieân noäp hoà sô sôùm. RSw: laø taäp hôïp caùc raøng buoäc phoøng-sinh vieân coù troïng soá. RS: laø taäp hôïp caùc raøng buoäc phoøng-sinh vieân khoâng coù troïng soá. RSerr: laø taäp hôïp caùc loãi lieân quan ñeán caùc raøng buoäc phoøng-sinh vieân. SSw: laø taäp hôïp caùc raøng buoäc sinh vieân – sinh vieân coù troïng soá. SS: laø taäp hôïp caùc raøng buoäc sinh vieân – sinh vieân khoâng coù troïng soá. SSerr: laø taäp hôïp caùc loãi lieân quan ñeán sinh vieân – sinh vieân. 3.3 Lòch bieåu laøm nguoäi Lòch bieåu laøm nguoäi ñöôïc theå hieän baèng söï giaûm nhieät ñoä trong quaù trình laøm nguoäi. Trong luaän vaên naøy, chuùng toâi söû duïng phöông phaùp lòch bieåu laøm nguoäi caáp soá nhaân vaø phöông phaùp lòch bieåu laøm nguoäi caáp soá nhaân vôùi taùi nung noùng khi möùc naêng löôïng ñaït traïng thaùi caân baèng nhaèm giuùp baøi toaùn thoaùt khoûi trình traïng toái öu cuïc boä. Caùc lòch bieåu naøy seõ ñöôïc söû duïng laøm lòch bieåu cô baûn trong suoát quaù trình moâ phoûng luyeän kim. Nhoùm chuùng toâi seõ thöû hieän thöïc giaûi thuaät ISA treân lòch bieåu laøm nguoäi caáp soá nhaân. 3.3.1 Lòch bieåu laøm nguoäi caáp soá nhaân Trong lòch bieåu laøm nguoäi naøy, nhieät ñoä ñöôïc giaûm theo caáp soá nhaân theo coâng thöùc: Tk+1=αTk (3.1) trong ñoù α ñöôïc xaùc ñònh baèng soá laàn chaïy mong muoán cuûa ngöôøi duøng ñoái vôùi giaûi thuaät SA. α ñöôïc xaùc ñònh baèng coâng thöùc sau döïa treân ñieàu kieän döøng cuûa giaûi thuaät SA: T0 * αN = T1 (3.2) Theo Burke et al [10] α = 1 - ( ln(T0) –ln(T1) )/ N (3.3) Vôùi T0 laø nhieät ñoä ban ñaàu, vaø T1 laø nhieät ñoä keát thuùc, N laø soá laàn chaïy cuûa giaûi thuaät SA do ngöôøi duøng cung caáp. Taïi moãi nhieät ñoä T, soá laàn laëp laïi cuûa giaûi thuaät ñöôïc ñònh nghóa baèng haèng soá nrep. Haèng soá nrep ñöôïc xaùc ñònh baèng thöïc nghieäm vaø thay ñoåi tuøy theo öùng duïng. Ñoái vôùi baøi toaùn xeáp phoøng cho sinh vieân ôû kyù tuùc xaù, thöïc nghieäm cho thaáy nrep coù giaù trò baèng 6 laø toát nhaát. 3.4 Lôøi giaûi laân caän Ñeå coù theå aùp duïng ñöôïc giaûi thuaät moâ phoûng luyeän kim caûi tieán ISA, ta phaûi xaùc ñònh ñöôïc moät taäp caùc lôøi giaûi laân caän s1 cho lôøi giaûi s0. Trong baøi toaùn xeáp phoøng cho sinh vieân ôû kyù tuùc xaù, töø lôøi giaûi s0 laø moät caùch saép xeáp phoøng naøo ñoù, ta choïn ngaãu nhieân moät sinh vieân, sau ñoù ta laïi tieáp tuïc choïn ngaãu nhieân moät sinh vieân khaùc cuøng giôùi tính vôùi sinh vieân ñaõ choïn sao cho söï hoaùn ñoåi hai sinh vieân naøy khoâng vi phaïm caùc raøng buoäc cöùng, traùo ñoåi giöôøng cuûa hai sinh vieân naøy, ta thu ñöôïc lôøi giaûi s1 laø moät caùch xeáp phoøng khaùc, laân caän vôùi lôøi giaûi s0. Caùc lôøi giaûi laân caän naøy seõ ñöôïc söû duïng trong caùc böôùc söûa chöõa cuûa giaûi thuaät. 3.5 Thieát keá heä thoáng Trong chöông trình quaûn lyù vieäc xeáp phoøng cho sinh vieân ôû kyù tuùc xaù, chuùng ta duøng giaûi thuaät moâ phoûng quaù trình luyeän kim ISA ñeå toái öu hoaù keát quaû xeáp phoøng. Quaù trình xeáp phoøng ñöôïc chia ra laøm hai böôùc: Böôùc 1 cuûa phöông phaùp naøy giaûi quyeát baøi toaùn xeáp phoøng sao cho söï xeáp phoøng ban ñaàu thoûa maõn taát caû caùc raøng buoäc cöùng cuûa baøi toaùn nhö: giôùi tính, soá sinh vieân trong töøng phoøng, toång soá sinh vieân va økhaû naêng ñaùp öùng cuûa kyù tuùc xaù, caùc sinh vieân nöõ vaø sinh vieân thuoäc dieän chính saùch cuõng ñöôïc öu tieân giaûi quyeát vaøo ôû kyù tuùc xaù. Böôùc 2 laø böôùc caûi thieän chaát löôïng cuûa söï xeáp phoøng ñöôïc sinh ra töø giai ñoaïn 1 döïa vaøo vieäc kieåm tra lôøi giaûi coù thoûa maõn caùc raøng buoäc meàm ñaõ ñöôïc neâu ra ôû phaàn trình baøy tröôùc hay khoâng. Cuï theå laø vieäc saép xeáp phaûi thoûa maõn yeâu caàu veà phoøng cuûa sinh vieân nhö ôû chung vôùi baïn cuøng chuyeân ngaønh, ñoä tuoåi, sôû thích vaø choïn loaïi phoøng phuø hôïp. Hình veõ 3.1 moâ taû toång quan veà caùc chöùc naêng cuûa heä thoáng xeáp phoøng cho sinh vieân ôû kyù tuùc xaù: Caùc khoái chöùc naêng chính cuûa heä thoáng xeáp phoøng sinh vieân trong kyù tuùc xaù goàm coù: khoái chöùc naêng quaûn lyù caùc thoâng tin veà sinh vieân vaø thoâng tin ñaêng kyù phoøng cuûa sinh vieân, khoái chöùc naêng thöïc hieän vieäc xeáp phoøng vaø khoái chöùc naêng quaûn lyù taøi nguyeân cuûa kyù tuùc xaù nhö phoøng, giöôøng,… Hình 3-1: Moâ taû toång quan heä thoáng. 3.5.1 Khoái chöùc naêng quaûn lyù sinh vieân Khoái chöùc naêng naøy cung caáp cho ban quaûn lyù kyù tuùc xaù coâng cuï ñeå quaûn lyù hoà sô caùc thoâng tin veà sinh vieân. Ban quaûn lyù kyù tuùc xaù vaø sinh vieân coù theå töông taùc vôùi heä thoáng qua module naøy ñeå caäp nhaät thoâng tin vaøo heä thoáng cuõng nhö laáy thoâng tin output töø heä thoáng, cuï theå laø moät soá chöùc naêng nhö sau: Nhaän vaøo hoà sô ñaêng kyù vaøo ôû kyù tuùc xaù cuûa sinh vieân. Chænh söûa caùc thoâng tin sinh vieân vaø hoà sô ñaêng kyù. Cho pheùp hieån thò keát quaû xeáp phoøng. Tìm kieám sinh vieân vaø in ra hoaù ñôn cho sinh vieân. 3.5.2 Khoái chöùc naêng xeáp phoøng Khoái chöùc naêng naøy thöïc hieän coâng vieäc sinh ra caùch xeáp phoøng ban ñaàu, trong ñoù caùch xeáp phoøng ban ñaàu naøy phaûi thoûa maõn taát caû caùc raøng buoäc cöùng ñaõ neâu nhö giôùi tính, ñoái töôïng chính saùch, soá löôïng sinh vieân trong phoøng. Caùch xeáp phoøng ban ñaàu naøy cuõng chöa ñöôïc toái öu hoaù neân veà maët lyù thuyeát chuùng ta coù theå xeáp caùc sinh vieân vaøo phoøng moät caùch tuaàn töï. Tuy nhieân, ñeå coù theå haïn cheá ñöôïc soá laàn thay ñoåi choã ôû cuûa caùc sinh vieân sau naøy, ta seõ öu tieân xeáp caùc sinh vieân vaøo phoøng maø coù haøm muïc tieâu ñoái vôùi caùch xeáp phoøng cuûa sinh vieân naøy coù giaù trò nhoû nhaát, nghóa laø ñaït ñöôïc traïng thaùi toát nhaát coù theå coù ñoái vôùi sinh vieân ngay taïi thôøi ñieåm xeáp phoøng. Sau ñoù khoái chöùc naêng naøy thöïc hieän vieäc aùp suïng kyõ thuaät ISA vaøo ñeå caûi thieän caùch xeáp phoøng ban ñaàu thaønh lôøi giaûi toát hôn. Ñaây laø khoái chöùc naêng chính cuûa luaän vaên. 3.5.3 Khoái chöùc naêng quaûn lyù kyù tuùc xaù Khoái chöùc naêng naøy duøng ñeå giuùp cho ban quaûn lyù kyù tuùc xaù quaûn lyù caùc thoâng tin veà taøi nguyeân cuûa kyù tuùc xaù nhö caùc daõy nhaø, taàng, phoøng cuøng vôùi caùc ñaëc ñieåm cuûa taøi nguyeân naøy. 3.6 Thieát keá döõ lieäu cho chöông trình Cô sôû döõ lieäu ñöôïc aùp duïng cho heä thoáng laø heä quaûn trò cô sôû döõ lieäu Microsoft SQL Server 2000 nhaèm löu tröõ caùc thoâng tin cuûa caùc ñoái töôïng heä thoáng. Caùc nhoùm thoâng tin naøy bao goàm: thoâng tin quaûn lyù kyù tuùc xaù, thoâng tin chöùa caùc nguyeän voïng cuûa sinh vieân, thoâng tin chöùa chi phí cho caùc raøng buoäc khi xeáp phoøng vaø thoâng tin veà caáu hình cho giaûi thuaät xeáp phoøng. Hình 3-2: Sô ñoà ERD cho cô sôû döõ lieäu chöông trình 3.6.1 Döõ lieäu quaûn lyù kyù tuùc xaù Döõ lieäu ñeå quaûn lyù kyù tuùc xaù bao goàm caùc baûng danh muïc phoøng, danh muïc giöôøng, danh muïc sinh vieân moâ taû caùc phoøng trong kyù tuùc xaù, moâ taû caùc giöôøng, thoâng tin veà sinh vieân vaø keát quaû xeáp phoøng cuûa sinh vieân. Chi tieát thieát keá cho caùc baûng ñöôïc moâ taû nhö sau: Baûng sinh vieân: chöùa caùc thoâng tin veà caù nhaân cuûa sinh vieân. Baûng 3-2: Moâ taû döõ lieäu cuûa baûng sinh vieân Teân coät Kieåu döõ lieäu Moâ taû Masv Varchar Löu tröõ maõ sinh vieân, laø khoaù chính Hoten nvarchar Löu tröõ hoï vaø teân sinh vieân Ngaysinh Smalldatetime Ngaøy thaùng naêm sinh cuûa sinh vieân Noisinh nvarchar Nôi sinh Quoctich nvarchar Quoác tòch Tongiao nvarchar Toân giaùo SoCMND Varchar Soá chöùng minh thö cuûa sinh vieân Ñiachi nvarchar Ñòa chæ thöôøng truù cuûa sinh vieân Gioitinh char Giôùi tính Mauutien char Maõ öu tieân cuûa sinh vieân khi ñaêng kyù vaøo ôû KTX Ngayñk Smalldatetime Ngaøy noäp ñôn ñaêng kyù vaøo kyù tuùc xaù Baûng phoøng: chöùa caùc thoâng tin veà caùc phoøng trong kyù tuùc xaù. Baûng 3-3: Moâ taû döõ lieäu cho baûng phoøng Teân coät Kieåu döõ lieäu Moâ taû Maphong Varchar Maõ phoøng, laøm khoaù chính Sogiuong Int Soá giöôøng maø phoøng naøy coù Tinhtrang char Phoøng coøn troáng hay ñaõ ñaày Danhcho char Phoøng daønh cho nam hay nöõ Baûng giöôøng: chöùa caùc thoâng tin veà giöôøng ôû trong kyù tuùc xaù. Baûng 3-4: Moâ taû döõ lieäu cho baûng giöôøng Teân coät Kieåu döõ lieäu Moâ taû Magiuong Varchar Maõ giöôøng Maphong Varchar Maõ phoøng Giathue Int Giaù thueâ cuûa giöôøng Tinhtrang char Giöôøng coøn troáng hay khoâng Baûng xeáp phoøng: chöùa caùc thoâng tin veà keát quaû xeáp phoøng cuûa caùc sinh vieân. Baûng 3-5: Moâ taû döõ lieäu cho baûng xeáp phoøng Teân coät Kieåu döõ lieäu Moâ taû STT Int Soá thöù töï Masv Varchar Maõ sinh vieân Magiuong Varchar Maõ giöôøng maø sinh vieân naøy ñöôïc xeáp vaøo ôû Maphong Varchar Maõ phoøng maø sinh vieân naøy ñöôïc xeáp vaøo 3.6.2 Döõ lieäu ñaêng kyù vaøo ôû cuûa sinh vieân Nhoùm döõ lieäu döïa treân ñaêng kyù vaøo ôû cuûa sinh vieân bao goàm caùc baûng chöùa döõ lieäu theå hieän caùc mong muoán, caùc yeâu caàu cuûa sinh vieân khi vaøo ôû kyù tuùc xaù. Caùc thoâng tin naøy ñöôïc löu laïi khi sinh vieân noäp ñôn ñaêng kyù vaøo ôû kyù tuùc xaù vaø ñöôïc duøng laïi trong giaûi thuaät SA ñeå laøm cô sôû cho vieäc tính toaùn caùc haøm chi phí. Chi tieát cho caùc baûng ñöôïc moâ taû nhö sau: Baûng tieâu chí choïn baïn: chöùa caùc thoâng tin moâ taû yeâu caàu veà baïn cuøng phoøng ñoái vôùi moät sinh vieân. Baûng 3-6: Moâ taû döõ lieäu baûng tieâu chí choïn baïn Teân coät Kieåu döõ lieäu Moâ taû Masv Varchar Maõ sinh vieân. Cungkhoa Char Choïn baïn cuøng khoa hay khoâng. Cungque Char Choïn baïn cuøng queâ hay khoâng. Cungnam Char Choïn baïn hoïc cuøng naêm hoïc hay khoâng. Cungtuoi Char Choïn baïn cuøng tuoåi ôû chung phoøng hay khoâng. Banthan Char Choïn baïn thaân ôû cuøng phoøng hay khoâng. Mabanthan Varchar Maõ baïn thaân maø sinh vieân naøy choïn ôû cuøng phoøng. Baûng tieâu chí choïn phoøng: chöùa caùc thoâng tin moâ taû yeâu caàu veà phoøng ôû maø sinh vieân naøy ñaõ choïn nhö yeâu caàu veà giaù thueâ, taàng giöôøng, daõy nhaø, taàng,... Baûng 3-7 Moâ taû döõ lieäu baûng tieâu chí choïn phoøng Teân coät Kieåu döõ lieäu Moâ taû Masv Varchar Maõ sinh vieân Giathue Int Giaù thueâ phoøng maø sinh vieân choïn Tanggiuong Int Sinh vieân choïn giöôøng ôû taàng 1 hay 2 Sogiuong Int Soá giöôøng trong 1 phoøng Tang Int Phoøng ôû taàng naøo Daynha Varchar Daõy nhaø Baûng sôû thích: chöùa caùc thoâng tin moâ taû sôû thích cuûa sinh vieân naøy vaø thoâng thöôøng, caùc sinh vieân mong muoán ñöôïc ôû chung phoøng vôùi caùc baïn khaùc coù cuøng sôû thích vôùi mình. Baûng 3-8: Moâ taû döõ lieäu baûng sôû thích Teân coät Kieåu döõ lieäu Moâ taû Masv Varchar Maõ sinh vieân TenST VarChar Teân cuûa sôû thích ñònh nghóa trong baûng chi phí sôû thích Giatri Char Sinh vieân coù sôû thích naøy hay khoâng Baûng ñaêng kyù laïi: chöùa thoâng tin caùc sinh vieân xin ñöôïc ñoåi phoøng Baûng 3-9 Moâ taû döõ lieäu baûng sinh vieân ñaêng kyù laïi Teân coät Kieåu döõ lieäu Moâ taû Masv Varchar Maõ sinh vieân Phongo Varchar Ñang ôû phoøng naøo 3.6.3 Döõ lieäu chi phí cho caùc raøng buoäc Nhoùm thoâng tin naøy ñöôïc duøng ñeå löu laïi chi phí cho caùc raøng buoäc, moãi loaïi raøng buoäc neáu khoâng ñöôïc thoaû maõn thì seõ ñöôïc tính chi phí ñöôïc löu trong caùc baûng naøy. Chi tieát cuûa caùc baûng naøy nhö sau. Baûng chi phí coá ñònh: Löu tröõ chi phí cho caùc raøng buoäc coá ñònh (khoâng phaûi raøng buoäc veà sôû thích) neáu nhö caùc raøng buoäc naøy khoâng ñöôïc thoûa maõn. Baûng 3-10 Moâ taû baûng chi phí coá ñònh Teân coät Kieåu döõ lieäu Moâ taû Item Varchar Teân cuûa chi phí, laø khoùa chính Val Int Giaù trò cuûa chi phí töông öùng vôùi teân chi phí ôû treân Baûng chi phí sôû thích: Ñònh nghóa caùc raøng buoäc veà sôû thích vaø chi phí töông öùng khi caùc raøng buoäc naøy khoâng ñöôïc thoûa maõn. Baûng 3-11 Moâ taû baûng chi phí sôû thích Teân coät Kieåu döõ lieäu Moâ taû TenST Varchar Teân cuûa raøng buoäc sôû thích, laø khoùa chính Val Int Giaù trò cuûa chi phí töông öùng vôùi teân raøng buoäc ôû treân 3.7 Thieát keá giao dieän ngöôøi duøng Thoâng qua giao dieän chöông trình, ban quaûn lyù kyù tuùc xaù coù theå töông taùc vôùi heä thoáng veà caùc chöùc naêng quaûn lyù quaù trình xeáp phoøng cho sinh vieân ôû kyù tuùc xaù. Giao dieän chính cuûa chöông trình nhö sau: Hình 3-3: Giao dieän toång quaùt cuûa chöông trình Chöông trình caàn hieän thöïc moät soá nhoùm chöùc naêng chính nhö: 3.7.1 Quaûn trò ngöôøi duøng Nhoùm chöùc naêng naøy hoã trôï ngöôøi duøng caùc chöùc naêng sau: Ñaêng nhaäp: tröôùc khi ngöôøi söû duïng duøng ñöôïc caùc chöùc naêng cuûa chöông trình xeáp phoøng, thì ngöôøi söû duïng phaûi ñaêng nhaäp vaøo heä thoáng vôùi teân ngöôøi duøng vaø maät khaåu do ngöôøi quaûn trò heä thoáng cung caáp nhaèm ñeå taêng cöôøng tính baûo maät cuûa chöông trình. Thoaùt khoûi heä thoáng: cho pheùp ngöôøi söû duïng thoaùt khoûi taøi khoaûn hieän ñang söû duïng treân heä thoáng, coù theå ñaêng nhaäp vaøo vôùi taøi khoaûn môùi. Thoaùt chöông trình: cho pheùp ngöôøi söû duïng thoaùt khoûi chöông trình xeáp phoøng. 3.7.2 Quaûn lyù sinh vieân Nhoùm chöùc naêng naøy hoã trôï ngöôøi duøng caùc chöùc naêng sau: Ñaêng kyù sinh vieân: chöùc naêng naøy cho ban quaûn lyù nhaäp hoà sô ñaêng kyù sinh vieân vaøo ôû kyù tuùc xaù. Khi sinh vieân naøy ñöôïc ñaêng kyù vaøo thì lôøi giaûi ban ñaàu ñöôïc sinh ra. Neáu khoâng coøn phoøng daønh thì sinh vieân naøy ñöôïc theâm vaøo danh saùch döï bò. Tìm kieám sinh vieân: chöùc naêng naøy cho pheùp ban quaûn lyù coù theå tìm kieám moïi thoâng tin caù nhaân cuõng nhö veà yeâu caàu choïn phoøng cuûa sinh vieân moät caùch nhanh choùng. Chænh söûa thoâng tin sinh vieân: chöùc naêng naøy cho pheùp ban quaûn lyù kyù tuùc xaù coù theå chænh söûa thoâng tin sinh vieân. Xoaù sinh vieân: chöùc naêng naøy cho pheùp ban quaûn lyù kyù tuùc xaù coù theå xoaù sinh vieân khi sinh vieân naøy khoâng coøn ôû kyù tuùc xaù nöõa. 3.7.3 Quaûn lyù kyù tuùc xaù Caùc chöùc naêng quaûn lyù kyù tuùc xaù cho pheùp ngöôøi quaûn lyù kyù tuùc xaù coù theå theâm bôùt vaø chænh söûa caùc thoâng tin sau: Danh muïc phoøng: chöùc naêng naøy cho pheùp heä thoáng in ra danh saùch caùc phoøng trong kyù tuùc xaù. Theâm phoøng: chöùc naêng naøy cho pheùp ban quaûn lyù kyù tuùc xaù theâm vaøo moät phoøng môùi. Xoaù phoøng: chöùc naêng naøy cho pheùp ban quaûn lyù kyù tuùc xaù xoaù caùc phoøng. Thay ñoåi thoâng tin phoøng: chöùc naêng naøy cho pheùp ban quaûn lyù kyù tuùc xaù thay ñoåi thoâng tin veà phoøng cuï theå naøo ñoù. Danh muïc giöôøng: chöùc naêng naøy cho pheùp heä thoáng in ra danh saùch caùc giöôøng trong kyù tuùc xaù. Theâm giöôøng: chöùc naêng naøy cho pheùp ban quaûn lyù theâm moät giöôøng môùi vaøo kyù tuùc xaù. Xoaù giöôøng: chöùc naêng naøy cho pheùp ban quaûn lyù xoaù giöôøng khoûi kyù tuùc xaù. Thay ñoåi thoâng tin giöôøng: chöùc naêng naøy cho pheùp ban quaûn lyù thay ñoåi thoâng tin cuûa giöôøng nhö giaù thueâ, giöôøng taàng maáy, … 3.7.4 Xeáp phoøng Caùc chöùc naêng veà quaûn lyù thoâng tin lieân quan ñeán vieäc xeáp phoøng cho pheùp ngöôøi quaûn lyù coù theå theâm bôùt vaø chænh söûa caùc thoâng tin cuõng nhö thöïc hieän caùc böôùc trong vieäc saép xeáp phoøng nhö sau: Tieâu chí xeáp phoøng: chöùc naêng naøy cho pheùp thay ñoåi chi phí cho caùc raøng buoäc. Thöïc thi giaûi thuaät: chöùc naêng naøy cho pheùp ban quaûn lyù kyù tuùc xaù môû ra moät cöûa soå môùi ñeå ñieàu khieån chöông trình xeáp phoøng nhö choïn soá laàn chaïy cho giaûi thuaät SA hoaëc laø lòch bieåu laøm nguoäi. 3.7.5 Baùo caùo Chöùc naêng naøy cho pheùp ngöôøi söû duïng heä thoáng in ra caùc baùo caùo lieân quan ñeán vieäc quaûn lyù sinh vieân cuõng nhö keát quaû cuûa vieäc saép xeáp phoøng cho sinh vieân ôû kyù tuùc xaù. Caùc baùo caùo thoâng thöôøng goàm coù: Keát quaû xeáp phoøng: chöùc naêng naøy cho pheùp in ra keát quaû xeáp phoøng, keát quaû naøy ñöôïc phaân nhoùm döïa theo maõ phoøng. Danh saùch sinh vieân: chöùc naêng naøy cho pheùp in ra danh saùch taát caû danh saùch sinh vieân xin vaøo ôû kyù tuùc xaù. 3.7.6 Trôï giuùp Heä thoáng cuõng coù phaàn trôï giuùp ñeå giuùp cho ngöôøi duøng coù theå söû duïng heä thoáng deã daøng vaø hieäu quaû hôn vaø tìm kieám thoâng tin lieân quan ñeán chöông trình nhanh hôn. Noäi dung: chöùc naêng naøy cho pheùp hieån thò caùc thoâng tin höôùng daãn söû duïng chöông trình. Thoâng tin veà chöông trình: chöùc naêng naøy cho bieát caùc thoâng tin veà chöông trình, taùc giaû, version… CHÖÔNG 4 HIEÄN THÖÏC VAØ KEÁT QUAÛ THÖÏC NGHIEÄM Chöông naøy seõ trình baøy caùc giaûi thuaät chính duøng ñeå hieän thöïc baøi toaùn xeáp phoøng baèng kyõ thuaät moâ phoûng quaù trình luyeän kim caûi tieán Informed Simulated Annealing (ISA), ñoàng thôøi chöông naøy cuõng trình baøy keát quaû chaïy thöïc nghieäm chöông trình treân taäp döõ lieäu laø 3000 sinh vieân theo lòch bieåu laøm nguoäi caáp soá nhaân. 4.1 Hieän thöïc chöông trình Trong phaàn naøy chuùng toâi seõ trình baøy moät soá giaûi thuaät chính ñöôïc hieän thöïc trong chöông trình. Chöông trình ñöôïc hieän thöïc theo giaûi thuaät ISA (Inform Simulated Annealing), ñaây laø moät caûi tieán cuûa giaûi thuaät SA truyeàn thoáng. Giaûi thuaät ISA döïa vaøo xaùc suaát cuûa caùc caëp bieán – giaù trò ñeå höôùng quaù trình choïn lôøi giaûi laân caän theo moät caùch toát hôn. Trong baøi toaùn naøy, chuùng toâi choïn caëp bieán – giaù trò chính laø caëp sinh vieân vaø giöôøng maø sinh vieân ñoù coù theå ñöôïc saép xeáp vaøo. Chi tieát veà giaûi thuaät ISA seõ ñöôïc trình baøy ñaày ñuû hôn trong phaàn 4.1.5. Ñoàng thôøi, ñeå giaûi thuaät ISA coù theå ñöôïc aùp duïng toát, chuùng toâi choïn lòch bieåu laøm nguoäi caáp soá nhaân coù soá laàn thöïc thi xaùc ñònh tröôùc vôùi muïc tieâu xaùc ñònh ñieåm döøng (stopping-criterion) trong hai phaàn SA hoïc hoûi vaø SA chaïy Caên cöù vaøo tính chaát cuûa baøi toaùn vaø khaû naêng cuûa caùc kyõ thuaät coù theå aùp duïng hieän taïi, chuùng toâi quyeát ñònh chia baøi toaùn xeáp phoøng naøy thaønh hai baøi toaùn rieâng bieät ñoäc laäp vôùi nhau: baøi toaùn xeáp phoøng cho caùc sinh vieân nam vaø baøi toaùn xeáp phoøng cho caùc sinh vieân nöõ. Hai baøi toaùn seõ ñöôïc giaûi quyeát duøng hai engine gioáng nhau döïa theo giaûi thuaät ISA vaø tieán haønh chaïy xen keõ hai engine naøy moät caùch lieân tuïc. Ñeå coù theå chaïy toát hai engine treân cuøng moät cô sôû döõ lieäu chung, nhoùm chuùng toâi nhaän thaáy khaû naêng xöû lyù nhanh vaø lieân tuïc nhieàu caâu truy vaán treân stored procedure cuûa heä quaûn trò cô sôû döõ lieäu Microsoft SQL Server 2000 laø moät phöông tieän quan troïng giuùp chuùng toâi hieän thöïc ñöôïc vieäc chaïy xen keõ hai engine naøy. Chuùng toâi ñaõ taùch nhoû caùc phaàn trong giaûi thuaät ra caùc phaàn nhoû hôn vaø tuøy theo tính chaát maø caùc phaàn naøy seõ ñöôïc hieän thöïc treân ngoân ngöõ C# hay thoâng qua caùc stored procedure caøi ñaët trong cô sôû döõ lieäu. Cuï theå phaàn taïo lôøi giaûi ban ñaàu thoûa maõn raøng buoäc cöùng, phaàn tính chi phí, phaàn choïn caëp sinh vieân ngaãu nhieân thoûa raøng buoäc cöùng, phaàn caäp nhaät cô sôû döõ lieäu xeáp phoøng seõ ñöôïc caøi ñaët thoâng qua stored procedure, phaàn ñieàu khieån giaûi thuaät lieân quan ñeán vieäc thay ñoåi caùc thoâng soá trong cuûa giaûi thuaät ISA ñöôïc vieát trong code C#. 4.1.1 Taïo lôøi giaûi ban ñaàu cho giaûi thuaät SA thoûa maõn raøng buoäc cöùng Khi moät sinh vieân ñaêng kyù vaøo ôû kyù tuùc xaù, heä thoáng seõ löu danh saùch sinh vieân naøy cuõng nhö caùc thoâng tin lieân quan cuûa sinh vieân ñoù cho vieäc xeáp phoøng. Tröôùc khi baét ñaàu giaûi thuaät ISA, heä thoáng seõ tìm taét caû caùc giöôøng coøn troáng theo giôùi tính, sau ñoù seõ duyeät qua danh saùch caùc sinh vieân trong danh saùch chôø xeáp phoøng vaø choïn ra caùc sinh vieân thuoäc dieän öu tieân xeáp phoøng, bao goàm caùc sinh vieân ñaêng kyù laïi vaø caùc sinh vieân thuoäc dieän chính saùch. Caùc sinh vieân naøy seõ ñöôïc xeáp vaøo caùc giöôøng coøn troáng ñaàu tieân theo ñuùng giôùi tính cuûa mình, sau ñoù môùi ñeán caùc sinh vieân khoâng thuoäc dieän öu tieân ñöôïc xeáp vaøo nhöõng giöôøng coøn laïi (cuõng phaûi theo ñuùng giôùi tính) theo thöù töï ngaøy ñaêng kyù vaøo ôû kyù tuùc xaù. Phaàn taïo lôøi giaûi ban ñaàu thoûa maõn raøng buoäc cöùng naøy ñöôïc chuùng toâi caøi ñaët söû duïng stored procedure. Moâ taû cuûa phaàn taïo lôøi giaûi ban ñaàu thoûa maõn raøng buoäc cöùng nhö sau: - Choïn caùc giöôøng coøn troáng, ñöa vaøo baûng GiuongNam vaø GiuongNu theo quy ñònh giôùi tính. - Choïn caùc SV thuoäc dieän ñaêng kyù laïi vaø caùc SV thuoäc dieän chính saùch, xeáp giöôøng cho caùc SV naøy theo ñuùng giôùi tính vaøo baûng XepphongNam hay XepphongNu. - Choïn caùc SV coøn laïi, xeáp theo thöù töï taêng daàn thôøi gian ñaêng kyù, tieáp tuïc xeáp giöôøng cho caùc SV naøy. - Nhöõng SV khoâng coù giöôøng cuõng ñöôïc xeáp vaøo caùc baûng Xepphong, nhöng phaàn maphong vaø magiuong laø null. 4.1.2 Kyõ thuaät choïn lôøi giaûi laân caän Ñaây laø moät kyõ thuaät ñöôïc duøng ñeå giaûi quyeát vieäc toái öu hoùa baøi toaùn xeáp phoøng, kyõ thuaät naøy ñöôïc xaây döïng thaønh moät ñoaïn chöông trình vaø ñöôïc goïi raát nhieàu laàn khi hieän thöïc giaûi thuaät ISA cho vieäc xeáp phoøng. Cuï theå, kyõ thuaät naøy ñöôïc ñònh nghóa nhö sau: -Choïn ngaãu nhieân hai sinh vieân s1 vaø s2 S thoûa moät soá yeâu caàu cuûa baøi toaùn, vôùi S laø taäp hôïp taát caû sinh vieân ñöôïc xeáp phoøng trong kyù tuùc xaù. Tieán haønh ñoåi choå hai sinh vieân s1 vaø s2 ta seõ thu ñöôïc lôøi giaûi laân caän cho quaù trình xeáp phoøng. -Trong baøi toaùn, yeâu caàu choïn hai sinh vieân raát chaët cheõ. Ngoaøi vieäc s1 s2 vaø cuøng giôùi tính, ñeå khoâng vi phaïm raøng buoäc cöùng, chuùng ta chæ cho pheùp s1 vaø s2 ñoåi choã cho nhau khi vaø chæ khi hai sinh vieân naøy cuøng coù phoøng hoaëc moät sinh vieân coù phoøng, moät sinh vieân khoâng coù nhöng caû hai sinh vieân naøy phaûi cuøng thuoäc dieän öu tieân hoaëc khoâng öu tieân. -Ngoaøi ra, ñeå traùnh vieäc phaûi choïn ñi choïn laïi nhieàu laàn caëp sinh vieân do vi phaïm raøng buoäc cöùng, chuùng toâi choïn ngaãu nhieân sinh vieân s1 laø sinh vieân ñaõ coù phoøng, sinh vieân s2 neáu coù phoøng hoaëc cuøng dieän öu tieân vôùi sinh vieân s1 thì dó nhieân ñöôïc ñoãi choã cho sinh vieân s1, neáu khoâng thì chæ tieán haønh choïn laïi sinh vieân s2. Ñieàu naøy seõ laøm cho vieäc choïn caëp sinh vieân ñöôïc tieán haønh nhanh hôn. Kyõ thuaät choïn lôøi giaûi laân caän ñöôïc moâ taû baèng hình veõ 4-1. 4.1.3 Haøm muïc tieâu Nhö ñaõ trình baøy ôû caùc phaàn tröôùc, haøm muïc tieâu ñöôïc xaây döïng nhaèm muïc ñích tính chi phí cho lôøi giaûi cuûa baøi toaùn. Do ñoù, haøm muïc tieâu ñöôïc xaùc ñònh nhieàu laàn trong khi thöïc hieän giaûi thuaät SA, ñaây cuõng laø cô sôû ñeå ñaùnh giaù giaûi thuaät ISA hoaït ñoäng toát hay khoâng. Haøm muïc tieâu ñöôïc xaùc ñònh nhö sau: f(e) =(slw(s) RSerrj(e,s) + RSerrj(e,s)) + (slw(s) SSerrj(e,s,r) + SSerrj(e,s,r)) (4.1) Trong giaûi thuaät ISA, khi tính ñoä cheânh leäch chi phí cuûa traïng thaùi laân caän s so vôùi traïng thaùi hieän taïi s0, chuùng ta khoâng caàn phaûi tính laïi haøm muïc tieâu vì söï cheânh leäch chi phí cuûa hai traïng thaùi baèng vôùi söï thay thay ñoåi chi phí cuûa hai phoøng p vaø p0, öùng vôùi hai phoøng cuûa hai sinh vieân ñöôïc choïn ñeå ñoåi phoøng cuûa hai traïng thaùi s vaø s0. Haøm muïc tieâu do ñoù seõ goàm hai phaàn: haøm tính toång chi phí cuûa traïng thaùi ban ñaàu (haøm naøy chæ ñöôïc goïi moät laàn duy nhaát ngay tröôùc khi thöïc thi giaûi thuaät) vaø haøm tính cheânh leäch chi phí giöõa traïng thaùi hieän taïi vaø traïng thaùi laân caän ngaãu nhieân ñang xem xeùt trong giaûi thuaät (soá laàn goïi haøm naøy laø tuøy theo soá böôùc chaïy cuûa giaûi thuaät). Caû hai haøm tính chi phí naøy ñeàu ñöôïc caøi ñaët thaønh stored procedure trong cô sôû döõ lieäu nhaèm taän duïng söùc maïnh tính toaùn cuûa heä quaûn trò Microsoft SQL Server 2000. Trong caùc stored procedure naøy laïi trieäu goïi caùc stored procedure khaùc caáp nhoû hôn ñöôïc xaây döïng ñeå deã quaûn lyù. Haøm muïc tieâu naøy seõ ñöôïc tính theo löu ñoà giaûi thuaät ôû hình 4-2. Hình 4-1: Kyõ thuaät choïn lôøi giaûi laân caän Hình 4-2: Tính toång chi phí cho giaûi thuaät ISA 4.1.4 Lòch bieåu laøm nguoäi caáp soá nhaân coù soá laàn thöïc thi xaùc ñònh tröôùc Trong lòch bieåu laøm nguoäi naøy, soá laàn chaïy cuûa giaûi thuaät ñöôïc xaùc ñònh laø N do ngöôøi duøng nhaäp vaøo tröôùc khi chaïy giaûi thuaät. Soá N seõ xaùc ñònh ñöôïc heä soá giaûm nhieät ñoä α cho lòch bieåu laøm nguoäi naøy, α ñöôïc xaùc ñònh baèng coâng thöùc sau: α = 1 - ( ln(T0) –ln(T1) ) / N. (4.2) Nhieät ñoä seõ giaûm daàn theo coâng thöùc T = α * T vaø giaûi thuaät seõ ñöôïc thöïc thi N laàn roài döøng laïi. Neáu ngöôøi söû duïng chaïy theo lòch bieåu laøm nguoäi loaïi naøy thì chöông trình coù öu ñieåm laø thôøi gian chaïy cuûa giaûi thuaät cuûa ngöôøi duøng coù theå ñieàu khieån ñöôïc. Chuùng toâi söû duïng lòch bieåu naøy vôùi muïc tieâu xaùc ñònh ñöôïc ñieåm döøng (stopping-criterion) cuûa phaàn SA hoïc hoûi vaø SA chaïy trong giaûi thuaät ISA (seõ noùi ôû phaàn 4.1.5). Thöïc nghieäm cho thaáy neáu nhö thôøi gian chaïy cuûa giaûi thuaät caøng nhieàu thì chaát löôïng cuûa baøi toaùn seõ caøng ñöôïc caûi thieän. Tuy nhieân, khi thôøi gian chaïy cuûa giaûi thuaät lôùn ñeán moät möùc naøo ñoù, chaát löôïng cuûa giaûi thuaät seõ khoâng coøn ñöôïc caûi thieän ñaùng keå, ta noùi baøi toaùn ñaõ ñaït traïng thaùi gaàn vôùi lôøi giaûi toái öu. Lòch bieåu laøm nguoäi caáp soá nhaân ñöôïc moâ taû baèng löu ñoà thuaät giaûi ôû hình 4-3. 4.1.5 Giaûi thuaät SA caûi tieán (ISA – Inform Simulated Annealing) Giaûi thuaät ISA, caûi tieán cuûa giaûi thuaät SA truyeàn thoáng, laø moät quaù trình giuùp cho kyõ thuaät tìm kieám caùc lôøi giaûi laân caän ñöôïc toát hôn. Trong giaûi thuaät ISA, quaù trình moâ phoûng luyeän kim seõ chia laøm hai phaàn: -Phaàn ñaàu thöïc hieän giaûi thuaät SA nhöng coù löu laïi xaùc suaát thaønh coâng cuûa caùc caëp bieán – giaù trò (coøn goïi laø quaù trình SA hoïc hoûi). Ngoaøi ra, ñeå quaù trình hoïc hoûi ñöôïc toát hôn, giaûi thuaät ñeà nghò giaûi quyeát cho caùc caëp bieán – giaù trò coù theå ñöôïc hoïc hoûi moät caùch coâng baèng, ñaûm baûo caùc caëp bieán – giaù trò ñeàu coù cô hoäi hoïc hoûi ngang nhau. Ñeå hieän thöïc phaàn naøy trong baøi toaùn, ngoaøi vieäc söû duïng caùc baûng ñeå tính toaùn, löu giöõ traïng thaùi, chuùng toâi söû duïng baûng Hoïc ñeå löu giöõ soá laàn ñöôïc hoïc hoûi cuûa caëp bieán –giaù trò cuõng nhö xaùc suaát thaønh coâng khi höôùng theo caëp bieán giaù trò ñoù, phuïc vuï cho quaù trình SA chaïy tieáp theo: Phaàn ñaàu (SA hoïc hoûi) ñöôïc moâ taû nhö hình 4-4: Hình 4-3: Lòch bieåu laøm nguoäi caáp soá nhaân -Phaàn sau seõ thöïc hieän giaûi thuaät SA vôùi vieäc höôùng caùch choïn lôøi giaûi laân caän theo caùc caëp bieán – giaù trò coù xaùc suaát thaønh coâng cao (goïi laø quaù trình SA chaïy). Trong phaàn naøy, chuùng toâi söû duïng moät bieán xaùc suaát P0 ñeå ñònh höôùng quaù trình choïn lôùi giaûi laân caän: choïn moät bieán vi baát kyø vaø moät giaù trò ngaãu nhieân töø 0 ñeán 1, neáu P0 lôùn hôn giaù trò ngaãu nhieân, chuùng ta seõ choïn giaù trò cho bieán theo xaùc suaát cuûa baûng Hoïc, ngöôïc laïi chuùng ta seõ choïn moät giaù trò baát kyø cho bieán ñoù. Roõ raøng, vôùi xaùc suaát P0 caøng lôùn, caùc caëp bieán giaù trò coù xaùc suaát cao seõ deã daøng ñöôïc choïn vaø lôøi giaûi laân caän, trong moät khaû naêng naøo ñoù, seõ coù hieäu quaû hôn quaù trình löïa choïn ngaãu nhieân. Phaàn sau (SA chaïy) ñöôïc moâ taû nhö hình 4-4: Hình 4-4: Giaûi thuaät ISA – phaàn SA hoïc hoûi Hình 4-5: Giaûi thuaät ISA – phaàn SA chaïy 4.2 Hieän thöïc giao dieän ngöôøi duøng Giao dieän ñaêng nhaäp ngöôøi duøng: Giao dieän naøy cho pheùp ngöôøi duøng ñaêng nhaäp vaøo heä thoáng vôùi teân ngöôøi duøng vaø maät maõ do chính ngöôøi quaûn trò heä thoáng cung caáp. Sau khi ñaêng nhaäp, ngöôøi duøng coù thöïc hieän moät soá chöùc naêng cuûa heä thoáng Hình 4-6: Form ñaêng nhaäp cho ngöôøi duøng. Giao dieän ñaêng kyù sinh vieân vaøo kyù tuùc xaù: Giao dieän naøy cho pheùp nhaân vieân kyù tuùc xaù nhaäp vaøo thoâng tin caù nhaân veà sinh vieân khi ñaêng kyù xeáp phoøng, bao goàm döõ lieäu caù nhaân cuûa sinh vieân, tieâu chí choïn phoøng, tieâu chí choïn baïn cuõng nhö sôû thích cuûa sinh vieân ñoù. Hình 4-7: Form ñaêng kyù vaøo ôû kyù tuùc xaù cho sinh vieân. Giao dieän duøng ñeå quaûn lyù chi phí cho caùc raøng buoäc: Giao dieän naøy ñöôïc duøng ñeå chænh söûa chi phí cho caùc raøng buoäc phoøng – sinh vieân, möùc ñoä öu tieân daønh cho caùc raøng buoäc naøy coù theå thay ñoåi tuyø theo nhöõng moâi tröôøng khaùc nhau. Hình 4-8: Form cho pheùp chænh söûa laïi chi phí phoøng – sinh vieân Giao dieän duøng ñeå quaûn lyù caùc thoâng soá cuûa giaûi thuaät ISA: Giao dieän naøy ñöôïc duøng ñeå chænh söûa caùc chi phí cho caùc raøng buoäc sinh vieân – sinh vieân, möùc ñoä öu tieân daønh cho caùc raøng buoäc naøy coù theå thay ñoåi tuyø theo nhöõng moâi tröôøng khaùc nhau. Hình 4-9: Form cho pheùp thay ñoåi caùc thoâng soá cuûa giaûi thuaät ISA Keát quaû xeáp phoøng cho sinh vieân: Hình veõ 4-11 moâ taû moät phaàn keát quaû xeáp phoøng cuûa sinh vieân, baùo caùo keát quaû xeáp phoøng bao goàm maõ soá sinh vieân, hoï vaø teân sinh vieân, ngaøy sinh, nôi sinh, giôùi tính, maõ phoøng, maõ giöôøng. Baùo caùo xeáp phoøng ñöôïc hieän thöïc baèng Crystal Report neân coù theå deã daøng ñöôïc in ra hoaëc laø chuyeån sang caùc daïng file khaùc nhö pdf, doc, excel, html… deã daøng cho vieäc quaûn lyù vaø baûo quaûn vaø ñöa thoâng tin leân maïng internet.. Hình 4-10: Keát quaû xeáp phoøng cho sinh vieân 4.3 Keát quaû thöïc nghieäm Chuùng toâi ñaõ hieän thöïc heä thoáng xeáp phoøng cho sinh vieân ôû kyù tuùc xaù Ñaïi hoïc Baùch Khoa TPHCM baèng kyõ thuaät moâ phoûng luyeän kim caûi tieán ISA söû duïng ngoân ngöõ Visual C# trong coâng cuï Microsoft Visual Studio.NET 2003, maùy tính ñöôïc söû duïng ñeå chaïy thöû chöông trình laø maùy coù CPU Pentium IV 2,6 Ghz, 512 MB RAM. Taäp döõ lieäu duøng ñeå thöû goàm 3,000 sinh vieân, trong ñoù moãi sinh vieân coù 3 raøng buoäc cöùng vaø 19 raøng buoäc meàm phaûi thoaõ maõn, nhö vaäy toång coäng heä thoáng coù 9,000 raøng buoäc cöùng baét buoäc phaûi thoaõ maõn vaø 57,000 raøng buoäc meàm ñöôïc duøng ñeå xeùt ñeán ñoä toái öu cuûa keát quaû baøi toaùn.. Sau nhieàu thöïc nghieäm vôùi caùc tham soá khaùc nhau, chuùng toâi nhaän thaáy heä thoáng cho lôøi giaûi coù chaát löôïng toát vôùi caùc thoâng soá ñieàu khieån coù giaù trò nhö T=10,000, T0=0.0001, nrep=6. Trong ñoù T laø nhieät ñoä ban ñaàu, T0 laø nhieät ñoä keát thuùc, nrep laø soá laàn laëp laïi cuûa vieäc xeáp phoøng ôû moãi nhieät ñoä. Thôøi gian töông öùng vôùi soá böôùc chaïy cuûa giaûi thuaät N theo thöïc nghieäm cho keát quaû nhö sau: Baûng 4-1: Thôøi gian thöïc thi giaûi thuaät ISA vôùi soá böôùc chaïy cho tröôùc N (soá böôùc chaïy) 500 1,000 5,000 10,000 20,000 Thôøi gian chaïy (giôø:phuùt:giaây) 0:04:59 0:11:40 0:56:27 2:01:34 4:27:59 Hình 4-11 theå hieän söï thay ñoåi cuûa chi phí cuûa baøi toaùn xeáp phoøng vôùi soá böôùc chaïy töø 0 – 20,000, vôùi caùc tham soá T=10,000, T0=0.0001, nrep=6. Hình 4-12 theå hieän söï thay ñoåi cuûa chi phí cuûa baøi toaùn xeáp phoøng vôùi soá böôùc chaïy töø 0 – 10,000, vôùi caùc tham soá T=10,000, T0=0.0001, nrep=6 do taùc giaû Leâ Trung Hieáu thöïc hieän theo giaûi thuaät SA truyeàn thoáng vôùi lòch bieåu laøm nguoäi caáp soá nhaân coù soá laàn thöïc thi xaùc ñònh tröôùc.. Hình 4-11: Keát quaû thöïc nghieäm thu ñuôïc duøng giaûi thuaät ISA Hình 4-12: Keát quaû thöïc nghieäm theo luaän vaên taùc giaû Leâ Trung Hieáu Töø keát quaû qua hai bieåu ñoà ta nhaän thaáy raèng khi soá böôùc chaïy caøng lôùn thì chi phí cuûa baøi toaùn caøng giaûm, tuy nhieân möùc ñoä giaûm cuûa chi phí veà sau caøng ít ñi. Tuøy theo muïc tieâu vaø thôøi gian maø ngöôøi duøng coù theå choïn cho mình soá böôùc chaïy phuø hôïp ñeå coù ñöôïc keát quaû öng yù. Keát quaû naøy cho thaáy roõ söï öu vieät khi aùp duïng giaûi thuaät ISA coù ñònh höôùng thoâng qua quaù trình hoïc hoûi vaøo baøi toaùn naøy. Nhôø quaù trình hoïc hoûi maø quaù trình saép xeáp nhaèm taïo ra lôøi giaûi toái öu ñaït ñeán nhöõng lôøi giaûi toát hôn haún khi so vôùi lôøi giaûi thu ñöôïc khi aùp duïng giaûi thuaät SA chaân phöông nhö trong tröôøng hôïp cuûa taùc giaû Leâ Trung Hieáu CHÖÔNG 5 TOÅNG KEÁT VAØ ÑAÙNH GIAÙ 5.1 Toång keát Tröôùc khi thieát keá vaø hieän thöïc phaàn giaûi thuaät chính cuûa luaän vaên, chuùng toâi ñaõ trình baøy cô sôû lyù thuyeát veà giaûi thuaät tìm kieám cuïc boä ñeå aùp duïng vaøo luaän vaên. Ngoaøi ra, chuùng toâi cuõng ñaõ trình baøy sô löôïc caùc giaûi thuaät tìm kieám cuïc boä khaùc nhau nhö giaûi thuaät leo ñoài Hill-climbing, giaûi thuaät tìm kieám Tabu, giaûi thuaät moâ phoûng luyeän kim SA. Beân caïnh ñoù, vieäc phaân tích so saùnh öu vaø khuyeát ñieåm cuûa caùc giaûi thuaät naøy cuõng ñaõ ñöôïc ñöa ra. Ñoâàng thôøi, chuùng toâi cuõng ñöa ra ñöôïc lyù giaûi nguyeân nhaân choïn giaûi thuaät moâ phoûng luyeän kim vaø caûi tieán noù vaøo baøi toaùn xeáp phoøng cho sinh vieân taïi kyù tuùc xaù.. Qua noäi dung cuûa ñeà taøi, chuùng toâi cuõng ñaõ tìm hieåu nghieäp vuï quaûn lyù vaø xeáp phoøng kyù tuùc xaù treân thöïc teá vaø trình baøy nhöõng yeâu caàu cô baûn nhaát cuûa baøi toaùn xeáp phoøng cho sinh vieân ôû kyù tuùc xaù Ñaïi hoïc Baùch Khoa TPHCM. Quaù trình tìm hieåu caùc chính saùch quy ñònh cuûa kyù tuùc xaù veà cô cheá xeáp phoøng ñaõ giuùp chuùng toâi coù cô sôû phaân tích vaø thieát keá giaûi thuaät xeáp phoøng mang tính thöïc tieãn vaø khaû thi cao. Tuy nhieân, chöông trình ñöôïc thieát keá mang tính môû vaø ngöôøi söû duïng heä thoáng coù theå thay ñoåi, theâm bôùt caùc yeâu caàu moät khi chính saùch quaûn lyù coù ít nhieàu thay ñoåi. Beân caïnh ñoù, luaän vaên ñaõ xaây döïng ñöôïc moät taäp raøng buoäc cöùng maø heä thoáng baét buoäc phaûi thoaõ maõn khi thöïc hieän giaûi thuaät do taøi nguyeân höõu haïn vaø caùc ñieàu kieän raøng buoäc treân thöïc teá. Ñoàng thôøi, chuùng toâi ñaõ xaây döïng moät taäp caùc raøng buoäc meàm döïa treân nhu caàu thöïc teá theå hieän caùc tieâu chí löïa choïn phoøng cuûa sinh vieân khi ñaêng kyù vaøo ôû kyù tuùc xaù. Ngoaøi ra, luaän vaên cuõng ñaõ nghieân cöùu ñeå ñöa ra ñöôïc haøm muïc tieâu phuø hôïp cho giaûi thuaät xeáp phoøng ñeå toái öu hoùa lôøi giaûi baèng caùch aùp duïng kyõ thuaät moâ phoûng quaù trình luyeän kim caûi tieán ISA. Ñeå chöông trình coù theå aùp duïng treân thöïc teá quaûn lyù kyù tuùc xaù vaø tieän duïng cho ngöôøi duøng vôùi caùc muïc ñích khaùc nhau, luaän vaên cuõng xaây döïng neân moät heä thoáng quaûn lyù vaø xeáp phoøng ôû kyù tuùc xaù goàm nhieàu khoái chöùc naêng khaùc nhau nhö khoái chöùc naêng quaûn lyù sinh vieân, khoái chöùc naêng quaûn lyù kyù tuùc xaù, khoái chöùc xeáp phoøng cho sinh vieân, khoái chöùc naêng quaûn lyù ngöôøi duøng. Phaàn coát loõi veà maët giaûi thuaät, luaän vaên ñaõ hieän thöïc thaønh coâng heä thoáng xeáp phoøng cho sinh vieân taïi kyù tuùc xaù öùng duïng giaûi thuaät moâ phoûng luyeän kim caûi tieán ISA vôùi lòch bieåu laøm nguoäi caáp soá nhaân. Cuoái cuøng, heä thoáng cuõng ñaõ ñöôïc chaïy thöû nghieäm treân taäp döõ lieäu lôùn laø 3,000 sinh vieân vôùi gaàn 60,000 raøng buoäc khaùc nhau, thôøi gian chaïy ñeå cho keát quaû laø hôn 2 giôø vôùi soá laàn böôùc chaïy cuûa giaûi thuaät SA laø 10,000. Ñaây laø moät keát quaû khaù toát neáu so vôùi khoaûng thôøi gian hôn 4 giôø maø taùc giaû Leâ Trung Hieáu ([9]) ñaõ ñöa ra khi aùp duïng giaûi thuaät SA truyeàn thoáng vôùi lòch bieåu laøm nguoäi caáp soá nhaân. Caùc lôøi giaûi cuûa baøi toaùn coù chaát löôïng toát. 5.2 Ñaùnh giaù Nhìn chung, luaän vaên ñaõ xaây döïng thaønh coâng heä thoáng xeáp phoøng cho sinh vieân ôû kyù tuùc xaù döïa treân nhu caàu thöïc teá cuûa sinh vieân vaø thöïc traïng qui trình quaûn lyù kyù tuùc xaù hieän taïi, ñaëc bieät laø ñöa ra giaûi phaùp toái öu hoùa caùch xeáp phoøng baèng caùch aùp duïng kyõ thuaät moâ phoûng luyeän kim caûi tieán ISA. Trong quaù trình xaây döïng vaø hieän thöïc heä thoáng, luaän vaên coù caùc öu ñieåm vaø haïn cheá nhö sau: 5.2.1 Öu ñieåm Ñaây laø chöông trình quaûn lyù vieäc xeáp phoøng cho sinh vieân ôû kyù tuùc xaù coù tính thöïc tieãn cao vaø caùc raøng buoäc cuûa baøi toaùn ñöôïc xaây döïng treân cô sôû phaân tích nhu caàu trong thöïc teá cuûa sinh vieân vaø cuûa vieäc quaûn lyù ôû kyù tuùc xaù, do ñoù tính khaû thi cuûa chöông trình raát cao. Luaän vaên cuõng ñaõ chia heä thoáng thaønh caùc khoái chöùc naêng cô baûn phuïc vuï cho caùc muïc ñích khaùc nhau giuùp cho vieäc quaûn lyù sinh vieân cuõng nhö quaûn lyù vieäc xeáp phoøng deã daøng, thuaän tieän cho ngöôøi duøng. Veà maët giaûi thuaät, luaän vaên ñaõ xaây döïng thaønh coâng heä thoáng xeáp phoøng cho sinh vieân ôû kyù tuùc xaù baèng kyõ thuaät moâ phoûng luyeän kim caûi tieán ISA vôùi thôøi gian chaïy ñöôïc ngöôøi söû duïng xaùc ñònh tröôùc. Ñieàu naøy laøm taêng söï tieän duïng cho ngöôøi duøng khi vaän haønh chöông trình, neáu ngöôøi söû duïng coù nhieàu thôøi gian thì ngöôøi duøng coù theå cho soá böôùc chaïy cuûa giaûi thuaät lôùn ñeå ñöa ra lôøi giaûi coù chaát löôïng cao. Thôøi gian chaïy heä thoáng cuõng giaûm xuoáng ñaùng keå coøn khoaûng 2 giôø chaïy cho taäp döõ lieäu thaät, giaûm raát nhieàu laàn so vôùi giaûi thuaät saép xeáp theo kieåu truyeàn thoáng maø thu ñöôïc keát quaû chaáp nhaän ñöôïc. Chuùng toâi cuõng ñaõ aùp duïng kyõ thuaät chia nhoû baøi toaùn ra töøng phaàn khi hieän thöïc chöông trình ñeå taêng toác ñoä thöïc thi cuûa giaûi thuaät. Ñaây laø moät maët thaønh coâng cuûa luaän vaên veà ñoä hieäu quaû cuûa vieäc xaây döïng giaûi thuaät. Vieäc chia nhoû baøi toaùn ra thaønh hai baøi toaùn nhoû hôn nhö chuùng toâi ñaõ trình baøy ôû treân vaø vieäc caøi ñaët moät phaàn giaûi thuaät duøng stored procedure laø hai ñieàu chuùng toâi caûm thaáy taâm ñaéc nhaát vì ñaáy chính laø nhöõng yeáu toá taïo neân söï thaønh coâng cuûa vieäc aùp duïng giaûi thuaät naøy cho baøi toaùn xeáp phoøng cho sinh vieân ôû kyù tuùc xaù cuûa chuùng toâi. Keát quaû cuûa chuùng toâi ñaït ñöôïc so vôùi keát quaû thu ñöôïc khi aùp duïng giaûi thuaät SA thuaàn tuùy vaøo chính baøi toaùn naøy cuûa taùc giaû Leâ Trung Hieáu laø moät böôùc tieán boä ñaùng keå veà caû thôøi gian chaïy cuõng nhö veà möùc ñoä toái öu cuûa lôøi giaûi. 5.2.2 Haïn cheá Tieâu chí ñaùnh giaù caùc sôû thích cuûa sinh vieân taïi kyù tuùc xaù do chuùng toâi ñöa ra coù phaàn chuû quan döïa treân moät soá thoâng tin do ban quaûn lyù kyù tuùc xaù cung caáp. Tuy nhieân, neáu coù ñaày ñuû thôøi gian thì chuùng toâi seõ phaûi laøm moät cuoäc ñieàu tra laáy yù kieán caùc sinh vieân vôùi quy moâ lôùn ñeå coù theå naém baét nhu caàu thaät söï cuûa sinh vieân nhaèm ñaùnh giaù chính xaùc möùc ñoä öu tieân töøng raøng buoäc. Thôøi gian chaïy giaûi thuaät khoaûng 2 giôø treân taäp döõ lieäu thaät cho duø coù nhieàu caûi tieán so vôùi keát quaû cuûa taùc giaû Leâ Trung Hieáu laø 4 giôø, nhöng heä thoáng nhìn chung cho keát quaû vaãn chaäm. Neáu coù nhieàu thôøi gian ñaàu tö hôn nöõa vaø ñieàu kieän haï taàng maùy moùc toát thì coù theå ruùt ngaén thôøi gian chaïy giaûi thuaät xuoáng nhieàu laàn. Ngoaøi ra, coù theå vaän duïng moät soá heuristic caûi tieán ñeå giuùp chöông trình chaïy trong moät khaû naêng toát hôn. 5.3 Höôùng phaùt trieån cuûa luaän vaên Veà maët chöùc naêng, luaän vaên coøn coù theå phaùt trieån khoái chöùc naêng cho pheùp sinh vieân coù theå noäp hoà sô ñaêng kyù vaøo ôû kyù tuùc xaù tröïc tuyeán vaø xem keát quaû xeáp phoøng tröïc tuyeán ñeå taêng theâm söï tieän lôïi cho sinh vieân veà dòch vuï hoã trôï sinh vieân. Tuy nhieân, vaán ñeà naøy coøn nhieàu tính baøn caõi do caùc dieän öu tieân cuûa sinh vieân caàn phaûi ñöôïc kieåm tra tröôùc cuõng nhö traùnh sinh vieân nhaäp döõ lieäu aûo. Ñeå giaûi quyeát, coù theå lieân keát vôùi phoøng ñaøo taïo cuûa tröôøng ñeå kieåm tra döõ lieäu nhaäp cuûa sinh vieân. Veà maët giaûi thuaät, luaän vaên coù theå ñöôïc môû roäng baèng caùch hieän thöïc treân nhieàu lòch bieåu laøm nguoäi khaùc nhau nhö lòch bieåu laøm nguoäi vôùi nhieàu heä soá giaûm nhieät ñoä, lòch bieåu laøm nguoäi taùi nung noùng caáp soá nhaân caûi tieán… vaø so saùnh caùc keát quaû töø nhöõng caùch chaïy khaùc nhau naøy ñeå coù theå coù ñöôïc lòch bieåu laøm nguoäi toái öu hôn thoâng qua quaù trình thöïc nghieäm. Ngoaøi ra, luaän vaên coù theå môû roäng ñeå coù theå theâm caùc raøng buoäc veà sôû thích moät caùch hieäu quaû hôn. Ngoaøi ra, coù theå vaän duïng moät soá heuristic caûi tieán ñeå giuùp chöông trình chaïy trong moät khaû naêng toát hôn. Ñeå taêng ñoä hieäu quaû cuûa chöông trình vaø giaûi thuaät, luaän vaên coøn coù theå ñöôïc môû roäng baèng caùch xaây döïng giaûi thuaät song song hoaëc phaân taùn ñeå hieän thöïc baøi toaùn xeáp phoøng cho sinh vieân ôû kyù tuùc xaù treân nhieàu boä vi xöû lyù hoaëc nhieàu maùy tính khaùc nhau, giaûi thuaät naøy ñöôïc ñeà caäp trong phaàn taøi lieäu tham khaûo [8]. Giaûi thuaät song song hoaëc phaân taùn giuùp cho thôøi gian chaïy baøi toaùn giaûm xuoáng raát nhieàu. Ñeå coù theå ruùt ngaén thôøi gian chaïy cuûa giaûi thuaät, baøi toaùn xeáp phoøng coù theå ñöôïc xaây döïng baèng giaûi thuaät tìm kieám Tabu, vì baûn chaát cuûa giaûi thuaät tìm kieám tabu laø khoâng choïn lôøi giaûi ngaãu nhieân neân soá laàn laëp laïi cuûa giaûi thuaät seõ ít ñi vaø thôøi gian chaïy giaûi thuaät seõ ñöôïc ruùt ngaén laïi. Tuy nhieân, neáu choïn giaûi thuaät tìm kieám Tabu thì chuùng ta phaûi toán chi phí veà boä nhôù ñeå löu laïi caùc lôøi giaûi ñaõ tìm ñöôïc. Neáu coù ñieàu kieän, thì baøi toaùn coù theå seõ ñöôïc hieän thöïc baèng giaûi thuaät tìm kieám Tabu ñeå coù theå so saùnh keát quaû xeáp phoøng cho sinh vieân ôû kyù tuùc xaù. TAØI LIEÄU THAM KHAÛO [1] M.A. Saleh Elmohamed, Geoffrey Fox, Paul Coddington, “A Comparison of Annealing Techniques for Academic Course Scheduling”, Northeast Parallel Architectures Center, Syracuse University, Syracuse NY, U.S.A., 1998. [2] Abramson, D., Krishnamoorthy, M., Dang, H., “Simulated Annealing Cooling Schedules for School Timetabling Problems”, 1997. [3] Fernando Melicio, Pailo Caldeira, Agostinho Rosa, “Implementation aspects of Simulated Annealing on Timetabling”, LaSEEB-ISR, 1998. [4] Eric Poupaert, Y ves Deville, “Simulated Annealing with estimated temperature”, Department of Computing Science and Engineering, Universite’ Catholique de Louvain, Louvain-la-Neuve, Belgium, 2000. [6] Elema Settanni, “Improving Dorm Room Assignments Using Simulated Annealing”, Master thesis of Computer Science, The Universisty of New Mexico, 2000. [7] Lam Kim Hoa, Duong Tuan Anh, ”Combining Constraint Programming and Simulated Annealing on University Exam Timetabling”, Proceedings of RIVF ’04, Ha Noi, Feb 2004. [8] Abramson D.A., “A Very High Speed Architecture to Support Simulated Annealing”, IEEE Computer, 1992. [9] Leâ Trung Hieáu , “ÖÙng duïng kyõ thuaät moâ phoûng luyeän kim cho baøi toaùn xeáp phoøng sinh vieân taïi kyù tuùc xaù”, Luaän vaên thaïc só, Ñaïi hoïc Baùch Khoa Tp. HCM, 2005. [10] Yinghao Li, “Directed Simulated Annealing In Constraints Satisfaction And Optimisation” , PhD thesis, Imperial College of Science, Technology and Medicine, University of London, October 1997. PHUÏ LUÏC