[algorithm] 학교 시간표를 만드는 알고리즘

Program / 글쓴이

학교 시간표를 만드는 알고리즘에 대해 알려진 솔루션이 있는지 궁금합니다. 기본적으로 주어진 수업-주제-교사 연관성에 대해 “시간 분산”(교사 및 수업의 경우 모두)을 최적화하는 것입니다. 입력시 서로 연관된 수업, 수업 주제 및 교사 세트가 있으며 시간표는 오전 8시에서 오후 4시 사이에 맞아야한다고 가정 할 수 있습니다.

아마도 정확한 알고리즘은 없을 것 같지만 누군가가 그것을 개발하기위한 좋은 근사치 나 힌트를 알고있을 것입니다.

답변

이 문제는 NP-Complete입니다 !
요컨대 허용 가능한 솔루션 목록을 찾기 위해 가능한 모든 조합을 탐색해야합니다. 여러 학교에서 문제가 나타나는 상황의 차이로 인해 (예 : 교실과 관련하여 제약이 있습니까?, 일부 수업이 때때로 하위 그룹으로 나뉘어 있습니까?, 이것이 주간 일정입니까? 등) 모든 스케줄링 문제에 해당하는 잘 알려진 문제 클래스가 없습니다. 아마도 Knapsack 문제 는 이러한 문제들과 유사한 많은 요소를 가지고있을 것입니다.

이것이 어려운 문제이며 사람들이 해법을 계속 찾는다는 확인 은 (대부분 상업적인) 소프트웨어 스케줄링 도구의 ( 긴) 목록 을 확인 하는 것입니다.

일반적으로 교수진의 욕구가 가장 큰 원인 인 변수가 많기 때문에 가능한 모든 조합을 열거 하는 것은 일반적으로 비현실적 입니다. 대신 문제 / 솔루션 공간의 하위 집합을 방문하는 접근 방식을 선택해야합니다.
– 유전자 알고리즘 다른 답변에서 인용은, (또는, IMHO, 보인다 아니라 반 가이드 검색 이런 종류의 (문제는 후보가 다음 세대를 위해 유지하는 좋은 평가 기능을 찾을 수있는)을 수행하기 위해 장착)
– 그래프 재 작성 접근법은 이러한 유형의 조합 최적화 문제에도 사용됩니다.

자동 일정 생성 프로그램의 특정 구현에 초점을 맞추기보다는 문제 정의 수준에서 적용 할 수있는 몇 가지 전략 을 제안하고 싶습니다 .
일반적인 이론적 근거는 대부분의 실제 스케줄링 문제에서 일부 타협이 필요하며 모든 제약이 명시되고 묵시적인 것이 아니라 완전히 충족된다는 것입니다. 따라서 우리는 다음을 통해 스스로를 돕습니다.

  • 알려진 모든 제약 조건 정의 및 순위 지정
  • 추가 제약 조건을 제공하여 수동으로 문제 공간을 줄 입니다.
    이것은 직관적이지 않은 것처럼 보일 수 있지만 예를 들어 모든 제약 조건을 완전히 충족하는 방식으로 초기 부분적으로 채워진 일정 (예 : 시간 슬롯의 약 30 %)을 제공하고이 부분 일정을 변경할 수없는 것으로 간주하여 후보 솔루션을 생성하는 데 필요한 시간 / 공간.
    추가 제약이 도움이되는 또 다른 방법은 예를 들어 “인공적으로”제약을 추가하여 특정 요일에 일부 과목을 가르치는 것을 방지하는 것입니다 (주간 일정 인 경우 …); 이러한 유형의 제약은 일반적으로 상당한 수의 좋은 후보를 제외하지 않고 문제 / 해결 방법 공간을 줄입니다.
  • 문제의 일부 제약 조건을 신속하게 계산할 수 있도록합니다. 이것은 종종 문제를 나타내는 데 사용되는 데이터 모델의 선택과 관련이 있습니다. 아이디어는 일부 옵션을 신속하게 선택 (또는 제거) 할 수있는 것입니다.
  • 문제를 재정의하고 제약 조건 중 일부가 몇 번 (일반적으로 그래프의 끝 노드쪽으로) 깨지도록 허용합니다. 생각이 여기에 있습니다 중 하나를 제거 일부 충전 된 지난 몇 슬롯 일정에 대한 제약을, 또는 자동 일정 생성 프로그램 정지 대신 다스 정도의 그럴듯한의 목록을 우리에게 제공, 전체 일정을 완료의 부끄러워해야 할 후보자. 일반적으로 자동화 된 논리와 공유되지 않는 정보 (예 : “오후에 수학 없음”규칙은 때때로 위반 될 수 있음)를 사용하여 지시 된대로 퍼즐을 완료하는 데 더 나은 위치에있는 경우가 많습니다. “고급 수학 및 물리학”수업의 경우, 또는 “Ms Smith 중 하나보다 Mr Jones 요구 사항 중 하나를 위반하는 것이 낫습니다 … ;-))

