교사 시간 일정 알고리즘

Question

이것은 내가 오랫동안 내 마음에 가졌던 문제입니다. 교사이자 프로그래머의 아들이기 때문에 일찍 나에게 일어 났지만 여전히 해결책을 찾지 못했습니다.

이것이 문제입니다. 일부 제약을 사용하여 학교의 시간 일정을 만들어야합니다. 이들은 일반적으로 두 가지 범주로 나뉩니다.

정신 점검

• 교사는 동시에 두 수업을 가르 칠 수 없습니다.
• 학생은 동시에 두 수업을 따를 수 없습니다.
• 일부 교사는 일주일 동안 하루를 쉬어야합니다.
• 요일은 시간 테이블로 덮여 있어야합니다.
• 주제 X는 매주 정확히 시간이 있어야합니다
• ...

선호도

• 각 교사의 일정은 가능한 한 컴팩트해야합니다 (예 : 교사는 하루 종일 일시 중지없이 일시 정지없이 일해야합니다).
• 쉬는 날이있는 교사는 어느 날 선호도를 표현할 수 있어야합니다.
• 파트 타임으로 일하는 교사는 수업 일의 시작 또는 끝에 일할 것인지에 대한 선호도를 표현할 수 있어야합니다.
• ...

이제 몇 년 동안 해결책을 찾지 못하고 (그 동안 한두 가지를 배우고 ...), 나는 이것이 NP- 하드 문제처럼 냄새가 나는 것을 깨달았습니다.

NP-HARD로 입증 되었습니까?

누구 든지이 일을 깨는 방법에 대한 아이디어가 있습니까?

보고 있습니다 이것 질문으로 인해이 문제에 대해 생각 하고이 경우 유전자 알고리즘을 사용할 수 있는지 여부는 생각해 냈습니다. 그러나 Wanity Check 규칙을 유지하면서 가능성을 돌연변이하는 것은 매우 어려울 것입니다. 또한 호환되지 않는 요구 사항을 구별하는 방법은 명확하지 않습니다.

---

문제를 더 잘 지정하기위한 작은 부록. 이것은 모든 학생들이 다른 수업 (예 : 1 학년 섹션 a)과 관련이 있고 교사는 수업 사이를 이동하는 이탈리아 학교 스타일의 교실에 적용됩니다. 같은 수업의 모든 학생들은 같은 일정을 가지고 있으며 어떤 교훈을 참석할 수있는 선택이 없습니다.

Answer 1

저는 학생 정보 시스템의 스케줄러 부분에서 일하는 개발자 중 하나입니다. 스케줄링 문제의 원래 접근 방식에서, 우리는 제약 만족도 문제를 해결하기 위해 유전자 알고리즘을 연구했으며, 처음에는 성공했지만 문제에 대한 복잡한 해결책이 있음을 깨달았습니다 (학교 일정 워크샵에 참석 한 후).

우리의 현재 구현은 훌륭하게 작동하며 Smart Heuristics와 함께 Brute Force를 사용하여 짧은 시간 안에 유효한 일정을 얻습니다. 마스터 일정 (교사에게 수업 할당)은 먼저 구축되었으며, 각 교사가 가지고있는 모든 제약을 고려하면서 학생들과의 갈등 가능성을 최소화합니다 (과정 요청에 따라). 그런 다음 학생들은 동일한 방법을 사용하여 수업에서 예약됩니다.

이렇게하면 기계에 먼저 마스터 일정을 빌드 한 다음 필요한 경우 사람을 조정할 수 있습니다.

스케줄러 현재 구현은 PERL로 작성되었지만 초기에 방문한 다른 옵션은 Prolog and Clips (Expert System)입니다.

Answer 2

이것은 매핑 문제입니다. 일주일에 매 시간마다 매핑하고 모든 교사에게 활동을해야합니다 (특정 수업 또는 무료 시간에 가르칩니다).

문제 나누기 :

1. 교사, 수업 및 선호도 목록을 만들고 사용자가 맵에서 선호도 중 일부를 출발점으로 채울 수 있습니다.
2. 목록에서 하나의 요소를 무작위로 가져 와서 목록이 비어있을 때까지 정신 점검을 통과하지 않으면지도에서 임의의 자유 위치에 놓습니다. 특정 반복에서 정신적 검사를 건너지 않고도 맵에 요소를 배치 할 수없는 경우지도에서 두 위치를 이동하고 다시 시도하십시오.
3. 맵이 채워지면 맵에서 위치를 이동하여 결과를 최적화하십시오.

2 단계와 3 단계에서 각 반복을 사용자에게 표시합니다. 목록에 남은 항목,지도의 위치 및 다음 계산 된 이동 및 사용자가 개입하도록합니다.

나는 이것을 시도하지 않았지만 이것은 나의 초기 접근법 일 것이다.

Answer 3

