計(jì)算機(jī)外文翻譯---定義，建模和求解一個(gè)真正的大學(xué)課程表問題

1、<p><b>　　外文文獻(xiàn)資料</b></p><p>　?。ㄍ馕奈募篋efining,Modeling,and Solving a Real University Course Timetabling Problem）</p><p>　　Introduction</p><p>　　As with many real lif

2、e problems, the university course timetabling problem can be messy and complicated. Solving the university course timetabling problem involves many people communicating to try to achieve a timetable that meets a set of r

3、equirements and goals. As explained in Chapter 3, the literature on automated timetabling often takes a given timetabling problem and reduces it to a mathematical definition, which can then be solved. In reality, there i

4、s a lot more to a real world timetablin</p><p>　　This chapter looks, in detail, at the timetabling problem at the faculty of applied science and engineering at the University of Toronto (APSC). The process d

5、escribed is the one that took place in order to create the timetable for the 2006-2007 school year. This process shows how real world problems are actually much more complicated than what appears in a mathematical model.

6、 As well, a detailed analysis of a given problem is a step towards creating a problem definition. It allows one to identif</p><p>　　The undergraduate program at APSC consists of four years of study. There ar

7、e 4000 students, over 1200 of which are first years. There are seven departments and nine degree programs totaling 79 POSts1. There are 219 faculty members, 12 buildings, and 80 lab rooms that are managed internally. The

8、 faculty uses a software scheduling package that is part of the Syllabus Plus suite of scheduling products. In particular the software Course Planner (CP) is used to schedule, identify issues, and support </p><

9、;p>　　Constraints</p><p>　　In the timetabling domain, there are two types of constraints. Hard constraints are constraints that cannot be violated because if they were, the schedule would be infeasible. So

10、ft constraints, otherwise known as preferences, are there to make the timetable as good as possible. Fewer soft constraint violations mean that the schedule is better. In addition, in the University of Toronto example, t

11、here are certain situations that arise, due to the nature of the program, that seriously constrain the</p><p><b>　　Strategy</b></p><p>　　There is no written protocol that is followed

12、 when creating the timetable. This is because every year is unique and different than the previous one. There is, however, a general strategy that is used. The basic steps that make up the scheduling process are the same

13、 each year. First is data acquisition. Second is deciding on the rollover strategy. The rollover strategy is deciding what part of the previous year's schedule is kept and rolled over for the following year. After th

14、e rollover strategy</p><p>　　The scheduling process really begins before the data acquisition stage, with the creation of the curriculum and calendar. However, this part of the process is not discussed here.

15、 In the following sections, each step in the above scheduling process will be looked at in more detail.</p><p>　　Problems in the Process</p><p>　　There are many areas of the process where there

16、is a need for improvement. These problems range from technical issues such as there being too much data being entered manually, to communication issues, to political issues within the faculty. Some can benefit from an IT

17、 solution, and some cannot.</p><p>　　IT Solutions</p><p>　　There are several instances during the process where automation would be helpful. The obvious one is that of the creation of the timeta

18、ble. Software is currently used, but that software requires a lot of interaction and in a way it is merely a database that holds data and notifies the user when conflicts exist, while the timetable is actually created ma

19、nually. The CP software can schedule automatically, but from experience, the created schedules are often quite far from ideal. CP often has a lot</p><p>　　The proposed solution, from the director of scheduli

20、ng, is to make the process of verifying, collecting, and updating data electronic. A database could be created from which the calendar data could be uploaded electronically to CP. Also, data collection could be done thro

21、ugh online forms, where there could be input restrictions so that the counselors would not be allowed to fill out the forms incorrectly and blank slots would not be permitted. The data from these forms could then be uplo

22、aded ele</p><p>　　Another area where an IT solution would be useful is that of the disconnect between the systems used for the schedule. When a change is made to the schedule, three systems must be updated:

23、CP, ROSI, and the Room Reservation System (RRS). Often, there are different people updating the different systems and if it is not done simultaneously, someone may work on one of the systems assuming it is up to date whe

24、n it is not. This can cause problems. It would be useful to connect the systems so that whe</p><p>　　Non-IT Solutions</p><p>　　There are two reasons why an IT solution may not be possible: there

