教養科目履修の最適割当アルゴリズムの提案

摘要

現在，岡山大学の教養科目は，主題，個別，ガイダンス，外国語の4つの科目群で構成されている．その中で選択の自由度の高い主題科目群および外国語科目群では，事前に学生が履修希望の科目を順位付けして提出し，それを基に各学生への科目割当を行っている．この数千人にのぼる学生の履修科目割当にあたり，教室定員，希望の偏り，キャンパス間の移動などを考慮しながら，全学生の希望を最大限に充足することは非常に困難である．そこで本稿では，この履修科目割当を組合せ最適化問題として定式化し，その2段階アルゴリズムを提案する．Ruby 言語を用いて本アルゴリズムを実装し，実際のデータを用いた実験結果により，その有効性を検証する．%Currently, general academic subjects in Okayama University consist of four categories, namely, "main subjects", "individual subjects", "guidance subjects", and "foreign language subjects". Among them, for "main subjects" and "foreign language subjects" that have much freedom in choice, students are requested to submit the ranks of the subjects that they want to take in the next semester beforehand. Then, the assignment of subjects to students is processed manually using the submitted ranks. However, this assignment task is very hard because it is necessary to assign fairly several thousand students at the same time while considering the capacity of each classroom, the bias in popularity among subjects, and movements of students between two distant campuses. In this paper, we define the assignment problem of general academic subjects to students as a combinational optimization problem, and propose its heuristic algorithm composed of two stages. We implement the algorithm as a Ruby application, and verify the effectiveness using real data in our university.