나는 과거에 비슷한 계획/일정 문제를 해결했으며,이 클래스의 문제에 가장 적합한 AI 기술은 "제약 기반 추론"입니다.

기본적으로 Laurenty가 제안한 것처럼 무차별적인 힘이지만,이 접근법은 효율적인 순서로 제약 조건을 적용하여 불가분의 솔루션이 빠르게 실패하여 필요한 계산을 최소화하는 것입니다.

인터넷 검색 "제약 기반 추론"은 기술과 스케줄링 문제에 대한 적용에 대한 많은 리소스를 제공합니다.

Answer 4

내 자신의 질문에 대답 :

GNUD가 언급 한 FET 프로젝트는이 알고리즘을 사용합니다.

알고리즘에 대한 일부 단어 : FET는 휴리스틱 알고리즘을 사용하여 가장 어려운 것부터 시작하여 활동을 차례로 배치합니다. 해결책을 찾을 수없는 경우 잠재적 인 불가능한 활동을 가리키므로 오류를 수정할 수 있습니다. 이 알고리즘은 새로운 활동을위한 공간을 만들기 위해 가능하다면, 또는 극단적 인 경우, 배경 및 스위치 평가 순서를 만들기 위해 활동적으로 활동적으로 교환합니다. 중요한 코드는 SRC/Engine/Generate.cpp입니다. 자세한 내용은 저에게 이메일을 보내거나 메일 링리스트에 가입하십시오. 알고리즘은 인적 시간표의 작동을 모방한다고 생각합니다.

링크

---

Wikipedia의 엄격한 소프트웨어에 의한 "제약 기반 추론"을 이어 이것들 페이지 흥미로운 단락이 있습니다.

유한 도메인에서 제약 만족도 문제를 해결하는 것은 일반적으로 NP- 완료 문제입니다. 연구 결과에 따르면 많은 다항식 시간 서브 케이스가 나타 났으며, 대부분 허용 도메인 또는 제약 조건을 제한하거나 제약 조건을 변수에 배치 할 수 있습니다. 연구는 또한 유한 모델 이론 및 데이터베이스와 같은 다른 영역의 문제와 제약 조건 만족도 문제의 관계를 확립했습니다.

Answer 5

이것은 이것을 생각 나게합니다 회의 일정에 대한 블로그 게시물, a 비디오 설명.

내가 어떻게 할 것인가 :

인구에 두 가지가 포함되어 있습니다.

• 누가 어떤 수업을 가르칩니다 (교사가 한 주제를 가르 칠 것으로 기대합니다).
• 클래스가 특정 시간 슬롯을 취하는 것.

이런 식으로 우리는 갈등을 가질 수 없습니다 (두 곳의 교사 또는 동시에 두 명의 주제를 가진 수업).

피트니스 기능에는 다음이 포함됩니다.

• 각 교사가 일주일에 몇 개의 시간 슬롯을 제공합니다.
• 선생님이 같은 날에 몇 개의 시간 슬롯이 있었는지
• 같은 날에 동일한 주제의 시간 슬롯이 몇 일에 있었는지 (그들은 하루 종일 수학을 가질 수 없습니다!)

균형을 잡아야하므로 모든 표준 편차를 사용해야합니다.

Answer 6

이것이 같은 근거를 다루는지 확실하지 않습니다. @Stringent 소프트웨어 대답 (이름이 약간 다르기 때문에)이지만 영역을 조사하는 아주 좋은 친구가 있습니다. 제약 프로그래밍. 시간표를 만드는 것은 연구를 적용하는 것 중 하나입니다.

Chris Jefferson 박사 라는 프로그램을 만들었습니다 미니언 Sourceforge에서 다운로드 할 수 있고 C ++로 작성된 매우 빠른 무차별 인력 구속 문제 솔버입니다.

Answer 7

나는 당신이 약간의 제약을 놓치고 있다고 생각합니다.

가능한 경우 교사가 인증을받은 수업에 예약 할 수 있도록 선호합니다.

요청 된 클래스와 각각의 예상 헤드 수가 중요하다고 의심 할 것입니다.

시작해야 할 곳은 모든 제약을 나열하고이를 나타내는 데이터 구조를 알아내는 것이라고 생각합니다.

그런 다음 시험 솔루션을 구축하는 엔진을 만들고 제약 조건에 따라 체력을 평가합니다.

그런 다음 재미있는 유전자 알고리즘을 던져서 유전자가 혼합 될 때 시간이 지남에 따라 체력을 얻을 수 있는지 확인할 수 있습니다.

작은 제약 세트로 시작하여 성공을 볼 때 증가시킵니다 (성공을 보면).

제약 조건을 취하고 선형 프로그래밍 알고리즘과 같은 것과 함께 구속 할 수있는 방법이있을 수 있습니다.

동의한다. 재미있는 도전처럼 들립니다

Answer 8

최악의 오픈 소스 웹 페이지 중 하나이지만 프로젝트는 유망한 것 같습니다.http://www.lalescu.ro/liviu/fet/