25、 is no IT solution that applies to the specific problem, or the IT solution that applies is not feasible.</p><p>　　The biggest issue existing in the current timetabling process is that of communication durin

26、g the data acquisition phase. During this phase, the counselors are supposed to get all the requirements from the faculty in regards to their schedule preferences and necessities. Faculty are supposed to supply their dep

27、artments with the delivery of the courses they will be teaching. Delivery refers to the number of sections the course should have and the number and length of all meetings of the course. F</p><p>　　Although

28、it may be possible to have an IT solution where faculty members could enter their data online, instead of going through the counselor, it is likely infeasible to expect "buy in" from all the faculty members. A

29、more realistic solution would be to develop a written policy that includes a date by which the departments must have all their teaching assignments done, a date by which the faculty members must submit their scheduling d

30、ata, and what data must be included. The scheduling office wo</p><p>　　Another issue that can be resolved without an IT solution is that of scheduling without known class sizes for first year. Since the admi

31、ssion numbers are not known until after classes start, it is impossible to schedule the first year schedule with known class sizes. However, the later on in the summer the first year is scheduled, the more accurate the e

32、stimate of the class sizes. It would be a good idea to change the scheduling order and schedule first year last, after all the other years are c</p><p>　　Conclusion</p><p>　　University course ti

33、metabling problems are combinatorial problems, which consist of scheduling a set of courses within a given number of rooms and time periods. Solving a real world timetabling problem manually often requires a significant

34、amount of time, sometimes several days or even weeks. Therefore, a lot of research has been invested in order to provide automated support for human timetablers. Contributions come from the fields of operations research

35、and artificial Intelligence. This paper </p><p>　　Applying classical methods from constraint satisfaction requires to model the problem as a constraint satisfaction problem, a set of variables, each associat

36、ed with a domain of values it can take on, and a set of constraints among the variables. Constraints are relations that specify the space of solutions by forbidding combinations of values.</p><p>　　Methods i

37、nclude search, heuristics, and constraint propagation. Typically, systematic search assigns values to variables sequentially following some search order. If the procedure fails to extend a partial solution, decisions are

38、 undone and alternatives explored. Systematic search often relies on heuristics, which define the order in which variables and values are chosen. Constraint propagation is complementary; it simplifies a problem by identi

39、fying values that cannot participate in a solution.</p><p>　　In practice, most constraint-based timetabling systems either do not support soft constraints or use a branch and bound search instead of chronolo

40、gical backtracking. Branch and bound starts out from a solution and requires the next solution to be better. Quality is measured by a suitable cost function that depends on the set of violated soft constraints. With this

41、 approach, however, soft constraints play no role in selecting variables and values.</p><p>　　After collecting wishes of teacher and information on the new courses, a first proposal is developed with the tim

42、etable of the previous year as a starting point. This is done by using free slots in the timetable left by courses not taking place again for new courses offered by the same people, whereas wishes of teachers take preced

43、ence over the timetable of the previous year. After handing out the proposal to all teachers, evaluations and new wishes are collected. </p><p>　　With the current proposal as a starting point, a new proposal

44、 is developed incorporating the responses on the current proposal, again changing as little as possible, and so on. Creating a new timetable is thus a multistage, incremental process. Relying on the timetable of the prev

45、ious year and changing as little as possible by incremental scheduling drastically reduces the amount of work necessary for creating a new timetable and ensures acceptance of the new timetable by keeping the weekly cour&

46、lt;/p><p>　　Note that the assignment of rooms is done elsewhere. Nevertheless, conflicting requirements for space or certain equipment may be a cause for changing the timetable. </p><p>　　The gener

47、al constraints are due to physical laws, academic reasons, and personal preferences of teachers: </p><p>　　A teacher cannot be in two places at the same time, so avoid clashing the courses of a teacher. Ther

48、e should be at least a one hour break between two courses of a teacher.</p><p>　　Some teachers prefer certain times or days for teaching.</p><p>　　Monday afternoon is reserved for professors’ me

49、etings: Do not schedule professors’ courses for Monday afternoon. </p><p>　　The department consists of five units, each dedicated to a certain area of research. Most courses are held by members of a single