이 답변을 교정하면서 확실한 답변을 제공하는 것이 매우 부끄럽지만 실용적인 제안으로 가득 차 있지는 않습니다. 결국 “어려운 문제”인이 도움이되기를 바랍니다.

답변

엉망입니다. 왕실 혼란. 이미 매우 완전한 답변을 추가하기 위해 가족 경험을 지적하고 싶습니다. 어머니는 선생님 이셨고 그 과정에 참여하셨습니다.

그렇게 할 수있는 컴퓨터를 갖는 것은 그 자체로 코딩하기 어려울뿐만 아니라 미리 구운 컴퓨터 프로그램에 지정하기 어려운 조건이 있기 때문에 어렵습니다. 예 :

  • 교사는 학교와 다른 기관에서 가르칩니다. 분명히 그가 10시 30 분에 레슨을 마치면 10시 30 분에 당신의 집에서 시작할 수 없습니다. 왜냐하면 그는 연구소 사이를 오가는 데 시간이 필요하기 때문입니다.
  • 두 명의 교사가 결혼했습니다. 일반적으로 같은 반에 두 명의 기혼 교사를 두지 않는 것이 좋습니다. 따라서이 두 교사는 두 개의 다른 클래스를 가지고 있어야합니다.
  • 두 명의 교사가 결혼했고 자녀는 같은 학교에 다니고 있습니다. 다시 말하지만, 두 교사가 자녀가있는 특정 수업에서 가르치는 것을 막아야합니다.
  • 학교에는 별도의 시설이 있습니다. 예를 들어 어느 날 수업은 한 기관에 있고 다른 날에는 다른 수업이 있습니다.
  • 학교에는 공동 실험실이 있지만 이러한 실험실은 특정 평일에만 이용할 수 있습니다 (예 : 추가 인력이 필요한 경우 보안상의 이유로).
  • 어떤 교사는 자유 일을 선호합니다. 어떤 교사는 월요일, 어떤 교사는 금요일, 어떤 교사는 수요일을 선호합니다. 일부는 아침 일찍 오는 것을 선호하고 일부는 늦게 오는 것을 선호합니다.
  • 첫 시간에 역사, 그다음에 수학 3 시간, 그리고 또 다른 시간에 역사에 대한 교훈이있는 상황이 있어서는 안됩니다. 학생이나 교사에게는 이치에 맞지 않습니다.
  • 논쟁을 균등하게 퍼뜨려 야합니다. 일주일의 첫날은 수학 만하고 나머지는 문학 만하는 것은 의미가 없습니다.
  • 일부 교사에게 평가 테스트를 위해 연속 2 시간을 주어야합니다.

보시다시피 문제는 NP- 완전한 것이 아니라 NP- 미친 것입니다.

그래서 그들이하는 일은 작은 플라스틱 삽입물이있는 큰 테이블을 가지고 있고 만족스러운 결과를 얻을 때까지 삽입물을 움직입니다. 그들은 처음부터 시작하지 않습니다. 일반적으로 전년도 시간표에서 시작하여 조정합니다.

답변

국제 Timetabling 경쟁 2007 년 수업 일정 트랙과 시험 일정을 추적했다. 많은 연구자들이 그 대회에 참가했습니다. 많은 휴리스틱과 메타 휴리스틱이 시도되었지만 결국에는 로컬 검색 메타 휴리스틱 (예 : Tabu Search 및 Simulated Annealing)이 다른 알고리즘 (예 : 유전 알고리즘)을 분명히 능가했습니다.

일부 결선 진출자가 사용하는 2 개의 오픈 소스 프레임 워크를 살펴보십시오.

답변

반기 과제 중 하나는 유전 알고리즘 학교 테이블 생성이었습니다.