웹 기반 aproach :
phpscheduleit (학교 별 아님)

Answer 9

이 질문을 살펴보면이 문제에 대해 생각 하고이 경우 유전자 알고리즘을 사용할 수 있는지 여부는 생각해 냈습니다. 그러나 Wanity Check 규칙을 유지하면서 가능성을 돌연변이하는 것은 매우 어려울 것입니다. 또한 호환되지 않는 요구 사항을 구별하는 방법은 명확하지 않습니다.

유전자 알고리즘은 이와 같은 문제에 매우 적합합니다. 일단 염색체의 적절한 표현을 생각해 내면 (이 경우, 아마도 사용 가능한 모든 클래스 슬롯을 나타내는 벡터) 당신은 대부분의 길입니다.

돌연변이 단계에서 정신 검사를 유지하는 것에 대해 걱정하지 마십시오. 돌연변이는 무작위입니다. 세력과 선호 점검은 둘 다 선택 단계에 속합니다. 실패한 정신 점검은 개인의 체력을 크게 낮추는 반면, 선호도 실패는 체력을 약간 낮게 낮추게됩니다.

양립 할 수없는 요구 사항은 모두 다른 문제입니다. 그것들이 완전히 호환되지 않으면 유용한 것에 수렴하지 않는 인구를 얻을 수 있습니다.

Answer 10

행운을 빕니다. 이런 종류의 문제를 가진 아버지의 아들이 되기는 것이 내가 끝난 연구 그룹에 나를 데려갔습니다 ...

---

내가 어렸을 때 아버지는 지역 스포츠 리그에서 경기 공무원을 예약했을 때, 이것은 비슷하게 긴 제약 조건을 가졌으며 도움을 줄 무언가를 쓰려고 노력했습니다. 내가 대학에 도착했을 때 나는 심지어 마지막 해 프로젝트가 결국 Monte Carlo 구현 (시뮬레이션 어닐링 모델 사용)에 정착 한 것으로 사용했습니다.

기본 아이디어는 NP가 아니라면 꽤 가깝기 때문에 해결책이 있다고 가정하기보다는 주어진 시간 내에 최고를 찾기 시작했다는 것입니다. 나는 모든 제약 조건을 파괴 비용으로 가중시킬 것입니다. 정신 점검은 막대한 비용을 가질 것이고, 선호도는 비용이 낮아질 것입니다 (그러나 더 많은 휴식의 경우 증가하므로 한 번 파괴하는 것은 두 번 끊는 데 드는 비용의 절반 미만입니다).

기본 아이디어는 '무작위'솔루션으로 시작하여 비용이 들었다는 것입니다. 그런 다음 적은 수의 과제를 교환하여 변경 한 다음 다시 평가 한 다음 변경 사항을 수락하거나 거부했습니다.

수천 개의 반복 후에는 허용되는 솔루션에 더 가깝습니다.

그러나이 클래스의 문제에는 박사 학위를 취득한 연구 그룹이있어서 당신이 아주 좋은 회사에 있습니다.

선형 프로그래밍 분야에 관심을 찾을 수도 있습니다. 단순성 등등.

Answer 11

그렇습니다. 이것이 NP 완료라고 생각합니다. 또는 최소한 최적의 솔루션이 NP가 완료된 것으로 생각합니다.

나는 친구의 아버지 (선생님이자)에게 적절한 프로그램을 찾지 못하면 그의 일정 문제를 해결할 수 있다고 말하면서 대학에서 비슷한 문제를 일으켰습니다 (1990 년에 돌아 왔습니다).

나는 내가 무엇을 얻었는지 전혀 몰랐다. 운 좋게도 내가해야 할 일은 제약 조건에 맞는 하나의 솔루션을 찾는 것이 었습니다. 그러나 테스트에서 나는 항상 해결책이 있는지 여부를 결정하는 것에 대해 항상 걱정했습니다. 그는 너무 많은 제약을 가지고 있지 않았으며 프로그램은 다른 휴리스틱과 백 추적을 사용했습니다. 정말 재미있었습니다.

Bill Gates는 고등학교 나 대학에서 고등학교 대학에서 이와 같은 시스템에서 일했다고 생각합니다. 그래도 확실하지 않습니다.

행운을 빕니다. 내 모든 메모가 사라지고 나는 내가 마케팅 할 수있는 솔루션을 구현하지 않았습니다. 새로운 언어를 배웠을 때 다시 코딩 한 전문 프로젝트였습니다 (Basic, Stand, C, VB, C ++)

그것으로 재미있게 보내십시오

Answer 12

이 문제는 데이터베이스에 연결하여 Prolog 프로그램에 의해 해결 될 수 있으며 프로그램은 ABT "제한 만족도 문제 Prolog"을 읽는 일련의 제약 조건을 주어 주면 일정을 만들 수 있습니다.