課程表編排問題

課程表編排問題在學校的教務管理工作中，課程表的編排是一項十分復雜、棘手的工作。排課需要考慮時間、課程、教學區(qū)域、教室、院系、班級、教師等等因素。經(jīng)優(yōu)化的排課，可以在任意一段時間內(nèi)，教師不沖突，授課不沖突，授課的班級不沖突，教室占用不沖突，且綜合衡量全校課表在宏觀上是合理的。如何利用有限的師資力量和有限教學資源，排出一個合理的課程安排結果，對穩(wěn)定教學秩序、提高教學質(zhì)量有著積極的意義。某高?，F(xiàn)有課程40門，編號為C01?C40.每門課程都是32學時；教師共有25名，編號為T01?T25；教室18間，編號為R01?R18。具體屬性及要求見表1，表2，表3。課表編排規(guī)則：一學期有20周，每周以5天（周一到周五）為單位進行編排，每天最多只能編排8節(jié)課（上午4節(jié)，下午4節(jié)），特殊情況下可以編排10節(jié)課（晚上2節(jié)），每門課程以2節(jié)課為單位進行編排，同類課程盡可能不安排在同一時間。你所要解決的問題：請你結合實際情況建立數(shù)學模型，通過計算，給出較為合理的課表編排方案，分析你所給出的方案的合理性。如果不準晚上排課，排課結果是否有所變化，如何變化？對教師聘用，教室配置給出合理化建議。表1課程編號課程類別周課時數(shù)對教室座位要求數(shù)對教室類別要求時間要求C011450多媒體教室上午C021430普通教室下午C031640普通教室下午C041225多媒體教室上午C051460普通教室下午C0624100普通教室下午C072450多媒體教室上午C082230普通教室上午C092440普通教室下午C102425多媒體教室上午C113660普通教室上午C123480普通教室上午C133250多媒體教室下午

C143230普通教室下午C153440普通教室下午C164425多媒體教室上午C174460普通教室下午C184690普通教室上午C194450多媒體教室上午C204250普通教室上午C215430普通教室上午C225440多媒體教室下午C235425普通教室上午C245660普通教室下午C2552100多媒體教室上午C266450多媒體教室下午C276230普通教室下午C286440普通教室下午C296450多媒體教室上午C306430普通教室下午C317640普通教室上午C327425多媒體教室下午C337460普通教室無C347280多媒體教室上午C357250普通教室下午C368630機房無C378440機房上午C388225機房上午C398460機房下午C408450機房無表2教師編號能勝任課程類別周最大課時數(shù)對教室類別要求上課時間要求開課周次盡可能不同天上課的教師T011，810多媒體教室或機房上午第10周T04T02110普通教室下午第4周T03112普通教室上午第1周T04210多媒體教室上午第10周T01T05210普通教室下午第4周T06212普通教室無第1周T07310普通教室上午第10周T083，810普通教室或機下午第1周

房T09310普通教室上午第4周T11,T18T10312多媒體教室上午第1周T11416普通教室下午第1周T09,T12410普通教室無第4周T13412多媒體教室下午第1周T14510普通教室上午第1周T155,810普通教室或機房下午第1周T23T1658普通教室上午第10周T17610普通教室下午第4周T18612普通教室無第1周T9T1968多媒體教室下午第1周T2078普通教室上午第10周T21712普通教室下午第1周T22712多媒體教室上午第1周T233,810普通教室或機房無第10周T15T244,812普通教室或機房上午第1周T256,810普通教室或機房下午第4周表3教室編號最大座位數(shù)教室類別R01100多媒體教室R02100普通教室R03100普通教室R0450多媒體教室R0550普通教室R0650普通教室R0750普通教室R0860普通教室R0960普通教室R1060多媒體教室R1160普通教室R1260機房R1340機房R1440機房R1540機房R1640多媒體教室R1750普通教室R1840普通教室[1]假設學校的優(yōu)先考慮目標是完成所有課程的編排；⑵假設所編排的課程表是學生自選型，即課程的編排不會受到班級以及班級人數(shù)的限制，只與課程的人數(shù)要求有關；表1課程要求中的各項均為強制要求，即“硬約束”；表2教師屬性中，能勝任課程類別、周最大課時數(shù)為強制要求，即“硬約束”;對教室類別要求、上課時間要求等用偏好程度衡量，為“軟約束”；假設課表只受上課時間、教師、教室、課程的影響，其他因素（教室故障問題等）不會影響課程的進行；一門課程