전체 테이블은 하나의 “유기체”입니다. 일반 유전 알고리즘 접근 방식에 몇 가지 변경 사항과주의 사항이 있습니다.

  • “불법 테이블”에 대한 규칙이 만들어졌습니다. 같은 교실에있는 두 개의 수업, 동시에 두 그룹을 가르치는 한 명의 교사 등등. 이러한 돌연변이는 즉시 치명적이라고 간주되어 즉시 “죽은”대신 새로운 “유기체”가 싹트게되었습니다. 최초의 것은 합법적 (무의미한 경우)을 얻기위한 일련의 무작위 시도에 의해 생성되었습니다. 치명적인 돌연변이는 반복의 돌연변이 수에 포함되지 않았습니다.

  • “교환”돌연변이는 “수정”돌연변이보다 훨씬 더 일반적이었습니다. 변화는 의미가있는 유전자 부분 사이에서만 이루어졌으며 교사를 교실로 대체하지 않았습니다.

  • 교사의 업무 시간과 수업 부하를 지속적으로 유지하기 위해 동일한 그룹에 대해 동일한 일반 교실을 순서대로 할당하기 위해 특정 2 시간을 함께 묶는 데 작은 보너스가 할당되었습니다. 주어진 과목에 대해 올바른 교실을 제공하고 수업 시간을 유대 (오전 또는 오후) 내에 유지하는 등 적당한 보너스가 할당되었습니다. 큰 보너스는 주어진 과목의 정확한 수를 할당하고 교사에게 주어진 작업량 등이었습니다.

  • 교사는 적절한 가중치를 할당하여 “그때 일하고 싶다”, “그때 일해도 괜찮다”, “그때 일하기 싫어”, “그때 일할 수 없음”등의 작업량 일정을 만들 수 있습니다. 밤 시간이 매우 바람직하지 않은 것을 제외하고는 24 시간 내내 합법적 인 근무 시간이었습니다.

  • 무게 함수 … 오 예. 가중치 함수는 선택한 기능 및 속성에 할당 된 가중치의 거대하고 괴물 같은 곱 (곱셈에서와 같이)이었습니다. 그것은 극도로 가파르고, 하나의 속성이 쉽게 위아래로 몇 배나 위아래로 바꿀 수 있었고, 한 유기체에는 수백 또는 수천 개의 속성이있었습니다. 이로 인해 가중치가 절대적으로 큰 숫자가되었고 직접적인 결과로 계산을 수행하기 위해 bignum 라이브러리 (gmp)를 사용해야합니다. 10 개 그룹, 10 명의 교사, 10 개의 교실로 구성된 소규모 테스트 케이스의 경우 초기 세트는 10 ^ -200something으로 시작하여 10 ^ + 300something으로 끝났습니다. 더 평평했을 때는 완전히 비효율적이었습니다. 또한 가치는 더 큰 “학교”와 함께 훨씬 더 넓어졌습니다.

  • 계산 시간을 고려할 때, 오랜 기간 동안 소규모 인구 (100 명)와 적은 세대 동안 대규모 인구 (10k +) 사이에는 거의 차이가 없었습니다. 동일한 시간에 걸친 계산은 거의 동일한 품질을 생성했습니다.

  • 계산 (일부 1GHz CPU에서)은 10 ^ + 300 근처에서 안정화되는 데 약 1 시간이 걸리며, 10x10x10 테스트 케이스에 대해 꽤 좋은 일정을 생성합니다.

  • 계산을 실행하는 컴퓨터간에 최상의 표본을 교환 할 수있는 네트워킹 기능을 제공하여 문제를 쉽게 병렬화 할 수 있습니다.

그 결과 프로그램은 한 학기에 좋은 성적을 얻도록 밖에서 일광을 보지 못했습니다. 그것은 약간의 약속을 보여 주었지만 GUI를 추가하고 일반 대중에게 사용할 수 있도록 충분한 동기를 얻지 못했습니다.

답변

이 문제는 생각보다 어렵습니다.

다른 사람들이 언급했듯이 이것은 NP- 완전한 문제이지만 그 의미를 분석해 봅시다.

기본적으로 가능한 모든 조합을 살펴 봐야합니다.

그러나 “봐”는 당신이해야 할 일을 많이 말해주지 않습니다.

가능한 모든 조합을 생성하는 것은 쉽습니다. 엄청난 양의 데이터를 생성 할 수 있지만 문제의이 부분에 대한 개념을 이해하는 데 많은 문제가 없어야합니다.

두 번째 문제는 주어진 가능한 조합이 이전의 “좋은”솔루션보다 좋은지, 나쁜지 또는 더 나은지를 판단하는 것입니다.

이를 위해서는 “가능한 해결책”이상이 필요합니다.

예를 들어, 같은 선생님이 X 주 동안 일주일에 5 일씩 일하고 있습니까? 그것이 작동하는 해결책이라고하더라도 두 사람을 번갈아 가며 각 교사가 한 주에 한 번씩하는 것보다 나은 해결책은 아닐 수 있습니다. 오, 그것에 대해 생각하지 않았나요? 이것은 단지 자원 할당 문제가 아니라 당신이 다루는 사람들이라는 것을 기억하십시오.

한 명의 교사가 16 주 동안 풀 타임으로 일할 수 있다고해도 교사를 번갈아 가며 시도하는 솔루션에 비해 차선책 일 수 있으며 이러한 종류의 균형을 소프트웨어에 구축하는 것은 매우 어렵습니다.

