학교 교직원의 작업 부하 (시간, 교수로드 등)에 자동으로 부합하는 전문가 시스템을 개발하고 특정 부서장이 원하는대로 클래스 섹션, 최소 90 % 정확도의 공간을 생성 할 계획입니다. 특정 학기 일정을 지정합니다.Dynamic Scheduling System에 사용할 알고리즘은 무엇입니까?
어떤 알고리즘을 사용해야합니까? 발견 적? 최적화? 어떤 제안이나 도움을 주시면 감사하겠습니다!
두 명의 친구가 수업 프로젝트와 비슷한 것을 만들었습니다. 그들은 simulated annealing 휴리스틱을 사용했습니다. 그들은 그것이 그 일에 가장 좋은 도구가 아닐 수도 있다고 결론 지었다.
안녕하세요, 무엇을 알고 이 아니라면이 유용 할 수 있습니다. 맞습니까? :)
그래서 그들은 수업 프로젝트에 실패 했습니까? : P –
아마도 그들은 그것을 올바르게 구현하지 않았을 것입니다. Drools Planner에서 2 개의 릴리스가 필요했습니다. 그러나 당신이 그것을 올바르게 얻었을 때 ... 유전 알고리즘, 금기 검색 등을 물 밖으로 날려 버릴 수 있습니다. 내 벤치 마크는 http://blog.athico.com/2010/07/simulated-annealing-new-algorithm-for에서 확인하십시오.html –
거기에있는 결과를 상호 연결하십시오. 어쩌면 그들의 경우가 테스트 케이스보다 복잡했을 수도 있습니다. 그들은 실제 야간 시간표, 수업 일정, 강좌, 교사, 강좌 등에서 야심 차게 이것을 시도했습니다 ... "X는 월요일에 수업을 할 수 없습니다", "학생들은 한 시간 이상을 보내면 안됩니다. 자유 시간의 연속 ". 쉽게 구현되지만, 검색 공간이 너무 제한되어 좋은 솔루션을 찾기가 어려울 수 있습니다. – Thomas
유전 알고리즘을 사용하는 동적 스케줄링에 대해서는 a paper입니다. 여기에 유용한 아이디어가 있습니다. 도메인이 동일하지 않더라도 아이디어가 더 일반적으로 적용될 수 있습니다.
이미 확인해 주셨습니다. 어쨌든 고마워요. 나는 그것이 도움이되지 않는다고 생각한다. –
여기에 몇 가지 일반적인 관측입니다 :
1) 수동 일정은 거의 처음부터 시도하지 않습니다. 대신, 전년도의 일정으로 시작하여 요구 사항의 변화를 고려하여 변경합니다. 컴퓨터로이를 모방하는 한 가지 방법은 지금까지 솔루션을 개선하기 위해 여러 가지 작은 변경을 반복적으로 시도하는 등산 알고리즘을 사용하는 것입니다. 그러면 현재 일정에서 시작할 수 있습니다.
2) 수동 프로세스가 요구 사항이 집합 적으로 달성 불가능하고 일부를 삭제해야한다는 결론과 함께 종료됩니까? 이 경우 알고리즘은 투명성이 있어야만 실패를 이해할 수 있거나 적어도 그러한 변경을 제안 할 수 있어야합니다 (예 : 페널티 기능을 최대화하여 원래의 모든 제약 조건을 충족시키지 않는 "최악의 솔루션"을 생성 할 수 있어야합니다). 제약 기반 시스템의 오류로 인해 충분한 사용자 피드백이 제공되지 않아 정교한 제약 기반 방식이 훨씬 간단한 알고리즘으로 대체 된 사례가 있습니다.
3) 충분히 흥미롭게도 차세대 시스템은 정교한 스케줄링을 전혀 사용하지 않았습니다. 대략적으로 말하자면, 결정은 정교한 스케줄링 결정의 결과의 전부가 포기 될 수는 없으며, 장기적으로 무기한 유지 될 수있는 간단한 예측 가능한 스케줄은 생산성보다 더 컸다. 작은 순간 이점을 얻기 위해 끊임없이 일정을 재 배열합니다.
Drools Planner의 예 (curriculum course lesson scheduling) (오픈 소스, java)를보십시오. simulated annealing 및 tabu search과 같은 메타 휴리스틱 스를 사용합니다.
동적 스케줄링 알고리즘이 필요합니다. –
이것은 약간 현지화되어 있으며 현재 양식으로 대답 할 수 없습니다. –
헨크 : 해당 알고리즘에 대한 링크 또는 참조? –