50、unit while only a few courses are held by members of different units. Courses held by members of a certain unit must not clash with courses held by other members of the same unit.</p><p>　　An offering typica

51、lly consists of two lectures and a tutorial per week. There should be a day break between the lectures of an offering. The tutorial should not take place on a day, on which a lecture of the same offering takes place. All

52、 courses should be scheduled between9 a.m.and6 p.m. No lectures should be scheduled for Friday afternoon. No tutorials should be scheduled for late Friday afternoon.</p><p>　　Only few of the courses are mand

53、atory for and dedicated to students of a certain term, while most courses are optional and open to all students. For each term of the undergraduate studies there is a set of mandatory courses, the attendance of which is

54、highly recommended. Courses of the graduate studies only rely on the knowledge provided by courses of the undergraduate studies. There is no recommended order of attendance. Undergraduate courses of a term must not clash

55、, while undergraduate course</p><p>　　First observations made clear that existing timetables do not meet the requirements stated, e.g., courses of a unit or graduate courses clash or a lecture of an offering

56、 and a tutorial of the same offering are scheduled for the same day. Furthermore, considering the number of graduate courses offered over the years, it became clear that there is too little space to schedule all graduate

57、 courses without clashes. This is due to the following reason. As mentioned before, undergraduate courses are m</p><p>　　The demand for incremental scheduling by basing the new timetable on the timetable of

58、the previous year and changing as little as possible made it necessary to handle old timetables, which do not meet the requirements stated. </p><p>　　From a scheduler’s point of view, the graduate studies la

59、ck structure taking freedom and leading to over constrained timetable specifications.</p><p>　　Tackling the second problem by removing selected no-clash constraints turned out to be laborious and time-consum

60、ing and, therefore, impractical. Classifying graduate courses by contents and expected number of students and allowing clashing of courses of different categories won back some freedom, but it was not possible to identif

61、y enough categories in such a way that courses spread evenly over categories, which would have been necessary to prevent conflicts. It became clear that we were in need</p><p>　　A Constraint Satisfaction Pro

62、blem(CSP)consists of a finite set of variables, each associated with a finite domain and a finite set of constraints. A solution of a CSP maps each variable to a value of its domain such that all the constraints are sati

63、sfied. A partial constraint satisfaction problem(PCSP) is a CSP where each constraint is associated with a weight. A weight of a constraint expresses the importance of its fulfillment, allowing one to distinguish hard co

64、nstraints from soft constraints</p><p>　　Clearly, we only need one variable for each course holding the period, the starting time point, it has been scheduled for. Each variable’s domain consists of the whol

65、e week, the periods being numbered from0 to 167, for example,9 denotes 9 a.m. on Monday, and so on. Requirements, wishes, and recommendations can be expressed with a small set of specialized constraints.</p><p

66、>　　No-clash constraints demand that a course must not clash with another one.</p><p>　　Preassignment constraints and availability constraints are used to express teachers’ preferences and that a course mu

67、st take place at a certain time.</p><p>　　Distribution constraints make sure that there is at least one day between a course and another, or that two courses are scheduled for different days.</p><

68、p>　　Compactness constraints make sure that one course will be scheduled directly after another.</p><p>　　With respect to soft constraints, three grades of preferences were chosen: weakly preferred, prefer

69、red, and strongly preferred, which get translated to the integer weights1,3, and9.</p><p>　　The search procedure employed integrates the solver given above with chronological backtracking and heuristics for

70、variable and value selection. For variable selection, the first fail principle was chosen, which dynamically orders variables by increasing cardinality of domains, the principle proposes to select one of the variables wi

71、th the smallest domains with respect to the current state of computation. For value selection, a best-fit strategy was used choosing one of the best rated periods. F</p><p>　　The generation of a timetable ru

72、ns as follows. Each course is associated with a domain constraint allowing for the whole week, the periods being numbered from 0 to 167. It is important to note that, for each course, the initial assessment for all perio

73、ds is 0 indicating that no period is given preference initially. Then preassignment constraints and availability constraints will be translated into in and not in constraints. Adding in and not in constraints may narrow

74、the domains of the courses u</p><p>　　Now that we have discussed the details of creating a timetable, how does one create a new timetable based on a timetable of the previous year with this system? Central t

