軟件工程課程設計-高校課表編排子系統(tǒng)

1、 28/28 題 目： 高校課表編排子系統(tǒng) 學 院 信息工程學院 專 業(yè) 計算機科學與技術 指 導 教 師 白 娟 2014年1 月 3 日摘要教學工作是高校的中心工作，而課表是高校日常教學活動運行的指揮調度表，是高校能否進行正常教學的關鍵，因此科學的，合理的課表在高校的重要性毋庸置疑。高校教務管理是一向復雜而繁重的工作，課表編排作為其中腰組成部分是長期困擾學校教務管理工作的大問題，計算機排課無疑是必然優(yōu)勢。課表編排是一個涉及多因素約束的，多目標的，結構復雜的典型的組合優(yōu)化問題，并且已經被證明為一個NP完全類，是典型的組合優(yōu)化的問題，其問題求解的時間復雜度呈指數函數增長。每個學校在排課表時考慮

2、的因素千差萬別，各種約束條件也不盡相同，但是它所涉及的主要實體卻具有相對穩(wěn)定性。關鍵字：NP完全類; 約束滿足；課表編排；課程設置；目錄TOC o 1-3 h u HYPERLINK l _Toc21161 目錄 PAGEREF _Toc21161 4 HYPERLINK l _Toc7064 第一章 需求分析說明 PAGEREF _Toc7064 5 HYPERLINK l _Toc13506 1.1編寫目的 PAGEREF _Toc13506 5 HYPERLINK l _Toc27283 1.2問題定義 PAGEREF _Toc27283 5 HYPERLINK l _Toc28065

3、1.3可行性分析 PAGEREF _Toc28065 5 HYPERLINK l _Toc15779 1.4任務描述 PAGEREF _Toc15779 5 HYPERLINK l _Toc11790 1.5目標 PAGEREF _Toc11790 5 HYPERLINK l _Toc14248 1.6運行環(huán)境 PAGEREF _Toc14248 6 HYPERLINK l _Toc21942 1.7功能需求 PAGEREF _Toc21942 6 HYPERLINK l _Toc10408 1.7.1功能描述 PAGEREF _Toc10408 6 HYPERLINK l _Toc20331

4、 1.7.2排課約束 PAGEREF _Toc20331 6 HYPERLINK l _Toc18312 1.7.3操作規(guī)程 PAGEREF _Toc18312 7 HYPERLINK l _Toc30835 第二章 概要設計說明 PAGEREF _Toc30835 8 HYPERLINK l _Toc16029 2.1數據描述與數據庫設計 PAGEREF _Toc16029 8 HYPERLINK l _Toc13133 2.2數據表 PAGEREF _Toc13133 8 HYPERLINK l _Toc18917 2.2.1E-R圖 PAGEREF _Toc18917 9 HYPERLI

5、NK l _Toc2448 2.2.2數據流圖部分 PAGEREF _Toc2448 9 HYPERLINK l _Toc23526 2.3運行需求 PAGEREF _Toc23526 10 HYPERLINK l _Toc7634 2.3.1硬件 PAGEREF _Toc7634 10 HYPERLINK l _Toc9847 2.3.2軟件 PAGEREF _Toc9847 10 HYPERLINK l _Toc30137 第三章 詳細設計說明 PAGEREF _Toc30137 11 HYPERLINK l _Toc3856 3.1模塊的具體算法 PAGEREF _Toc3856 11

6、HYPERLINK l _Toc9637 3.1.1登陸模塊 PAGEREF _Toc9637 11 HYPERLINK l _Toc4684 3.1.2管理員模塊 PAGEREF _Toc4684 11 HYPERLINK l _Toc29330 數據庫中各表的物理結構 PAGEREF _Toc29330 15 HYPERLINK l _Toc30913 第四章 編碼+測試 PAGEREF _Toc30913 17 HYPERLINK l _Toc25634 4.1登錄模塊 PAGEREF _Toc25634 17 HYPERLINK l _Toc3936 4.1.1 管理員模塊 PAGER

7、EF _Toc3936 18 HYPERLINK l _Toc20471 4.1.2教師模塊 PAGEREF _Toc20471 20 HYPERLINK l _Toc26607 4.2測試方案設計 PAGEREF _Toc26607 21 HYPERLINK l _Toc28859 測試結果分析： PAGEREF _Toc28859 22 HYPERLINK l _Toc2669 第五章 用戶使用說明書 PAGEREF _Toc2669 23 HYPERLINK l _Toc28296 第六章 實驗總結 PAGEREF _Toc28296 26 HYPERLINK l _Toc1617 第七

