4 Replies Latest reply on Aug 18, 2017 9:09 AM by Karen Hignett

# Classroom (interval) scheduling problem modify greedy algorithm to optimize #classes/classroom/day

I have a list of courses with a unique id in rows. The courses already have a schedule with assigned rooms in various buildings. Eight classrooms in a new building have become available and I need to maximize the number of the existing courses scheduled in the new classrooms for each weekday. Each course has a start time and end time and day of the week. For each day of the week I would like to find the course with the earliest end time, then compare that end time to other classes to see if it's earlier than the start time of next class. So, ENDTIME(course1)<=STARTTIME(course2,3,4....n). The first true is added to schedule, else null. Then find next earliest end time course, repeat comparison to other course start times, add to schedule or null...until schedule is filled and all classes have been added or ruled out. Attached is the workbook.

• ###### 1. Re: Classroom (interval) scheduling problem modify greedy algorithm to optimize #classes/classroom/day

Hi, Karen

I have played your workbook for a bit, still not come up with a solution. But I would like to share what I have achieved so far.

Workbook attached.

ZZ

• ###### 2. Re: Classroom (interval) scheduling problem modify greedy algorithm to optimize #classes/classroom/day

ZZ -

Thank you for looking at this! I meant to say in original post that my plan was to sort by earliest end time, then use INDEX function to iterate through courses. So we are on the same page there.

Looking at your viz, you are filtering by day of [END DATE] to make the window view be based on the day of the week. Besides INDEX(), the only other calculation added is Class. The result of the calc is correct--the OTHERS set contains the optimal class schedule, but I don't understand how that is accomplished without any use of end time. (probably there is something obvious staring me in the face, but right now I'm not seeing it :-)) Also, I see what you are saying about the overlapping courses for Class 2 ending at 4:20, and I'm looking at why it occurred--thinking it's just too many dates going on in the original viz.

Can you explain how your calculation is working?

Thanks!

Karen

• ###### 3. Re: Classroom (interval) scheduling problem modify greedy algorithm to optimize #classes/classroom/day

Hi, Karen

If you change the Class calculation as below,

it could fix the issue I mentioned for 29 August 2017

ZZ

1 of 1 people found this helpful
• ###### 4. Re: Classroom (interval) scheduling problem modify greedy algorithm to optimize #classes/classroom/day

Hi ZZ,

I used rank_unique and restarted every end_time to number the courses ending at a particular day/time, then added a calculation that evaluated the rank number against the total rooms available for each class size.

For example, there are two rooms available that will seat up to 80, so: IF RANK_UNIQUE=1 THEN <classroom#1> ELSEIF RANK_UNIQUE=2 THEN <classroom#2>  ELSEIF RANK_UNIQUE>2 THEN <slack>

This works only if no end times overlap the following start time. I had one instance of that and adjusted it manually rather than re-writing the calculation--although I will rewrite it for future use.

If you have any other thoughts feel free to share!

Thanks you again for looking at this with me!

Karen