75、o our solution is the notion of fixing a timetable. Fixing a timetable consists in adding a soft preassignment constraint for each course that has been scheduled ensuring that all courses offered again will be scheduled

76、for the same time.</p><p>　　The time necessary to compute a timetable depends on whether a previous timetable is reused or not. Scheduling 89 courses within 42 time periods from scratch took about five minut

77、es. Considering an ‘‘a(chǎn)lmost good’’ previous timetable saved about two and a half minutes.</p><p><b>　　中文翻譯稿</b></p><p>　?。ㄍ馕奈募憾x，建模和求解一個(gè)真正的大學(xué)課程表問題）</p><p>　　翻譯：蘇州大學(xué)應(yīng)用技

78、術(shù)學(xué)院 06計(jì)算機(jī) 陸婷</p><p><b>　　2010年4月</b></p><p><b>　　介紹</b></p><p>　　如同許多現(xiàn)實(shí)生活中的問題，大學(xué)課程時(shí)間表問題可以是混亂和復(fù)雜。求解大學(xué)課程表問題涉及溝通，努力實(shí)現(xiàn)一個(gè)時(shí)間表，以滿足一系列要求和目標(biāo)設(shè)置了許多人。正如第三章解釋，對(duì)自動(dòng)時(shí)間表文學(xué)往往需

79、要一個(gè)給定的時(shí)間表問題，并降低它的數(shù)學(xué)定義，然后可以解決。在現(xiàn)實(shí)中，有很多更真實(shí)的世界時(shí)間表，以這樣一個(gè)定義為代表的問題。該時(shí)間表的過程是漫長(zhǎng)的，包括以前的許多階段課程的實(shí)際放置到時(shí)隙。在解決一個(gè)或問題的第一階段涉及的系統(tǒng)的詳細(xì)研究，確定具體的問題，制度約束和目標(biāo)函數(shù)。</p><p>　　本章看起來，詳細(xì)，在應(yīng)用科學(xué)和工程學(xué)院舉行的多倫多（亞太空間中心）大學(xué)的時(shí)間表問題。介紹的方法，是一個(gè)發(fā)生在以創(chuàng)造為2006

80、-2007學(xué)年時(shí)間表。這一過程顯示了如何真實(shí)世界的問題，實(shí)際上要復(fù)雜得多比在數(shù)學(xué)模型中。同樣，一個(gè)給定問題的詳細(xì)分析，是朝著建立一個(gè)問題的定義步驟。它允許一個(gè)進(jìn)程，以確定所有問題，約束，限制和目標(biāo)，從而提供的信息可能會(huì)在問題的定義包括基地。</p><p>　　在亞太空間中心的本科課程包括4年。有4000多學(xué)生，其中1200是第一年。有七個(gè)部門和9個(gè)學(xué)位課程共79 POSts1。有教職工219，12座和80所實(shí)驗(yàn)

81、室內(nèi)部管理室。教師使用的軟件調(diào)度包的課程加上調(diào)度產(chǎn)品套件的一部分。特別是軟件課程規(guī)劃師（CP）是用來計(jì)劃，識(shí)別問題，并支持決策。 CP是一個(gè)軟件包，使用多種啟發(fā)式時(shí)調(diào)度。 75％的時(shí)間表交付給個(gè)別學(xué)生無沖突，對(duì)方案的結(jié)構(gòu)。在以下章節(jié)中，我們描述的目標(biāo)是試圖實(shí)現(xiàn)的時(shí)間表，所涉及的限制，戰(zhàn)略，這個(gè)過程中，創(chuàng)建時(shí)使用的時(shí)間表。然后，我們提出一些在目前的過程中存在問題的地區(qū)和突出的地區(qū)可能是有益的。確定在哪些領(lǐng)域可以有所幫助，應(yīng)使問題的定義問題

82、更加容易。</p><p><b>　　約束</b></p><p>　　在上課時(shí)間表域，有兩種類型的約束。硬約束，不能侵犯，因?yàn)槿绻麄兊臅r(shí)間表將是不可行的限制。軟約束，相反，作為著名的喜好，有沒有時(shí)間表，以使該盡可能好。較少的軟約束行為表示時(shí)間表更好。此外，在加拿大多倫多大學(xué)的例子，有些情況下出現(xiàn)的，由于該方案的性質(zhì)，嚴(yán)重制約了時(shí)間表。雖然這是一個(gè)稍微不同的含義的

