Key points are not available for this paper at this time.
강의 배정 문제에서 대학 관리자는 이질적인 선호를 가진 학생들에게 수요가 많은 강의 일정을 효율적이고 공정하게 배정하려고 합니다. 우리는 이 문제에 대한 최근 제안된 이론적 솔루션(Budish, 2009)을 컴퓨터적으로 구현하는 방법을 조사합니다. 이 솔루션은 효율성, 공정성 및 인센티브 개념의 균형을 맞추기 위해 근사 경쟁 균형을 사용합니다. 잘 알려진 조합 경매 문제와의 명백한 유사성에도 불구하고, 우리는 다항 크기의 혼합 정수 프로그램(MIP)이 우리 문제를 해결할 수 없음을 보여줍니다. 대신, 우리는 두 단계 검색 프로세스를 개발합니다: 마스터 단계에서 중심은 두 개의 서로 다른 이웃의 합집합에 대해 타부 검색을 사용하여 가격을 제안합니다; 에이전트 단계에서는 MIP를 사용하여 현재 가격에서 학생 수요를 병렬로 해결합니다. 우리의 방법은 사용된 프로세서 수에 대해 거의 최적적으로 확장되며, 현실적인 크기의 문제를 충분히 빠르게 해결하여 실제로 사용할 수 있게 됩니다.
Othman et al. (Mon,)은 이 문제를 연구했습니다.