8、章 參考文獻 PAGEREF _Toc1617 28第一章 需求分析說明1.1編寫目的供設計人員、開發(fā)人員參考。為明確軟件需求、安排項目規(guī)劃進度、組織軟件開發(fā)與測試，撰寫本文檔。1.2問題定義隨著社會的發(fā)展，我們越來越接近自動化的時代。隨著高校學生的日益增多、學校制度的日趨完善，我們的排課也不需要人工操作了，慢慢的交給系統(tǒng)自動完成。為了給操作人員提供更簡便的操作，排課系統(tǒng)必須不斷完善以滿足需求。根據工作人員的實際需要，高校課表排課系統(tǒng)主要應包括以下幾個方面：任課教師只具有查詢個人課程信息和教室信息以及修改密碼的功能。管理員除了具有查詢功能之外，還有設定排課約束，完成排課的功能。1.3可行性分析

9、排課管理系統(tǒng)是一個教育單位不可缺少的部分,它的內容對于學校的決策者和管理者來說都至關重要,所以排課管理系統(tǒng)應該能夠為用戶提供充足的信息和快捷的查詢手段。對于一個課表編排子系統(tǒng)來說，基礎表的設置是很重要的基礎性問題。而基礎表的設置僅僅是一個數量級問題，查詢的時間復雜度是一個線性復雜度O(n)或平方復雜度O(n2)。在此基礎上，較為困難的部分是排課。由于排課問題已被證明為NP問題，找到最優(yōu)解的時間復雜度為指數級，故采用優(yōu)化的方式是必需的。對排課來說，各個學校都有著不太相同的排列方法，有每天的課節(jié)數，允許課程連排數，時間段等等，而這些方法轉換為計算機語言時，往往會因為各類限制而造成死循環(huán)或者程序速度

10、緩慢，因為排課系統(tǒng)要適應大部分學校使用，所以這里提供的一些要求是需要滿足大部分人的。經過詳細的分析與計算之后，小組成員一致認為，在一定程度的隨機化算法（退火、貪心變形算法、類貪心算法）下，排課的時間復雜度可以減小到多項式級別，達到O(n3)甚至更低。故該系統(tǒng)是可行的。1.4任務描述1.5目標隨著時代的發(fā)展，高校擴招的趨勢正在加大。與此同時，高校教務管理是一項復雜繁重的工作。課表編排是一項繁重的工程，計算機排課已經成為必然趨勢。軟件的目的是設計出一套易于使用與維護的排課子系統(tǒng)，能夠完成課程管理、課程編排、教師、學生、課程基本信息維護等功能。軟件需要較大的通用性，能夠適應多學年的排課，以及一個專業(yè)

11、多個學期的排課。同時，能夠對于各種信息進行查詢。1.6運行環(huán)境操作系統(tǒng)： Microsoft Windows 7 Ultimate / Microsoft Windows XP Professiona支持環(huán)境：.NET Framework 4.0數據庫： Microsoft SQL Server 20051.7功能需求1.7.1功能描述作為一個課表編排子系統(tǒng)，應當在完成排課任務之外，進行一部分相應的查詢與管理功能。經過小組成員分析，列出主要功能如下。機構設置： 建立系、系內部門、專業(yè)、班級等信息。課程信息：建立全校開設的課程并錄入相關信息。教師信息：建立教師的基本信息。教室信息：建立可用教室的

12、信息、類型等。包括教學樓、教室。教學任務：錄入教學任務，包括生成上課班級。課表編排：建立排課約束、預排課、自動排課、手動調整課表、沖突檢測恢復。上述功能不僅應包括新增，還應包括查詢與維護。1.7.2排課約束基本約束同一時間一個教室不能夠上兩門課。同一時間一個教師不能上兩門課。同一時間一個班級不能上兩門課。優(yōu)先順序經小組討論分析，考慮優(yōu)先順序問題，將優(yōu)先順序分類，再按照優(yōu)先順序設計算法排課。1.7.3操作規(guī)程對于新建立的數據庫，需要設定各基本信息。包括院系、職稱、職位、課程類別、教室類別等。設立基本信息后，建立教學資源信息。包括教師、教室、樓房等。建立學籍信息，包括學生、班級。建立教學計劃，決定