83、限制，他們將被稱為制約因素，他們將在本節(jié)列出。</p><p><b>　　戰(zhàn)略</b></p><p>　　無書面協(xié)議，其次是在創(chuàng)建時(shí)間表。這是因?yàn)槊恳荒甓际仟?dú)特的，比以往有所不同。有，但是，一般的策略是使用。在構(gòu)成該調(diào)度程序的基本步驟是相同的，每年。首先是數(shù)據(jù)采集。二是決定的過渡戰(zhàn)略。轉(zhuǎn)期的策略是什么樣的決定前一年的計(jì)劃的一部分，是保持并推出下一年了。后過渡戰(zhàn)略是

84、確定的，每年的時(shí)間表安排，一次一個(gè)，開始與第一年的計(jì)劃和完成了第四年了。</p><p><b>　　過程中存在的問題</b></p><p>　　有許多的過程，其中有許多需要改進(jìn)的一個(gè)領(lǐng)域。這些問題的范圍，例如有太多的數(shù)據(jù)被輸入了手動(dòng)，溝通問題，在教師的政治問題從技術(shù)的問題。有些可以受益于一個(gè)IT解決方案，有些卻不能。</p><p><

85、;b>　　IT解決方案</b></p><p>　　有幾次在這個(gè)過程中，自動(dòng)化將是有益的。最明顯的一個(gè)是，在時(shí)間表的創(chuàng)建。目前使用的軟件，但軟件需要一個(gè)互動(dòng)的方式很多，它僅僅是一個(gè)數(shù)據(jù)庫(kù)，保存數(shù)據(jù)，并通知用戶時(shí)存在沖突，而實(shí)際上是手動(dòng)創(chuàng)建的時(shí)間表。 CP的軟件可以自動(dòng)時(shí)間表，但是從經(jīng)驗(yàn)，創(chuàng)建的時(shí)間表往往很遠(yuǎn)的理想。處長(zhǎng)往往是很難找到一個(gè)時(shí)間表，這并不違反很大限制。處長(zhǎng)沒有，畢竟，使用啟發(fā)式使其調(diào)

86、度決定，這未必是最好的選擇。利用數(shù)學(xué)規(guī)劃，建立一個(gè)模型可以解決亞太空間中心時(shí)間表問題。這種模式可能并不需要太多的互動(dòng)。它將采取數(shù)據(jù)并創(chuàng)建一個(gè)時(shí)間表，然后可以由用戶修改。</p><p>　　還有其他一些地區(qū)，早些時(shí)候在亞太空間中心的過程，也可從中受益自動(dòng)化。對(duì)調(diào)度處處長(zhǎng)已確定了這些領(lǐng)域，以及建議的解決方案。其中一個(gè)領(lǐng)域是核實(shí)CP和日歷數(shù)據(jù)的一步。這是當(dāng)前一本手冊(cè)，兩個(gè)人的過程，涉及從三個(gè)不同的來源交叉核對(duì)數(shù)據(jù)。

87、假如這些電子數(shù)據(jù)連接，很多的時(shí)間將被保存。此外，在數(shù)據(jù)采集階段，數(shù)據(jù)收集，通過電子表格。這一過程涉及來回傳遞信息的獲取，每次稍微改變。這一進(jìn)程正在做手工，創(chuàng)造了許多誤解和錯(cuò)誤的機(jī)會(huì)。錯(cuò)誤包括錯(cuò)誤地填寫表格，以及缺少的信息。第三個(gè)領(lǐng)域，自動(dòng)化將是有益的是，更新后的CP完成數(shù)據(jù)的電子表格。這是手工完成。</p><p>　　建議的解決方案，從調(diào)度主任，是要核實(shí)過程中，收集和更新數(shù)據(jù)的電子?？梢越⒁粋€(gè)數(shù)據(jù)庫(kù)從該日歷可

