Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
797 views
in Technique[技术] by (71.8m points)

c - Class Scheduling to Boolean satisfiability [Polynomial-time reduction] Final Part

I'm working since few weeks now on a project really interesting but unfortunately with a very complex background.

I already asked 3 questions :

in both of them, I get my answer (thank you again @Amit) but now arrived the final part, who will make this project useable :)

I for now can manage :

  • N time-intervals.
  • C courses.
  • T teachers.
  • S rooms.

My constraints are the follow:

  • 2 teachers cannot be in the same room in the same time.
  • 2 courses cannot be in the same room in the same time.
  • Teachers can teach only specific courses.
  • Some courses can happen only on specific time-intervals.

So this is for now, my result :

Illustration of my final output for now

But here comes the final part that I want to add : I want to manage group of students, with the following constraints :

  • A group has only some courses to do.
  • 2+ groups can be in the same room in the same time only for specific courses (like Magistral course for example)

Again, I success to isolate the constraint, but I have no idea on how to transform this constraint into a "time-intervals should not overlap" constraint.

Thanks in advance, Best regards,

See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Reply

0 votes
by (71.8m points)

Since a student can only be in one place at a time:

Lectures for courses attached to the same student group should not overlap in time.

Edit:

There should be no constraint on different student groups overlapping. If you have such a constraint you should remove it!

The constraints are on courses. If you schdeule a lecture for course A, then it may not overlap a lecture for any other course for the student group(s) that attend course A. It may also not overlap any other course held by the same teacher.

So, you have a many-to-many relationship between students and courses and a many-to-many relationship between teachers and courses.

You want to schedule a number of lectures for each course with the constraint that no teacher and no student has overlapping lectures.

Regarding

2+ groups can be in the same room in the same time only for specific courses (like Magistral course for example)

If the groups may not mix, then it is not the same course (even though the subject may be the same). So if two student groups can not mix for Java, then you need to model it as two separate courses, Java group1 and Java group2.


与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
OGeek|极客中国-欢迎来到极客的世界,一个免费开放的程序员编程交流平台!开放,进步,分享!让技术改变生活,让极客改变未来! Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...