13、每個專業(yè)在學期間的課程。安排教學任務。根據教學計劃排定本學年學期的教學任務，包括對該學期每個專業(yè)的每一門課程指定上課班級和上課老師，生成教學任務。排課。包括預排課、自動生成上課記錄、手動調整、沖突分析檢測步驟。此步需要經過反復執(zhí)行。STD圖如下。錄入基本信息錄入教學資源錄入學籍制定教學計劃安排教學任務排課學年結束圖1-5-3 系統(tǒng)操作流程圖第二章 概要設計說明2.1數據描述與數據庫設計2.2數據表登錄表（用戶名，密碼，身份）教師信息表（工號，姓名，性別，出身年月，職稱，聯系電話）課程信息表（課程號，課程名，是否選修課，課時，學分，考試形式，是否安排，開始周次）教室信息表（教室號，容量，是否多媒

14、體）班級課程表（班級號，課程號，任務號）教師任務書（任務號，工號，課程號，所教專業(yè)，周數，人數，要求，是否多媒體）選課表（教室號，星期，時間段，任務號，占用情況）其中，加下劃線的為關鍵碼。2.2.1E-R圖N班級課程表N講課選課表11安排NN1安排教師信息表授課教師任務書N11教授教室信息表登錄11課程信息表登錄表2.2.2數據流圖部分 數據流圖說明：系統(tǒng)的流程為：管理員和教師通過登錄表進入該系統(tǒng)，管理員查詢、設置排課約束以及排課等職能，排課使選課表、課程信息表數據發(fā)生變化。根據分析，可得系統(tǒng)頂層數據流圖。將頂層數據流圖進行分解，可知教師登錄后有查詢課程安排、修改密碼的功能，這樣得出了系統(tǒng)的數

15、據流圖。D6教師任務書排課系統(tǒng)管理管理員數據流圖：D7班級課程表D2排課表登錄表D1D3課程信息表查 詢教 師教師信息表D4教室信息表D52.3運行需求2.3.1硬件 x86架構CPU512MB以上內存1.7KB硬盤空間2.3.2軟件操作系統(tǒng)：Microsoft Windows 7 Ultimate / Microsoft Windows XP Professional數據庫系統(tǒng)：Microsoft SQL Server 2005運行時環(huán)境：.NET Framework 4.0第三章 詳細設計說明3.1模塊的具體算法3.1.1登陸模塊該模塊涉及到2個登錄身份：教師，管理員教師和管理員，需要用用

16、戶名和密碼和身份進行驗證才能登錄。登錄要有自己的身份識別，是教師還是管理員，可以先判斷出用戶是以什么身份登錄的。若未選擇身份就進行查詢，則提示出錯。程序流程圖如下：YN身份為管理員 開 始YYN根據用戶名和密碼查詢記錄reader.read()N根據用戶名和密碼查詢記錄reader.read()跳轉Form2name = “管理員”跳轉Form2name = “教師”跳出提示信息3.1.2管理員模塊管理員添加排課約束條件，進行排課；其中休息日時間不能和選修課時間沖突，同時兩節(jié)選修課的時間同樣也不能發(fā)生沖突。程序流程圖如下：給所有課程分開始周數 開 始查詢教師任務書所有記錄，Fill ds i

17、= 0foreachNY要求 != 0require = 0require 接收查詢的要求YNrequire!=0YN周數=16開始周數=require入庫NY開始周數=1入庫周數=8NYi/2=0開始周數=1入庫開始周數=9入庫開始周數=1入庫 結 束選修課排課 開 始查詢未安排的選修課foreach，i = 0查詢該課程的任務號、人數、是否多媒體、任務號NYi/2=0上課時間為選修課約束的第二節(jié)上課時間為選修課約束的第一節(jié)select符合條件的教室random教室更新選課表、課程信息表 結 束其他課程排課 開 始創(chuàng)建時間鏈表h查詢課程號、人數按照人數降序排列YNcount!=0row0課程

18、的所有任務排課完成foreachNY每周課時=課時/周數每周課時=6Y每周課時=4排除矛盾分派教室并入庫的函數N排除矛盾分派教室并入庫的函數排除矛盾分派教室并入庫的函數第二節(jié)鏈表p指向”星期三”第一節(jié)”第二節(jié)鏈表p指向”星期三”第一節(jié)”排除矛盾分派教室并入庫的函數第三節(jié)鏈表p指向”星期四”第一節(jié)”排除矛盾分派教室并入庫的函數排除矛盾分派教室并入庫的函數 結 束排除矛盾的函數 開 始該工號該時段選修課表的記錄Fill dsYNcount!=0該班級該時段選修課表的記錄Fill dsYNcount!=0該時段符合條件的教室記錄 Fill dsNcount!=0Y隨機入庫下一時間段 結 束數據庫中各