88、以上傳電子數(shù)據(jù)到CP。此外，數(shù)據(jù)收集可以通過在線表格，那里可以輸入，這樣的輔導(dǎo)員將不能錯(cuò)誤地填寫表格和空白時(shí)段進(jìn)行限制，將不會(huì)獲得批準(zhǔn)。這些形式的數(shù)據(jù)便可以電子方式上傳到CP。這種解決辦法將節(jié)省大量的時(shí)間以及防止許多錯(cuò)誤。</p><p>　　另一個(gè)領(lǐng)域的IT解決方案將是有益的是，斷開系統(tǒng)之間的時(shí)間安排使用。若改變了預(yù)定計(jì)劃，三個(gè)系統(tǒng)必須進(jìn)行更新：CP，ROSI和客房預(yù)訂系統(tǒng)（RRS）版。通常，不同的人有不同的系

89、統(tǒng)更新，如果它沒有這樣做的同時(shí)，可能有人會(huì)工作的系統(tǒng)之一，它假設(shè)是最新的時(shí)候并非如此。這可能會(huì)導(dǎo)致問題。它是有用的連接系統(tǒng)，以便當(dāng)一個(gè)更新時(shí)，其他人也是如此。</p><p><b>　　非IT解決方案</b></p><p>　　有兩個(gè)原因，一個(gè)IT解決方案可能是不可能的：沒有任何的IT解決方案，適用于對(duì)具體問題，或IT解決方案，適用是不可行的</p>

90、<p>　　最大的問題在目前的時(shí)間安排過程中存在的是，在數(shù)據(jù)采集通信階段。在這個(gè)階段，輔導(dǎo)員都應(yīng)該得到所有從教師要求問候他們的日程安排的喜好和需要。教師都應(yīng)該提供的課程，他們提供自己的部門將教學(xué)。交付是指部分當(dāng)然應(yīng)該有多少的數(shù)量和培訓(xùn)班的所有會(huì)議的長(zhǎng)度。學(xué)院成員也應(yīng)該提供他們母嬰同室的要求。這是當(dāng)前進(jìn)程中非常普遍，教師不提供在數(shù)據(jù)采集階段多的數(shù)據(jù)。在這種情況下，假定有沒有嚴(yán)格的限制和交付是一樣的東西是寫在日歷中。這也是一個(gè)強(qiáng)

91、有力的教師共同來與調(diào)度辦公室要求或投訴后的時(shí)間表完成，并上載。這些要求的范圍從不同的房間，希望想改變一個(gè)小時(shí)的實(shí)驗(yàn)室是一個(gè)三小時(shí)的實(shí)驗(yàn)室。</p><p>　　雖然它可能有一個(gè)IT解決方案，其中教師成員可以進(jìn)入他們的在線數(shù)據(jù)，而不是通過輔導(dǎo)員去，它可能是不可行的期望“購(gòu)買”的所有教員。更現(xiàn)實(shí)的解決辦法是制定一份書面的政策，其中包括一個(gè)日期，其中各部門必須完成所有的教學(xué)任務(wù)，日期，其中教師成員必須提交他們的調(diào)度數(shù)據(jù)

92、，什么數(shù)據(jù)必須被包括在內(nèi)。調(diào)度辦公室，然后要求批準(zhǔn)從教師的要求有任何偏差，將不會(huì)改變?nèi)粘贪才胚M(jìn)行一次上傳。類似的政策將是有益的問候課程發(fā)展。應(yīng)該沒有過去的某一個(gè)日期提出課程改革。實(shí)施這樣一套嚴(yán)格的規(guī)則不會(huì)是一個(gè)簡(jiǎn)單的任務(wù)。理想情況下，課程委員會(huì)將提前一年他們現(xiàn)在在哪里。該時(shí)間表將調(diào)整需要時(shí)間和精力，雖然這將是很好的安排，這將意味著每年將需要更長(zhǎng)的課程更改生效。</p><p>　　另一個(gè)可以沒有IT解決方案解決的

