Assignment Task
Think about the following timetabling issue. A researcher may participate in numerous projects. Based on their projects, ten researchers must attend the following meetings (P1-P8). The projects that each researcher is working on are listed below:
- Adi:P1, P3, P6, P2
- Ahmad: P2, P3
- Ali: P2, P3, P5, P8
- Ann: P4, P6
- Debs: P6, P1
- John: P6, P1, P3, P4
- Lee: P7, P8
- Linda: P7, P5
- Maria:P1, P2
- Sophia:P8, P7, P5, P6
Each day (D1, D2 and D3) has two meeting slots (S1 and S2), and each slot has two meeting rooms (R1 and R2). That is, we can have two meetings in parallel. The researchers must be scheduled to attend all of their project meetings on those days without conflict.
a) Draw a graph to represent the project meeting problem.
b) Create a suitable constructive heuristic for these project meetings using a graph-based technique so that all researchers can attend them without conflicts. Write a pseudocode or flowchart of your algorithm.
c) The effectiveness of the solution is evaluated by summing the penalty value, where:
penalty is given if the researcher is idle (does not attend a meeting between two meetings) for n timeslots.
- If a researcher has only one meeting scheduled per day, they lose one point (whereas he actually has more than one project meeting).
For every day D1 or D2 when a room is unoccupied, there will be a two- point penalty (not reserved for a meeting). - Implement the proposed constructive heuristic (in (b)) and demonstrate how you calculate the solution’s quality value in your generated timetable.
