Abstract
Abstract
In my high school, teachers in the curriculum department need to spend a lot of time making a schedule for each student that can fit their subjects choice.So I have the idea of using computer programs to solve this problem.My high school uses the shift system.Therefore, we can’t arrange courses by class, but by individual.In this essay,there are three solution might be useful to make schedule for students.
Introduction
Introduction
My program starts with a simple case.Suppose that there are four subjects: a,b,c,d and three students.Each student needs to choose two subjects. There are 2 rooms and 2 time periods(1p.m. and 2p.m.) available.
For example, three students 's choice are :
Student1{a,b}
Student2{b,c}
Student3{c,d}
Then the timetable should be like the things below
For example, three students 's choice are :
Student1{a,b}
Student2{b,c}
Student3{c,d}
Then the timetable should be like the things below
In[]:=
TextGrid[{{Null,"Room1","Room2"},{"1p.m.","a","c"},{"2p.m.","b","d"}},FrameAll]
Out[]=
| Room1 | Room2 |
1p.m. | a | c |
2p.m. | b | d |
Under this schedule, all students are satisfied.Student 1 can always stay at room 1 to have a and b.Student 2 needs to go to room2 at 1 p.m. to have c and then go to room1 at 2p.m. to have b.Student 3 can always stay at room2 to have c and d.For the convenience of calculation and expression, the timetable will be represented by matrix in the output.Like the timetable above will be expressed asHowever,under these constraints we may not be able to give a perfect timetable.If all the students choose a same subject and then choose another subject that is different to other's choice,there will be no perfect schedule.Just like the example below and you can check it by yourself.Student1{a,b}Student2{a,c} Student3{a,d}The following part of the article will introduce how to use program to find a best timetable for students under these constraints.
a | c |
b | d |
Solution1: Find All Possible Schedule
Solution1: Find All Possible Schedule
The simplest way to find the schedules that can satisfy all students is to list all possible schedules and check them one by one.
In[]:=
ClearAll[a,b,c,d,P1,P2,P3,P4,Answer,Solution,FinalAnswer,as1,as2,as3,n,s1,s2,s3]AllSolutionFind[]:=(s1=Sort[{a,b}];s2=Sort[{b,d}];s3=Sort[{c,a}];FinalAnswer={};TimeTable=Flatten[Tuples[{a,b,c,d},4]];TimeTable=Partition[Partition[TimeTable,2],2];(CurrentList=Part[TimeTable,#];lista1=Part[CurrentList,1];lista2=Part[CurrentList,2];CurrentCan={Sort[{Part[lista1,1],Part[lista2,1]}],Sort[{Part[lista1,1],Part[lista2,2]}],Sort[{Part[lista1,2],Part[lista2,1]}],Sort[{Part[lista1,2],Part[lista2,2]}]};as1=Count[CurrentCan,s1];as2=Count[CurrentCan,s2];as3=Count[CurrentCan,s3];If[as1==as2==as3==1,AppendTo[FinalAnswer,MatrixForm[CurrentList]]];)&/@Range[256]; If[Length[FinalAnswer]==0,AppendTo[FinalAnswer,"There is no all satisfied function"]];Return[FinalAnswer])AllSolutionFind[]
Out[]=
,
,
,
,
,
,
,
a | d |
b | c |
a | d |
c | b |
b | c |
a | d |
b | c |
d | a |
c | b |
a | d |
c | b |
d | a |
d | a |
b | c |
d | a |
c | b |
The algorithm can list all possible schedules, including some symmetric ones, such as exchanging classes of two classrooms at the same time.But the disadvantage of this method is that it needs a lot of calculation. In the case of many rooms and time periods, this algorithm can hardly give a feasible solution, because there are too many possibilities.
Solution2: Lock The First Person’s Choice
Solution2: Lock The First Person’s Choice
Solution 1 needs to list all possibility.But for a perfect schedule, the first person’s subject selection certainly can be found in the schedule. So we can directly fill the two time periods of Room1 with the two subject that first student choose.This can reduce a lot of computation.
In[]:=
FindSolution[]:=(s1=Sort[{a,b}];s2=Sort[{b,d}];s3=Sort[{a,d}];s1p1=Part[s1,1];s1p2=Part[s1,2];s2p1=Part[s2,1];s2p2=Part[s2,2];s3p1=Part[s3,1];s3p2=Part[s3,2];list1={{s1p1},{s1p2}};list2={{s1p1},{s1p2}};list3={{s1p1},{s1p2}};list4={{s1p1},{s1p2}};Answer={};SubjectList={a,b,c,d};SubjectList=Delete[SubjectList,Position[SubjectList,s1p1]];SubjectList=Delete[SubjectList,Position[SubjectList,s1p2]];try1=RandomChoice[SubjectList];SubjectList=Delete[SubjectList,Position[SubjectList,try1]];try2=Part[SubjectList,1];list1={{s1p1,try1},{s1p2,try2}};list2={{s1p1,try2},{s1p2,try1}};list3={{s1p1,try1},{s1p2,try1}};list4={{s1p1,try2},{s1p2,try2}};(S1Can={Sort[{Part[Part[#,1],1],Part[Part[#,2],1]}],Sort[{Part[Part[#,1],1],Part[Part[#,2],2]}],Sort[{Part[Part[#,1],2],Part[Part[#,2],1]}],Sort[{Part[Part[#,1],2],Part[Part[#,2],2]}]};s1a1=Count[S1Can,s1];s1a2=Count[S1Can,s2];s1a3=Count[S1Can,s3];If[s1a1==s1a2==s1a3==1,AppendTo[Answer,MatrixForm[#]]];If[StudentHappy<s1a1+s1a2+s1a3<3,StudentHappy=s1a1+s1a2+s1a3])&/@{list1,list2,list3,list4};If[Length[Answer]==0,AppendTo[Answer,"There is no perfect solution "]];Return[Answer];)FindSolution[]
Out[]=
a | d |
b | d |
Solution3: Color Graph Solution
Solution3: Color Graph Solution
This method turns the scheduling problem into a vertex coloring problem. Each subject will become a vertex, and the two subjects selected by a student at the same time will be connected. After connecting all the vertices according to the students’ course selection, color all the vertices. It is required that the two connected vertices cannot be the same colors. Those vertices(subjects) with the same color can be placed at the same time periods, because no one need to have them at the same time.
In[]:=
ClearAll[a,b,c,d,e,f,biglist,student1,subjectlist,subject1,subject2,subject3,subject4]sg1=Subsets[#,{2}]&/@{{a,b},{b,c},{c,d}}sg1=DeleteDuplicates[Flatten[sg1,1]]vertexlink=#[[1]]<->#[[2]]&/@sg1vertexgraph=Graph[vertexlink]colorgraph=ResourceFunction["VertexColoring"][vertexgraph]ans2=HighlightGraph[vertexgraph,%,VertexSize0.2]ans1=MatrixForm[colorgraph]
Out[]=
{{{a,b}},{{b,c}},{{c,d}}}
Out[]=
{{a,b},{b,c},{c,d}}
Out[]=
{ab,bc,cd}
Out[]=
Out[]=
{{a,c},{b,d}}
Out[]=
Out[]//MatrixForm=
a | c |
b | d |
But when the connected image is a complete graph, the program will have problems.Just like the example below.
In[]:=
ClearAll[a,b,c,d,e,f,biglist,student1,subjectlist,subject1,subject2,subject3,subject4]sg1=Subsets[#,{2}]&/@{{a,b},{b,c},{c,a}}sg1=DeleteDuplicates[Flatten[sg1,1]]vertexlink=#[[1]]<->#[[2]]&/@sg1vertexgraph=Graph[vertexlink]colorgraph=ResourceFunction["VertexColoring"][vertexgraph]ans2=HighlightGraph[vertexgraph,%,VertexSize0.2]ans1=MatrixForm[colorgraph]
Programs That Can Adapt To More Situations
Programs That Can Adapt To More Situations
The main idea of this program is still to list all the possibilities, and then verify the schedule by finding independent edge set.After that put the feasible combination into the timetable. We can modify part of the data to complete the course scheduling. For example, the program below can complete three rooms, three time periods and four students. In theory, this program can adapt to any environment, but the amount of computation will increase.This program may take a while to run.
Conclusion
Conclusion
In reality, the problem of course arrangement is much more complicated than this, and my program also needs to be optimized. But in this case, we can still find their respective advantages and disadvantages from these algorithms.Listing all the possibilities and checking them one by one is the most basic solution, and there are many optimizations on top of it. For example, we can give priority to the most popular course selection combination, and then list all the remaining possibilities for course scheduling.That's actually what solution2 does.
Future Work
Future Work
In the future, I will optimize around the last algorithm. The ultimate goal is to create a course scheduling program for my high school that can completely replace manual work. Now it seems that I still need to make a lot of efforts.