高校大規(guī)?？荚嚨陌才艑?zhuān)項(xiàng)方案優(yōu)化

摘要增多，學(xué)校在安排期終考試等大型考試時(shí)總會(huì)遇到各種難題，如，4、使每個(gè)監(jiān)考教師監(jiān)考日程比較平均，且保證不發(fā)生某一時(shí)段監(jiān)考教師本文采用圖論中逆著色算法解決問(wèn)題1，并設(shè)計(jì)程序依照已知各種教室規(guī)模意最優(yōu)者。安排逆著色算法滿意度ii一.問(wèn)題重述考意。。二.基本假設(shè)1.選同一門(mén)課程所有學(xué)生一起參加該課程考試，不考慮上學(xué)時(shí)邏輯班級(jí)。2.一種學(xué)校學(xué)生選課狀況足夠交錯(cuò)復(fù)雜以致能排在同一時(shí)間考試科目不會(huì)過(guò)4.每天至多可以安排五個(gè)時(shí)間段考試。5.學(xué)生選課狀況已知。三.符號(hào)闡明：監(jiān)考教師數(shù)量Sj：第j個(gè)考試時(shí)間段四.問(wèn)題分析及模型建立(一)問(wèn)題分析進(jìn)一步調(diào)節(jié)各場(chǎng)考試，滿足題目別的規(guī)定。所有考試。這是基于假設(shè)2“一種學(xué)校學(xué)生選課狀況足夠交錯(cuò)復(fù)雜以致能排在同大教師充分理解：教室分派合理理解：考?對(duì)方案使學(xué)生滿意定義：2、學(xué)生普通是但愿能盡快結(jié)束考試。為了做到這一點(diǎn)，咱們?cè)跊Q定考試日程方案時(shí)總是考慮把考生更多時(shí)間段放在前面。?對(duì)方案使教師滿意定義：1、對(duì)于每個(gè)教師，監(jiān)考場(chǎng)次需大體相似；2、由于教師需要休息，對(duì)于每個(gè)教師，盡量不浮現(xiàn)持續(xù)監(jiān)考狀況，監(jiān)考安排也需盡量均勻。?對(duì)方案使學(xué)校滿意定義：2、設(shè)計(jì)安排方案應(yīng)當(dāng)簡(jiǎn)便易行，不致過(guò)于繁復(fù)，難以實(shí)現(xiàn)。綜合考慮，最后對(duì)于監(jiān)考方案擬定分四個(gè)過(guò)程：將所有參加考試科目分在不同步間段，保證每個(gè)學(xué)生不會(huì)遇到在同一時(shí)間段監(jiān)考她所專(zhuān)家科目，并滿足使教師(二)模型設(shè)計(jì)n咱們將看到這與下面問(wèn)題是等價(jià)。下面(1)~(3)引自參照資料[1]。(1)圖節(jié)點(diǎn)著色問(wèn)題①圖節(jié)點(diǎn)著色問(wèn)題定義[互補(bǔ)圖]：圖G(V，E1)，E為邊全集(任意兩個(gè)屬于V節(jié)點(diǎn)之間均有相應(yīng)邊[圖逆著色]：圖G一種逆著色是指k種顏色1，2，...，k對(duì)于G節(jié)點(diǎn)一個(gè)分派，使得一種顏色任意兩個(gè)節(jié)點(diǎn)都相鄰。而G逆色數(shù)(G)是指G逆著色數(shù)k最小(2)問(wèn)題1轉(zhuǎn)化為圖節(jié)點(diǎn)著色問(wèn)題Cn}，每一條邊CiCj(CiCj∈E)兩個(gè)端點(diǎn)Ci和Cj表達(dá)某一位同窗兩門(mén)考試課程。G顯然圖H是上述圖G互補(bǔ)圖，依照定理，對(duì)求解圖G色數(shù)和求解圖H逆色(3)逆著色問(wèn)題解決算法①遍歷圖，找出度數(shù)不不大于零且度數(shù)最小節(jié)點(diǎn)X。。X。④找出和節(jié)點(diǎn)X相鄰度數(shù)最小節(jié)點(diǎn)Y。⑤合并節(jié)點(diǎn)X和Y。但該算法較為簡(jiǎn)潔有效。算法有效性見(jiàn)第五某些模型檢查。(4)針對(duì)其她規(guī)定及程序?qū)崿F(xiàn)某些問(wèn)題闡明Y1X與Y一起構(gòu)成一種更高階完全圖，從而可以合并為一種新節(jié)點(diǎn)。這時(shí)該算法③實(shí)現(xiàn)算法程序中，咱們用零一矩陣(對(duì)稱陣)表達(dá)圖。有邊連接兩點(diǎn)在④在輸入一組學(xué)生選課表(涉及總課程數(shù)和每個(gè)學(xué)生選取課程表列)時(shí)，由于教室安排時(shí)遵循原則是使每門(mén)考試占用教室數(shù)目盡量少，因此，第i門(mén)課程考試需要教室數(shù)量可以由第i門(mén)課程選修學(xué)生數(shù)除以大型教室可容納考生人「x]ni=||每個(gè)教室安排兩名監(jiān)考教師，則同一時(shí)間每個(gè)教室安排兩名監(jiān)考教師，則同一時(shí)間j考試科目(假設(shè)為j1it(1),C,jm) i=j其中Nt為監(jiān)考教師總?cè)藬?shù)。對(duì)每一組考試，用不等式(2)進(jìn)行檢查，若不滿足，則將其拆分為總參加這樣，考試所有進(jìn)行完所需時(shí)間段數(shù)目Ns也就擬定了。2.為各門(mén)考試安排教室最優(yōu)3.分派各門(mén)考試時(shí)間「N](3)D=|5s(3),,S,,將各個(gè)時(shí)間段考試組1Ns分派到D天當(dāng)中去。循原則有：然后按(1)、先考大面積課程，再考別的課程這是題目原文中提出一種安排方案，即在前幾天中集中考完所有大面積課量時(shí)間段,即將所有時(shí)間段1,S,(3)、大小容量時(shí)間段交替安排,,S,,即將所有時(shí)間段1Ns按其包括考生總數(shù)由多到少排序成ii,,,,.,,,,...iiiiNs2Ns1(4)、先考大面積課程，再考別的課程，橫向分派1192345本分派方案即先將大面積課程按容量自多至少進(jìn)行橫向分派，然后將別的時(shí)(5)、先考大容量課程，再考小容量課程，橫向分派,S,即，將即將所有時(shí)間段1,S,Ns按其包括考生總數(shù)由多到少排序后進(jìn)行橫4.為各個(gè)教師分派監(jiān)考場(chǎng)次下：②、對(duì)每一種教師T，考察她所專(zhuān)家課程與否尚有考場(chǎng)需要監(jiān)考。如果有，ii+1個(gè)教師監(jiān)考場(chǎng)次接近(教師滿意.1)五.模型求解及模型檢查(一)模型使用案例獲得運(yùn)營(yíng)程序，所得案例如下所示(某些)：程序生成學(xué)生選課狀況(某些)310291112132652903102911121413210177修課，每個(gè)學(xué)院各不相似。(二)考試分段及教室分派后成果天時(shí)一致?？荚嚂r(shí)間段組合及教室分派(某些) 1314large：3middle：0small：1713large：3middle：0small：0313large：2middle：0small：1213large：2middle：0small：1(注：第28和第29時(shí)間段某些考試。每行依次為：課程編號(hào)、總需教室數(shù)、大、中、小教序沒(méi)故意義。表格內(nèi)所列各數(shù)字表達(dá)安排在這一時(shí)間段內(nèi)進(jìn)行考試所有科目編123456789234503729987654321(三)考試安排各方案實(shí)現(xiàn)(1)、先考大面積課程，再考別的課程(2)、先考大容量時(shí)間段，再考小容量時(shí)間段(3)、大小容量時(shí)間段交替安排(4)、先考大面積課程，再考別的課程，橫向分派(5)、先考大容量課程，再考小容量課程，橫向分派(四)監(jiān)考教師安排了XX若一門(mén)院系課程總學(xué)生數(shù)是Y，則該科教師參加監(jiān)考人數(shù)是。師分派監(jiān)考場(chǎng)次。運(yùn)營(yíng)程序得到教師監(jiān)考安排如下所示(某些)：……3131955555顯示)(五)最后安排方案擬定安高。(II)2iU=i=1p(S)=1=n1sU(II)2ii=1依照咱們樣本進(jìn)行計(jì)算發(fā)現(xiàn)這個(gè)p(s)值太小(102量級(jí))，因而采用作sU為滿意度計(jì)算成果。咱們用所有學(xué)生滿意度均值ss作為評(píng)價(jià)每種方案優(yōu)劣指標(biāo)之一。t教教師滿意度Pt學(xué)生滿意度Ps00.60.50.40.3學(xué)生滿意度0.20.10schedule1schedule2schedule3schedule4schedule5教師滿意度可以看出不同安排方案導(dǎo)致了滿意度明顯差別。綜合看來(lái)，方案5(先考大容量課程，再考小容量課程，橫向分派)是使學(xué)生和教師最滿意安排方案：學(xué)生六.模型評(píng)價(jià)與改進(jìn)個(gè)擊破，使用計(jì)算機(jī)模仿驗(yàn)證了模型有效性，并通過(guò)實(shí)驗(yàn)提出了較為合理方案。將協(xié)助咱們得到更加精準(zhǔn)模型，為咱們?cè)O(shè)計(jì)選課方案提供更為可信資料。繁復(fù)參照書(shū)目莉，康艷萍，《圖節(jié)點(diǎn)著色問(wèn)題變換及算法》，甘肅科隨機(jī)生成學(xué)隨機(jī)生成學(xué)生選課樣本程序intmain(){srand((unsigned)time(NULL));col_sel(i);ongif(temp[j]!=0)stu_cour[j]=temp[j];/*公共課*/lsestu_cour[j]=0;}stu_cour[j+num_gonggong]=college_select[j];/*院必修課*/first=college_select[num_bixiu];last=college_select[college_course-1];forjnumgonggongnumbixiuj<num_gonggong+num_bixiu+if(temp[j-num_gonggong-num_bixiu]!=0)stu_cour[j]=temp[j-num_gonggong-num_bixiu];/*院選修課*/sestu_cour[j]=0;}first=foundamental+college*college_course+1;last=courses；for(j=num_gonggong+num_bixiu+num_yuanxuan；j<course_max；j){if(temp[j-(num_gonggong+num_bixiu+num_yuanxuan)]!=0)stu_cour[j]=temp[j-(num_gonggong+num_bixiu+num_yuanxuan)]；se/*公選課*/stu_cour[j]=/*公選課*/}if(stu_cour[j]!=0){course_con[stu_cour[j]]++；stucourj}fprintf(fpo,"0\n");}}}教室按容量分派程教室按容量分派程序cla*get_assigned(intstu_num){cla*head=newcla;head->capacity=head->large=head->mid=head->small=0;head->cla_num=0;cla*p=0;intcap_now=0;l_max=stu_num/l_cap+1;m_max=stu_num/m_cap+1;s_max=stu_num/s_cap+1;while(s<s_max){m-1;s++;while(m<m_max){l;while(l<l_max&&l<20){if(head->capacity!=0){if(cap_now<stu_num||cap_now>head->capacity||head->cla_num<(l+m+s))continue;if(head->cla_num==(l+m+s)&&head->capacity<cap_now)continue;else{head->capacity=cap_now;head->large=l;head->mid=m;head->small=s;head->cla_num=l+m+s;}}elseif(cap_now>=stu_num){head->capacity=cap_now;head->large=l;head->mid=m;head->small=s;head->cla_num=l+m+s;}}}}returnhead;}clas*get_painted(intrelation[clas_num][clas_num]，intstudent_sum[clas_num]){clas*head=newclas;intk=0;irelation[i][j]=1-relation[i][j];head->bro=head->next=NULL;head->stu=0;head->nam=-1;head->in_degree=10000;p=newclas;p->nam=i;p->bro=NULL;p->in_degree=0;if(relation[i][j]==1)p->in_degree=p->in_degree+1;p->stu=0;p->classroom=get_assigned(student_sum[i]);p->next=head->next;head->next=p;}intl=0;while(1){q=head;p=head->next;while(p!=NULL){if(q->in_degree>p->in_degree&&p->in_degree>0)q=p;p=p->next;}if(q==head)break;r=head;p=head->next;while(p!=NULL){if(relation[q->nam][p->nam]==1&&r->in_degree>p->in_degree&&p->in_degree>0)r=p;p=p->next;}k0;a=r;while(a!=NULL){while(b!=NULL){relation[a->nam][b->nam]=relation[b->nam][a->nam]=0;b=b->bro;}a=a->bro;}wh