19、表的物理結構（1）登錄表（2）教師信息表（3）教室信息表（4）課程信息表班級課程表教師任務書選課表第四章 編碼+測試4.1登錄模塊if (comboBox1.Text = 管理員) string sql = select 密碼 from 登錄表 where 用戶名= + name + and 身份=管理員; SqlCommand cmd = new SqlCommand(sql, conn); SqlDataReader reader = cmd.ExecuteReader(); if (reader.Read() if (reader密碼.ToString().Trim()=textBox2

20、.Text) Form2 f2 = new Form2(); f2.GetName(name, 管理員); this.Hide(); f2.Show(); else MessageBox.Show(用戶名錯誤或密碼錯誤，請核對！); else MessageBox.Show(用戶名錯誤，請核對！); if (comboBox1.Text = 教師) string sql = select 密碼 from 登錄表 where 用戶名= + name + and 身份=教師; SqlCommand cmd = new SqlCommand(sql, conn); SqlDataReader rea

21、der = cmd.ExecuteReader(); if (reader.Read() if (reader密碼.ToString().Trim() = textBox2.Text) Form2 f2 = new Form2(); f2.GetName(name, 教師); this.Hide(); f2.Show(); else MessageBox.Show(用戶名錯誤或密碼錯誤，請核對！); else MessageBox.Show(用戶名錯誤，請核對！); 管理員模塊 /排課 void MatchStartWeek() /給任務課程分前8和后8:根據周數和要求 string comm

22、String = ; SqlCommand cmd = new SqlCommand(commString, conn); / cmd.CommandText = select 課程號,周數,要求 from 教師任務書; SqlDataReader reader = cmd.ExecuteReader(); / if (reader.Read() reader.Close(); /可以不使用reader,直接ds.Tables0.Rows.Count！=0就可以了 SqlDataAdapter da = new SqlDataAdapter(cmd.CommandText, conn); Da

23、taSet ds = new DataSet(); da.Fill(ds, mytable); /for (int i = 0; i ds.Tables0.Rows.Count; i+) / int i = 0; foreach(DataRow Row in ds.Tables0.Rows) cource_num = Row課程號.ToString().Trim(); / week_num = Convert.ToInt32(Row周數.ToString().Trim(); if (Row要求.ToString().Trim() = ) require = 0; else require =

24、Convert.ToInt32(Row要求.ToString().Trim(); if (require != 0) cmd.CommandText = update 課程信息表 set 開始周次 = + require + where 課程號 = + cource_num + ; cmd.ExecuteNonQuery(); else if (week_num = 16) cmd.CommandText = update 課程信息表 set 開始周次 = 1 where 課程號 = + cource_num + ; cmd.ExecuteNonQuery(); else if (week_n

25、um = 8) if (i / 2 = 0) cmd.CommandText = update 課程信息表 set 開始周次 = 1 where 課程號 = + cource_num + ; cmd.ExecuteNonQuery(); else cmd.CommandText = update 課程信息表 set 開始周次 = 9 where 課程號 = + cource_num + ; else cmd.CommandText = update 課程信息表 set 開始周次 = 1 where 課程號 = + cource_num + ; cmd.ExecuteNonQuery(); i+

26、; /MessageBox.Show(開始周數已分配！); else MessageBox.Show(教師任務書為空！); /約定無課時間安排、選修課時間安排，用變量接受，每次排課時間上排除掉 /排課結束4.1.2教師模塊 private void button5_Click(object sender, EventArgs e) SqlConnect(); string sql1 = ;/; SqlCommand cmd1 = new SqlCommand(sql1, conn); cmd1.CommandText = select * from 選課表; SqlDataReader rea

27、der11 = cmd1.ExecuteReader(); if (reader11.Read() if (radioButton1.Checked = true) SqlConnect(); string num = textBox1.Text; string sql = ;/; SqlCommand cmd = new SqlCommand(sql, conn); if (id = 教師) cmd.CommandText = select * from 教師信息表 where 工號 = + num + ; /只有一條 SqlDataReader reader = cmd.ExecuteRe

28、ader(); if (reader.Read() name_N = reader姓名.ToString().Trim(); else reader.Close(); else cmd.CommandText = select * from 教師信息表 where 工號 = + num + ; /只有一條 SqlDataReader reader = cmd.ExecuteReader(); if (reader.Read() name_N = reader姓名.ToString().Trim(); else MessageBox.Show(該職工號不存在，請核對！); reader.Clos

29、e(); SqlDataAdapter adapter = new SqlDataAdapter(select * from 教師任務書 where 工號= + num + , conn);/確定這位老師所有任務號 DataSet ds = new DataSet(); adapter.Fill(ds, mytable); if (ds.Tables0.Rows.Count != 0) for (int i = 0; i ds.Tables0.Rows.Count; i+)/對一個任務號 進行 一系列查詢 /課程信息查詢 cource_num = ds.Tables0.Rowsi課程號.ToS

30、tring().Trim(); week_num = Convert.ToInt32(ds.Tables0.Rowsi周數.ToString().Trim(); string pross = ds.Tables0.Rowsi所教專業(yè).ToString().Trim(); cmd.CommandText = select * from 課程信息表 where 課程號= + cource_num + ; SqlDataReader reader1 = cmd.ExecuteReader(); if (reader1.Read() course_name = reader1課程名.ToString(

31、).Trim(); teststyle = reader1考試形式.ToString().Trim(); score = reader1學分.ToString().Trim(); totalhour = reader1課時.ToString().Trim(); startweek = reader1開始周次.ToString().Trim(); int startweeks = Convert.ToInt32(startweek.ToString().Trim(); int endweeks = startweeks + week_num - 1; string endweek = endwe

32、eks.ToString().Trim(); weeks = + startweek + - + endweek + ; else reader1.Close(); /該老師 該任務號 該課程的排課時間 地點 4.2測試方案設計測試方式：黑盒測試，白盒測試。原因：由于白盒測試需要進行某種路徑覆蓋，而無論是邏輯覆蓋還是路徑覆蓋，都由于數據量過大而無法設計測試用例。故前期只采用白盒測試（部分），后期均采用黑盒測試，且測試數據來自前期的數據。由于基本模塊在單元測試時全都通過，而且接口均為標準化接口，而較大的模塊只是調用該接口，故只需在接口進行測試，即可保證數據的正確性。測試結果：測試結果分析：大部分

33、的測試都較為平穩(wěn)，主要原因在于大部分的工作都由數據庫來做，而數據庫的查詢一般情況下是安全的。而由于使用了SQL Server的性能分析器后，查詢性能一般較高。第五章 用戶使用說明書(1)首先將VS和數據庫相連接，然后在VS中打開項目，點擊調試程序，出現主界面(2)選擇相應的身份，輸入用戶名和密碼進入到系統(tǒng)中，在此以管理員為例，輸入用戶名和密碼后，進入選擇界面(3)首先，進行初步排課，選擇某個下午作為休息日，再選擇進行排選修課的時間(4)初步排課完成后，就可以進行相應的查詢了，因為是管理員登錄，可以查詢每個老師的課表和每個教室的課表(5)輸入對應的教職工號和教室號可以查詢到相應的課表信息由于時間

34、緊迫，調課模塊和修改密碼模塊僅僅完成了界面，還未實現其功能。第六章 實驗總結 實驗前期，由于該實驗的前期部分的過程最為困難。教務系統(tǒng)較為龐大，即使是子系統(tǒng)，也很難做的很完善。由于排課需要根據教學任務進行，而教學任務牽涉到課程、班級、教師等多種信息，而課程、班級等實體又有各自的屬性，并且彼此相連，在查詢時就會變得非常復雜。故一個良好的數據庫體系結構設計是非常重要的。數據庫的建立中，遇到了如下的問題。外鍵的基表必須是主鍵而非主屬性。故無論是用B作基表還是用A作基表，主鍵都大于1個，而外鍵只有1個，故列不匹配。而一對一的實現不符合外鍵的定義，故被數據庫否決。在咨詢了兩位老師之后，小組成員進行了討論。大家一致認為沒有合適的解決方案。故解決的辦法是不設此外鍵，而是采用程序控制的方式讓這兩個表建立聯系，并在開發(fā)文檔中標明。在這一部分測試較為用心。 編碼階段由于表比較多，排課設計的條件比較多，查看了大量的關于排課的算法，最終決定用貪心算法。當一個問題具有最優(yōu)子結構性質時，我們會想到用動態(tài)規(guī)劃法去解它，但有時會有更簡單、更有效的算法，即貪心算法。顧名思義，貪心算法總是做出在當前看來最好的選擇。也就是說貪心算法并不是整體最優(yōu)上加以考慮，他所作出的選擇只是在某種意義上的局部最優(yōu)的選擇