遺傳演算為基的研究所入學考試時間表及考場排程法

Abstract

本文提出一個以遺傳演算法為基的研究所入學考試時間表及考場排程法。針對目前大多以人工方式分兩階段排程的研究所入學考試問題，提出一套混合編碼遺傳演算排程法以期能排出更接近全域最佳解的結果。該排程法包含兩種不同的遺傳演算編碼染色體。數值型編碼的染色體可在不違反考科互斥限制的情況下排定各考科堂次，排序型編碼的染色體則排出最能節省成本的考場分配結果。另外相較於一般考試時間表排程問題，研究所入學考試問題的成本主要落在考場使用數量及監考人員雇用數量。本研究並根據所提出的方法實作一套求解系統，以近年來台、政大的研究所入學考試資料作為範例驗證其可行性。實證結果也顯示本研究所提出的排程法可以有效地縮減監考堂次的成本，並提供介面可清楚地展示排程後的結果。

This thesis proposed a genetic algorithm based timetable scheduling method for Graduate Institute Entrance Examination Timetabling Problem (GIEETP). GIEETP used to be scheduled manually in a 2-phase procedure. In order to approach the global optimum, this research presents a combined-coded genetic algorithm (GA) based scheduling method. This method includes two different types of chromosome encoding, real-valued encoding and permutation encoding. The first chromosome allocates timeslots for all subjects and avoids the mutual-exclusive constraints within subjects. The second chromosome arranges sequence for room allocation. In contrast to other exam timetabling problems, GIEETP emphasizes on the cost of total rooms used and the invigilators hired. The scheduling method is implemented in a software system, and real GIEETP data in recent years is taken as example to facilitate result comparisons. Results show that our method in general can obtain a solution more efficiently.