Help me in Algorithm.

wodDyLee 101 Jul 31, 2007 at 20:47

Hi all, now I have a problem that I don’t whether GA is suitable for or not.

I give an example base on my university,

Year 1:
- 5 Core subjects (all must be fulfilled)
- 5 Elective subjects (choose any 4)

Year 2:
- 4 Core subjects (all must be fulfilled)
- 13 Elective subjects (choose any 4)

Year 3:
- 3 Core subjects (all must be fulfilled)
- 6 Elective subjects (choose any 4)

All students must pass total 24 subjects (core subjects + elective subjects) in 3 years in order to get their degree. Each year there are 3 semesters, so separate the courses of the year into 3 semesters, and they are 2 long semesters and 1 short semester. Like below study plan (eg. Year 1):
Year 1:
Jan session (long semester)
3 subjects
May session (long semester)
4 subjects
August session (short semester)
2 subjects

So here is one way to separate the subjects into different semester in order to generate the study plan.

I think there is another way to generate the study plan by using Credit hour of each subject, all the Core subjects that each student must fulfil, and for elective subjects, students just need to fulfil the credit hour of each year.

So 1st way to generate the study plan is based on Fulfilment of subjects. 2nd way is based on the Credit hour of subjects.

And also there still the prerequisite of some Core subjects, Like below:
Year 1:
August session (Current semester of the student)
Cs171 <–(prerequisite of the Cs208, but the student fail the exam)

Year 2:
Jan session (The coming semester)
X Cs208 <–(because the student never fulfil the requirement, so not allow to take this subject)
Cs171 <–(retake the subject to fulfil the requirement, so if the student pass the subject, then he/she will allow to take the subject in next coming semester)
Other available subjects.

Hope you can see my post until here, now I think I am only use these two ways to generate the study plan for each student (Fulfilment of the subjects, and Credit hours of the subjects).

In your opinion, is the GA suitable for me based on the scenario?

And btw can you tell me some algorithms that designed for Arrangement and Scheduling?

Because I am still a student, and doing my final year project, I am new in the algorithm, so actually in my case, that use an algorithm better or just the assignment and operator better (like a simple program? Use “if statement” and “looping statement”)?

All the study record of each student will be stored in a database, and according to the record to generate the study plan.

Please help me.

7 Replies

Please log in or register to post a reply.

Ed_Mack 101 Jul 31, 2007 at 23:09

This thread has been complained about, as such as it is a ‘homework question’.
But, if you can rephrase it, into a single question ‘i’ve tried to do this, this method, but this went wrong’ the community will take much more interest.

wodDyLee 101 Aug 01, 2007 at 00:49

Hi, Ed Mack.

I hope you can understand the above question was not come from the Lecturer.

I give the real example that because I worry about you guys might not be understand my question, becuase from starting I try too use GA to solve my problem, but some people say GA is suitable and some people say no.

I am new to the algorithm, and when I search the algorithm on Internet, the result let me don’t where to start my 1st step.

All the questions that I typed by my hand, and its not a home work.

wodDyLee 101 Aug 01, 2007 at 01:07

From the starting I just wanna know which algorithm is most suitable for the Arrangement and Scheduling problem ?

I went other forum before and some people they suggested me “GA”, but some people say no.

wodDyLee 101 Aug 01, 2007 at 02:49

Okie, let me change a point of view.

Let say I have 10 tasks here, from task 1 to task 10, each one has different priority.

and the algorithm will arrange and schedule the tasks for me based on priority of each tasks. and some task is the prerequisite of other tasks, if not fulfil the prerequisite then not allow to enter next task.

Reedbeta 167 Aug 01, 2007 at 18:11

I don’t think a GA will be terribly useful here because they tend to come up with approximate solutions, and you have constraints that cannot be violated (prerequisites).

zakaluka 101 Aug 01, 2007 at 22:54

I agree with Reedbeta. GAs are most primarily useful when you have an input set that is too large to map 100% to the output. So, you use a GA to try and find which set of values from all those tested will get you a local maximum, ie, approximate best answer.

Take your arrangement and scheduling problem. The set of inputs, or classes, is finite. Just using the information you have provided above, I can compute every possible combination of classes in a very “short” amount of time. Given that you have prerequisites for classes AND want to take exam failure, etc. into account, I would say that the easiest way to go about this is to use some form of constraint-based modeling.

Now, I might not be using the term “constraint-based” correctly, but here’s what I mean. Let’s say you start your study plan program from scratch. So, there are no current constraints on class choices for any year save the first (due to prerequisites). The user, at this time, enters some data (maybe historical data on grades, or just mapping out some classes they want to take in the future). Treating this user input as constraints on class choices, it is trivial for your program to figure out which classes have to come before to satisfy prerequisites and what can be taken in the future. You can also easily determine whether a given study plan is feasible or not.

So, in summary, I would say that while using a GA is possible in this case, it is overkill and non-optimal.



wodDyLee 101 Aug 02, 2007 at 23:45

Thanks for Reedbeta and Zakaluka,

When 1st time I tried to find out the solution for my problem, I went to some forums also, people said the GA is suitable for my case, and ask me to search the information based on Timetabling problem, but when I go throught the Timetabling problem, I find the GA might be not the best solution for my case, I think those peopel might be misunderstanding what is my problem, and at the same time, I focused on the wrong point, and I start confused on my case. from you guys’ opinion and based on the information that I searched, I think GA is very good in solve Timetabling problem and TSP(Traveling Salesman Problem), finally I know what is the GA and what GA actually performs.

Now I would like to change a solution that is based on the Priority and Sorting of the task, becuase the Priority can satisfy the “prerequisite” and Sorting is to sort for the priority.

Like students who is not allowed to make a shortcut :” take Year 2 subjects before they finished the Year 1.” and “students are not allowed to take certain subjects before they satisfy the requirement. “ <<– Here all are the Priority, and the sorting will sort for the priority, high priority must be finished 1st then just go to the low priority, so by default that means the Year 1 must be the highest priority, and the Year 3 should be the lowest priority.

Do you guys agree me ? Can give me some suggestion based on my solution?
and is there any Algorithm that working fine with the Priority and Sorting ?

Thanks . \^\^