요약하면,이 문제에 대한 좋은 해결책을 만드는 것은 많은 사람들에게 많은 가치가있을 것입니다. 따라서 분해하고 해결하는 것은 쉬운 문제가 아닙니다. 100 %가 아닌 몇 가지 목표를 파악하고 “충분히 좋다”고 말할 준비를하십시오.

답변

FET (Free Timetabling Software, http://lalescu.ro/liviu/fet/ , 성공적인 응용 프로그램) 에서 구현 된 내 시간표 알고리즘 :

알고리즘은 휴리스틱입니다. 나는 그것을 “재귀 스와핑”이라고 명명했습니다.

입력 : 일련의 활동 A_1 … A_n 및 제약.

출력 : TA_1 … TA_n 시간 세트 (각 활동의 시간 슬롯. 단순성을 위해 여기서 룸은 제외됨). 알고리즘은 제약 조건을 준수하면서 각 활동을 시간 슬롯에 배치해야합니다. 각 TA_i는 0 (T_1)과 max_time_slots-1 (T_m) 사이입니다.

제약 :

C1) 기본 : 동시에 할 수없는 활동 쌍의 목록 (예 : A_1 및 A_2, 동일한 교사 또는 동일한 학생이 있기 때문에)

C2) 기타 많은 제약 (간단 함을 위해 여기에서 제외됨).

시간표 알고리즘 ( “재귀 스와핑”이라고 명명) :

  1. 가장 어려운 활동부터 정렬합니다. 중요한 단계는 아니지만 알고리즘 속도를 10 배 이상 높일 수 있습니다.

  2. 위의 순서에 따라 한 번에 하나씩 허용 된 시간 슬롯에 각 활동 (A_i)을 배치하십시오. A_i에 대해 사용 가능한 슬롯 (T_j)을 검색합니다.이 활동은 제약 조건에 따라 배치 될 수 있습니다. 더 많은 슬롯을 사용할 수있는 경우 무작위로 선택합니다. 사용할 수없는 경우 재귀 스와핑을 수행하십시오.

    a . 각 시간 슬롯 T_j에 대해 A_i를 T_j에 넣으면 어떻게되는지 고려하십시오. 이 이동에 동의하지 않는 다른 활동 목록이있을 것입니다 (예 : 활동 A_k는 동일한 슬롯 T_j에 있고 A_i와 동일한 교사 또는 동일한 학생이 있음). 각 시간대 T_j에 대해 상충되는 활동 목록을 유지하십시오.

    b . 충돌 활동 수가 가장 적은 슬롯 (T_j)을 선택하십시오. 이 슬롯의 활동 목록에 A_p, A_q, A_r의 3 가지 활동이 포함되어 있다고 가정합니다.

    c . A_i를 T_j에 놓고 A_p, A_q, A_r을 할당 해제합니다.

    d . 재귀 적으로 A_i가 시작된 A_p, A_q, A_r (재귀 수준이 너무 크지 않은 경우 14, 2 단계 이후 계산 된 총 재귀 호출 수)가 너무 크지 않은 경우 (2 * n) 배치하려고합니다. 2 단계에서와 같이).

    e . A_p, A_q, A_r을 성공적으로 배치 한 경우 성공으로 돌아오고, 그렇지 않으면 다른 시간 슬롯을 시도하고 (2 단계 b로 이동) 다음 최적의 시간 슬롯을 선택합니다.

    f . 모든 (또는 합리적인 수의) 시간 슬롯이 성공적으로 시도되지 않은 경우 성공하지 않고 반환합니다.

    g . 레벨 0이고 A_i 배치에 성공하지 못한 경우 2b) 및 2c) 단계와 같이 배치하지만 재귀는 없습니다. 이제 3-1 = 2 개의 활동을 더 배치 할 수 있습니다. 2 단계로 이동) (여기에서는 사이클링을 피하는 몇 가지 방법이 사용됩니다).

답변

업데이트 : 의견에서 …도 휴리스틱이 있어야합니다!

나는 Prolog와 함께 갈 것입니다 … 그런 다음 Ruby 또는 Perl 또는 무언가를 사용하여 솔루션을 더 예쁜 형태로 정리하십시오.

teaches(Jill,math).
teaches(Joe,history).

involves(MA101,math).
involves(SS104,history).

myHeuristic(D,A,B) :- [test_case]->D='<';D='>'.
createSchedule :- findall(Class,involves(Class,Subject),Classes),
                  predsort(myHeuristic,Classes,ClassesNew),
                  createSchedule(ClassesNew,[]).
createSchedule(Classes,Scheduled) :- [the actual recursive algorithm].

나는 (여전히)이 문제와 비슷한 일을하고 있지만 방금 언급 한 것과 동일한 경로를 사용하고 있습니다. Prolog (기능적 언어)는 실제로 NP-Hard 문제를 더 쉽게 해결합니다.