93、問題是，沒有已知的每班學(xué)生人數(shù)為一年級(jí)的調(diào)度。由于參觀人數(shù)不上課之后才知道，這是不可能的時(shí)間表與已知的每班學(xué)生人數(shù)第一年的時(shí)間表。但是，后來在今年夏天的第一年，計(jì)劃，更準(zhǔn)確的每班學(xué)生人數(shù)的估計(jì)。這將是一個(gè)好主意，改變調(diào)度順序和時(shí)間安排第一年的最后，所有其他年份后完成。有幾個(gè)原因，列在本章前面的調(diào)度第一年。然而，當(dāng)?shù)谝荒甑臅r(shí)間表，必須改變最后一分鐘，由于每班學(xué)生人數(shù)不明，但最終被定最后反正。唯一不同的是，它是由第一次調(diào)度浪費(fèi)時(shí)間。調(diào)度部門

94、打算嘗試在新的一年的最后安排的第一年。</p><p><b>　　結(jié)論</b></p><p>　　大學(xué)的排課系統(tǒng)是一個(gè)組合的問題，這個(gè)問題是由在規(guī)定的房間和時(shí)間段的數(shù)量?jī)?nèi)安排一套課程組成。解決為問題訂時(shí)間表的一個(gè)現(xiàn)實(shí)世界手工經(jīng)常需要相當(dāng)多數(shù)量的時(shí)間，有時(shí)幾天或者甚至周。因此，許多研究已被投資為了提供對(duì)于人類課程表的自動(dòng)化的支持。貢獻(xiàn)來自運(yùn)籌學(xué)和人工智能的領(lǐng)域。 本

95、文參照學(xué)期和方法來滿足限制條件。方法提出使用約束邏輯編寫程序被發(fā)展。約束邏輯編寫程序把邏輯編寫程序的語(yǔ)句與從運(yùn)籌學(xué)和人工智能的方法的效率相結(jié)合。 它最近成為解決時(shí)間表問題的一種有前途的方法。</p><p>　　從滿足限制運(yùn)用古典的方法要求作一個(gè)滿足限制問題的模擬問題，一套變量，每一個(gè)帶有它能承擔(dān)的價(jià)值的一個(gè)領(lǐng)域，和在變量中間的一套約束。約束是通過禁用的結(jié)合價(jià)值規(guī)定解決方案的空間的關(guān)系。</p>&

96、lt;p>　　方法包括搜索，啟發(fā)式，和約束傳播。 典型地，系統(tǒng)的搜索把價(jià)值分配到依次地跟隨一些搜索秩序的變量。如果過程沒能擴(kuò)展一種部分的解決，被取消與選擇探索的決定。 系統(tǒng)的搜索經(jīng)常依賴于啟發(fā)式，這定義在其中變量和價(jià)值被選擇的秩序。約束傳播是補(bǔ)充的； 它通過識(shí)別不能參加一種解決的價(jià)值簡(jiǎn)化一個(gè)問題。 這方法搜索空間剪除與搜索變得容易。</p><p>　　在實(shí)踐中，大多數(shù)以約束為基礎(chǔ)的時(shí)間表系統(tǒng)不支持或者是輕

97、微的約束或者是使用一個(gè)分支和境界代替搜索時(shí)序回溯。 分支和境界從一種解決開始并且要求下一種解決是更好的。質(zhì)量依賴于輕微的約束的裝置的一個(gè)適合的費(fèi)用功能測(cè)量。 有了這方法，然而，在選擇變量和價(jià)值中較弱的約束將不起起作用。</p><p>　　在收集教師的要求之后和關(guān)于新的過程的信息，第一項(xiàng)建議作為一個(gè)起始的點(diǎn)以前一年的課程表被發(fā)展。這被再一次為了被同樣的人們提供的新的過程不發(fā)生的過程被在課程表中使用自由的狹縫完成左

98、邊左，而教師的要求優(yōu)先于前一年的課程表。 在把建議分發(fā)到所有教師的估計(jì)和新的要求之后將加以收集。</p><p>　　從當(dāng)前的建議一個(gè)起始開始，一項(xiàng)新的建議被發(fā)展在當(dāng)前的建議上結(jié)合修改，再一次可能少量的改動(dòng)等等。建立一張新的課程表，這樣是一個(gè)多級(jí)而逐漸增長(zhǎng)的過程。 依賴于上學(xué)期的課程表，改變盡可能少量的信息，減少為建立一張新的課程表所需要的工作的量，并且通過保持人們每星期保證接受新的課程表的習(xí)慣。</p&g