計算機外文翻譯---定義，建模和求解一個真正的大學課程表問題

1、<p><b>　　外文文獻資料</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 ‘‘almost good’’ previous timetable saved about two and a half minutes.</p><p><b>　　中文翻譯稿</b></p><p>　　（外文文件名：定義，建模和求解一個真正的大學課程表問題）</p><p>　　翻譯：蘇州大學應用技

78、術學院 06計算機 陸婷</p><p><b>　　2010年4月</b></p><p><b>　　介紹</b></p><p>　　如同許多現實生活中的問題，大學課程時間表問題可以是混亂和復雜。求解大學課程表問題涉及溝通，努力實現一個時間表，以滿足一系列要求和目標設置了許多人。正如第三章解釋，對自動時間表文學往往需

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

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

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

82、更加容易。</p><p><b>　　約束</b></p><p>　　在上課時間表域，有兩種類型的約束。硬約束，不能侵犯，因為如果他們的時間表將是不可行的限制。軟約束，相反，作為著名的喜好，有沒有時間表，以使該盡可能好。較少的軟約束行為表示時間表更好。此外，在加拿大多倫多大學的例子，有些情況下出現的，由于該方案的性質，嚴重制約了時間表。雖然這是一個稍微不同的含義的

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

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

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

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

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

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

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

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

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

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

93、問題是，沒有已知的每班學生人數為一年級的調度。由于參觀人數不上課之后才知道，這是不可能的時間表與已知的每班學生人數第一年的時間表。但是，后來在今年夏天的第一年，計劃，更準確的每班學生人數的估計。這將是一個好主意，改變調度順序和時間安排第一年的最后，所有其他年份后完成。有幾個原因，列在本章前面的調度第一年。然而，當第一年的時間表，必須改變最后一分鐘，由于每班學生人數不明，但最終被定最后反正。唯一不同的是，它是由第一次調度浪費時間。調度部門

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

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

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

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

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