For an assignment i need to program an application to schedule conversations. Something similar to speeddating or Pta meeting. The problem is that i know that this is hard to solve, but i dont know if its np-hard. What can I do to proof that this problem is np-hard? I read that i need to reduce a known problem to my problem. But how do I do this?
There is an event where Respresentatives of the elementary schools talks with the representatives of a highschool. They will talk about the students that will be transferred to the highschool. There are approximately 200 elementary schools and 40 highschools that will be participating in this event. And this event last 2 days.
The rules are:
- The duration of each conversation is based on the ammount of students per representatives. Each conversation last 5 minutes per student. If a group consist of 1 student, this conversation last 10 minutes.
- No timeclashes
- All the students of the same group will be scheduled together, so, a representatives will only face the same representative once.
- Timespan is 13.00-19.00
- The waiting time of a representative is at most 20% of his time. A waiting time is an empty timeslot between the 1st and last conversation.
- Schedules for 2 days
- Each representatives participate for 1 day.
Based on this i will decide if i will use a heuristic algorithm to solve this problem.
Sorry for my english
Thanks in advance