학교 시간표를 만드는 알고리즘
학교 시간표를 만드는 알고리즘에 대해 알려진 솔루션이 있는지 궁금합니다. 기본적으로 주어진 수업-주제-교사 연관성에 대해 "시간 분산"(교사 및 수업의 경우 모두)을 최적화하는 것입니다. 입력시 서로 연관된 수업, 수업 주제 및 교사 세트가 있으며 시간표는 오전 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 개의 오픈 소스 프레임 워크를 살펴보십시오.
- JBoss OptaPlanner (Java, 오픈 소스)
- Unitime (Java, 오픈 소스)-대학을위한 추가 정보
반기 과제 중 하나는 유전 알고리즘 학교 테이블 생성이었습니다.
전체 테이블은 하나의 "유기체"입니다. 일반 유전 알고리즘 접근 방식에 몇 가지 변경 사항과주의 사항이 있습니다.
"불법 테이블"에 대한 규칙이 만들어졌습니다. 같은 교실에있는 두 개의 수업, 동시에 두 그룹을 가르치는 한 명의 교사 등등. 이러한 돌연변이는 즉시 치명적이라고 간주되었고 즉시 "죽은"대신 새로운 "유기체"가 싹 트었습니다. 최초의 것은 합법적 (무의미한 경우)을 얻기위한 일련의 무작위 시도에 의해 생성되었습니다. 치명적인 돌연변이는 반복의 돌연변이 수에 포함되지 않았습니다.
"교환"돌연변이는 "수정"돌연변이보다 훨씬 더 일반적이었습니다. 변화는 의미가있는 유전자 부분 사이에서만 이루어졌으며 교사를 교실로 대체하지 않았습니다.
교사의 업무 시간과 수업 부하를 지속적으로 유지하기 위해 동일한 그룹에 대해 동일한 일반 교실을 순서대로 할당하기 위해 특정 2 시간을 함께 묶는 데 작은 보너스가 할당되었습니다. 주어진 과목에 대해 올바른 교실을 제공하고 수업 시간을 유대 (오전 또는 오후) 내에 유지하는 등 적당한 보너스가 할당되었습니다. 큰 보너스는 주어진 과목의 정확한 수를 할당하고 교사에게 주어진 작업량 등이었습니다.
교사는 적절한 가중치가 할당 된 상태에서 "그때 일하고 싶다", "그때 일해도 돼", "그때 일하기 싫어", "그때 일할 수 없음"등의 작업량 일정을 만들 수 있습니다. 야간 시간이 매우 바람직하지 않은 것을 제외하고는 24 시간 내내 합법적 인 근무 시간이었습니다.
무게 함수 ... 오 예. 가중치 함수는 선택한 기능 및 속성에 할당 된 가중치의 거대하고 괴물 같은 곱 (곱셈에서와 같이)이었습니다. 그것은 극도로 가파르고, 하나의 속성이 쉽게 위아래로 몇 배나 위아래로 바꿀 수 있었고, 한 유기체에는 수백 또는 수천 개의 속성이있었습니다. 이로 인해 가중치가 절대적으로 큰 숫자가되었고 직접적인 결과로 계산을 수행하기 위해 bignum 라이브러리 (gmp)를 사용해야합니다. 10 개 그룹, 10 명의 교사, 10 개의 교실로 구성된 소규모 테스트 케이스의 경우 초기 세트는 10 ^ -200something으로 시작하여 10 ^ + 300something으로 끝났습니다. 더 평평했을 때는 완전히 비효율적이었습니다. 또한 가치는 더 큰 "학교"와 함께 훨씬 더 넓어졌습니다.
계산 시간을 고려할 때, 오랜 기간 동안 소규모 인구 (100 명)와 적은 세대 동안 대규모 인구 (10k +) 사이에는 거의 차이가 없었습니다. 동일한 시간에 걸친 계산은 거의 동일한 품질을 생성했습니다.
계산 (일부 1GHz CPU에서)은 10 ^ + 300 근처에서 안정화되는 데 약 1 시간이 걸리며, 10x10x10 테스트 케이스에 대해 꽤 좋은 일정을 생성합니다.
계산을 실행하는 컴퓨터간에 최상의 표본을 교환 할 수있는 네트워킹 기능을 제공하여 문제를 쉽게 병렬화 할 수 있습니다.
그 결과 프로그램은 한 학기 동안 좋은 성적을 얻도록 밖에서 일광을 보지 못했습니다. 그것은 약간의 약속을 보여 주었지만 GUI를 추가하고 일반 대중에게 사용할 수 있도록 충분한 동기를 얻지 못했습니다.
이 문제는 생각보다 어렵습니다.
다른 사람들이 언급했듯이 이것은 NP- 완전한 문제이지만 그 의미를 분석해 봅시다.
기본적으로 가능한 모든 조합을 살펴 봐야합니다.
그러나 "봐"는 당신이해야 할 일을 많이 말해주지 않습니다.
가능한 모든 조합을 생성하는 것은 쉽습니다. 엄청난 양의 데이터를 생성 할 수 있지만 문제의이 부분에 대한 개념을 이해하는 데 많은 문제가 없어야합니다.
두 번째 문제는 주어진 가능한 조합이 이전의 "좋은"솔루션보다 좋은지, 나쁜지 또는 더 나은지를 판단하는 것입니다.
이를 위해서는 "가능한 해결책"이상이 필요합니다.
For instance, is the same teacher working 5 days a week for X weeks straight? Even if that is a working solution, it might not be a better solution than alternating between two people so that each teacher does one week each. Oh, you didn't think about that? Remember, this is people you're dealing with, not just a resource allocation problem.
Even if one teacher could work full-time for 16 weeks straight, that might be a sub-optimal solution compared to a solution where you try to alternate between teachers, and this kind of balancing is very hard to build into software.
To summarize, producing a good solution to this problem will be worth a lot, to many many people. Hence, it's not an easy problem to break down and solve. Be prepared to stake out some goals that aren't 100% and calling them "good enough".
UPDATE: from comments ... should have heuristics too!
I'd go with Prolog ... then use Ruby or Perl or something to cleanup your solution into a prettier form.
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].
I am (still) in the process of doing something similar to this problem but using the same path as I just mentioned. Prolog (as a functional language) really makes solving NP-Hard problems easier.
Genetic algorithms are often used for such scheduling.
Found this example (Making Class Schedule Using Genetic Algorithm) which matches your requirement pretty well.
Here are a few links I found:
School timetable - Lists some problems involved
A Hybrid Genetic Algorithm for School Timetabling
Scheduling Utilities and Tools
My timetabling algorithm, implemented in FET (Free Timetabling Software, http://lalescu.ro/liviu/fet/ , a successful application):
The algorithm is heuristic. I named it "recursive swapping".
Input: a set of activities A_1...A_n and the constraints.
Output: a set of times TA_1...TA_n (the time slot of each activity. Rooms are excluded here, for simplicity). The algorithm must put each activity at a time slot, respecting constraints. Each TA_i is between 0 (T_1) and max_time_slots-1 (T_m).
Constraints:
C1) Basic: a list of pairs of activities which cannot be simultaneous (for instance, A_1 and A_2, because they have the same teacher or the same students);
C2) Lots of other constraints (excluded here, for simplicity).
The timetabling algorithm (which I named "recursive swapping"):
- Sort activities, most difficult first. Not critical step, but speeds up the algorithm maybe 10 times or more.
Try to place each activity (A_i) in an allowed time slot, following the above order, one at a time. Search for an available slot (T_j) for A_i, in which this activity can be placed respecting the constraints. If more slots are available, choose a random one. If none is available, do recursive swapping:
a. For each time slot T_j, consider what happens if you put A_i into T_j. There will be a list of other activities which don't agree with this move (for instance, activity A_k is on the same slot T_j and has the same teacher or same students as A_i). Keep a list of conflicting activities for each time slot T_j.
b. Choose a slot (T_j) with lowest number of conflicting activities. Say the list of activities in this slot contains 3 activities: A_p, A_q, A_r.
c. Place A_i at T_j and make A_p, A_q, A_r unallocated.
d. Recursively try to place A_p, A_q, A_r (if the level of recursion is not too large, say 14, and if the total number of recursive calls counted since step 2) on A_i began is not too large, say 2*n), as in step 2).
e. If successfully placed A_p, A_q, A_r, return with success, otherwise try other time slots (go to step 2 b) and choose the next best time slot).
f. If all (or a reasonable number of) time slots were tried unsuccessfully, return without success.
g. If we are at level 0, and we had no success in placing A_i, place it like in steps 2 b) and 2 c), but without recursion. We have now 3 - 1 = 2 more activities to place. Go to step 2) (some methods to avoid cycling are used here).
I have designed commercial algorithms for both class timetabling and examination timetabling. For the first I used integer programming; for the second a heuristic based on maximizing an objective function by choosing slot swaps, very similar to the original manual process that had been evolved. They main things in getting such solutions accepted are the ability to represent all the real-world constraints; and for human timetablers to not be able to see ways to improve the solution. In the end the algorithmic part was quite straightforward and easy to implement compared with the preparation of the databases, the user interface, ability to report on statistics like room utilization, user education and so on.
This paper describes the school timetable problem and their approach to the algorithm pretty well: "The Development of SYLLABUS—An Interactive, Constraint-Based Scheduler for Schools and Colleges."[PDF]
The author informs me the SYLLABUS software is still being used/developed here: http://www.scientia.com/uk/
I work on a widely-used scheduling engine which does exactly this. Yes, it is NP-Complete; the best approaches seek to approximate an optimal solution. And, of course there are a lot of different ways to say which one is the "best" solution - is it more important that your teachers are happy with their schedules, or that students get into all their classes, for instance?
The absolute most important question you need to resolve early on is what makes one way of scheduling this system better than another? That is, if I have a schedule with Mrs Jones teaching Math at 8 and Mr Smith teaching Math at 9, is that better or worse than one with both of them teaching Math at 10? Is it better or worse than one with Mrs Jones teaching at 8 and Mr Jones teaching at 2? Why?
The main advice I'd give here is to divide the problem up as much as possible - maybe course by course, maybe teacher by teacher, maybe room by room - and work on solving the sub-problem first. There you should end up with multiple solutions to choose from, and need to pick one as the most likely optimal. Then, work on making the "earlier" sub-problems take into account the needs of later sub-problems in scoring their potential solutions. Then, maybe work on how to get yourself out of painted-into-the-corner situations (assuming you can't anticipate those situations in earlier sub-problems) when you get to a "no valid solutions" state.
A local-search optimization pass is often used to "polish" the end answer for better results.
Note that typically we are dealing with highly resource-constrained systems in school scheduling. Schools don't go through the year with a lot of empty rooms or teachers sitting in the lounge 75% of the day. Approaches which work best in solution-rich environments aren't necessarily applicable in school scheduling.
Generally, constraint programming is a good approach to this type of scheduling problem. A search on "constraint programming" and scheduling or "constraint based scheduling" both within stack overflow and on Google will generate some good references. It's not impossible - it's just a little hard to think about when using traditional optimization methods like linear or integer optimization. One output would be - does a schedule exist that satisfies all the requirements? That, in itself, is obviously helpful.
Good luck !
You can takle it with genetic algorithms, yes. But you shouldn't :). It can be too slow and parameter tuning can be too timeconsuming etc.
There are successful other approaches. All implemented in open source projects:
- Constraint based approach
- Implemented in UniTime (not really for schools)
- You could also go further and use Integer programming. Successfully done at Udine university and also at University Bayreuth (I was involved there) using the commercial software (ILOG CPLEX)
- Rule based approach with heuristisc - See Drools planner
- Different heuristics - FET and my own
See here for a timetabling software list
I think you should use genetic algorithm because:
- It is best suited for large problem instances.
- It yields reduced time complexity on the price of inaccurate answer(Not the ultimate best)
- You can specify constraints & preferences easily by adjusting fitness punishments for not met ones.
- You can specify time limit for program execution.
The quality of solution depends on how much time you intend to spend solving the program..
Also take a look at :a similar question and another one
I don't know any one will agree with this code but i developed this code with the help of my own algorithm and is working for me in ruby.Hope it will help them who are searching for it in the following code the periodflag ,dayflag subjectflag and the teacherflag are the hash with the corresponding id and the flag value which is Boolean. Any issue contact me.......(-_-)
periodflag.each do |k2,v2|
if(TimetableDefinition.find(k2).period.to_i != 0)
subjectflag.each do |k3,v3|
if (v3 == 0)
if(getflag_period(periodflag,k2))
@teachers=EmployeesSubject.where(subject_name: @subjects.find(k3).name, division_id: division.id).pluck(:employee_id)
@teacherlists=Employee.find(@teachers)
teacherflag=Hash[teacher_flag(@teacherlists,teacherflag,flag).to_a.shuffle]
teacherflag.each do |k4,v4|
if(v4 == 0)
if(getflag_subject(subjectflag,k3))
subjectperiod=TimetableAssign.where("timetable_definition_id = ? AND subject_id = ?",k2,k3)
if subjectperiod.blank?
issubjectpresent=TimetableAssign.where("section_id = ? AND subject_id = ?",section.id,k3)
if issubjectpresent.blank?
isteacherpresent=TimetableAssign.where("section_id = ? AND employee_id = ?",section.id,k4)
if isteacherpresent.blank?
@finaltt=TimetableAssign.new
@finaltt.timetable_struct_id=@timetable_struct.id
@finaltt.employee_id=k4
@finaltt.section_id=section.id
@finaltt.standard_id=standard.id
@finaltt.division_id=division.id
@finaltt.subject_id=k3
@finaltt.timetable_definition_id=k2
@finaltt.timetable_day_id=k1
set_school_id(@finaltt,current_user)
if(@finaltt.save)
setflag_sub(subjectflag,k3,1)
setflag_period(periodflag,k2,1)
setflag_teacher(teacherflag,k4,1)
end
end
else
@subjectdetail=TimetableAssign.find_by_section_id_and_subject_id(@section.id,k3)
@finaltt=TimetableAssign.new
@finaltt.timetable_struct_id=@subjectdetail.timetable_struct_id
@finaltt.employee_id=@subjectdetail.employee_id
@finaltt.section_id=section.id
@finaltt.standard_id=standard.id
@finaltt.division_id=division.id
@finaltt.subject_id=@subjectdetail.subject_id
@finaltt.timetable_definition_id=k2
@finaltt.timetable_day_id=k1
set_school_id(@finaltt,current_user)
if(@finaltt.save)
setflag_sub(subjectflag,k3,1)
setflag_period(periodflag,k2,1)
setflag_teacher(teacherflag,k4,1)
end
end
end
end
end
end
end
end
end
end
end
참고URL : https://stackoverflow.com/questions/2177836/algorithm-for-creating-a-school-timetable
'IT story' 카테고리의 다른 글
| 클립 보드 이벤트 C # (0) | 2020.09.15 |
|---|---|
| Google Maps API v3에서 하나의 InfoWindow 만 열어 둡니다. (0) | 2020.09.15 |
| Eclipse에서 코드 블록을 축소하는 방법은 무엇입니까? (0) | 2020.09.15 |
| Android WebView로 기존 .html 파일로드 (0) | 2020.09.15 |
| 바이트 배열을 문자열로 변환 (Java) (0) | 2020.09.15 |