I just wondering if there are other ways to solve this problem (like Branch and bound) and some explanation for how the algorithm works. Problems: There are classes 1,2,…, that need to be scheduled. Each class has () as the number of periods and () as the teacher assigned to teach that class and () as the number of students in the class. There are classrooms 1,2,…,, where () is the number of seats in room . There are 5 days in the week (from Monday to Thursday), each day is divided into 12 periods (6 morning periods and 6 afternoon periods). The periods of each day are numbered from 1 to 60. Make a schedule (determine days, periods and rooms assigned to each class):
- Two classes with the same teacher must have separate schedules
- The number of students in each class must be less than or equal to the number of seats in the classroom
- The number of classes scheduled is the largest
I have tried the Greedy algorithms like this:
class Class:
constructor(ID, t, g, s)
self.ID = ID
self.t = t
self.g = g
self.s = s
self.rooms = []
self.sol = []
class Room:
constructor(ID, capacity)
self.ID = ID
self.capacity = capacity
self.last_False = 1
self.used = {slot: False for slot in range(1, 61)}
class Teacher:
constructor(ID)
self.ID = ID
self.used = {slot: False for slot in range(1, 61)}
function import_data()
classes = []
teachers = {}
rooms = []
N, M = read integers from input
for i = 1 to N do
t, g, s = read integers from input
class = new Class(i, t, g, s)
classes.append(class)
if g not in teachers.keys() then
teacher = new Teacher(g)
teachers[g] = teacher
temp = read list of integers from input
for i = 1 to M do
capacity = temp[i-1]
room = new Room(i, capacity)
rooms.append(room)
return classes, teachers, rooms
class Solver:
constructor(classes, teachers, rooms)
self.classes = classes
self.teachers = teachers
self.rooms = rooms
function find_possible_rooms()
for each class in classes do
for each room in rooms do
if room.capacity >= class.s then
class.rooms.append(room)
function solve()
find_possible_rooms()
sort classes by t in ascending order
removed_classes = []
for each class in classes do
for slot = 1 to 60 do
if slot + class.t > 61 then
continue
found_slot = true
for each room in class.rooms do
for period = slot to (slot + class.t - 1) do
if room.used[period] or teachers[class.g].used[period] then
found_slot = false
exit inner loop
if found_slot then
class.sol = [slot, room.ID]
for period = slot to (slot + class.t - 1) do
room.used[period] = true
teachers[class.g].used[period] = true
room.last_False = slot + class.t
exit outer loop
if not found_slot then
removed_classes.append(class)
for each class in removed_classes do
classes.remove(class)
sort classes by ID in ascending order
function print_sol()
print length of classes
for each class in classes do
print class.ID, class.sol
function main()
classes, teachers, rooms = import_data()
solver = new Solver(classes, teachers, rooms)
solver.solve()
solver.print_sol()
main()
And also tried with Local Search like this:
class Class:
constructor(ID, t, g, s)
self.ID = ID
self.t = t
self.g = g
self.s = s
self.rooms = []
self.sol = []
class Room:
constructor(ID, capacity)
self.ID = ID
self.capacity = capacity
self.last_False = 1
self.used = {slot: False for slot in range(1, 61)}
class Teacher:
constructor(ID)
self.ID = ID
self.used = {slot: False for slot in range(1, 61)}
function import_data()
classes = []
teachers = {}
rooms = []
N, M = read integers from input
for i = 1 to N do
t, g, s = read integers from input
class = new Class(i, t, g, s)
classes.append(class)
if g not in teachers.keys() then
teacher = new Teacher(g)
teachers[g] = teacher
temp = read list of integers from input
for i = 1 to M do
capacity = temp[i-1]
room = new Room(i, capacity)
rooms.append(room)
return classes, teachers, rooms
class Solver:
constructor(classes, teachers, rooms)
self.classes = classes
self.teachers = teachers
self.rooms = rooms
function find_possible_rooms()
for each class in classes do
for each room in rooms do
if room.capacity >= class.s then
class.rooms.append(room)
function initial_solution()
find_possible_rooms()
sort classes by t in ascending order
removed_classes = []
for each class in classes do
for slot = 1 to 60 do
if slot + class.t > 61 then
continue
found_slot = true
for each room in class.rooms do
for period = slot to (slot + class.t - 1) do
if room.used[period] or teachers[class.g].used[period] then
found_slot = false
exit inner loop
if found_slot then
class.sol = [slot, room.ID]
for period = slot to (slot + class.t - 1) do
room.used[period] = true
teachers[class.g].used[period] = true
room.last_False = slot + class.t
exit outer loop
if not found_slot then
removed_classes.append(class)
for each class in removed_classes do
classes.remove(class)
sort classes by ID in ascending order
function evaluate_solution()
score = 0
for each class in classes do
slot, roomID = class.sol
score += slot + roomID
return score
function local_search()
best_score = evaluate_solution()
best_solution = copy of classes
for each class in classes do
original_sol = class.sol
for each room in class.rooms do
if room.ID == original_sol[1] then
continue
class.sol[1] = original_sol[1]
room.used[original_sol[0]] = false
teachers[class.g].used[original_sol[0]] = false
for period = original_sol[0] to (original_sol[0] + class.t - 1) do
room.used[period] = false
teachers[class.g].used[period] = false
if room.capacity >= class.s then
class.sol[1] = room.ID
for period = class.sol[0] to (class.sol[0] + class.t - 1) do
room.used[period] = true
teachers[class.g].used[period] = true
score = evaluate_solution()
if score < best_score then
best_score = score
best_solution = copy of classes
room.used[original_sol[0]] = true
teachers[class.g].used[original_sol[0]] = true
for period = original_sol[0] to (original_sol[0] + class.t - 1) do
room.used[period] = true
teachers[class.g].used[period] = true
classes = copy of best_solution
function metaheuristic()
iterations = 100
best_score = evaluate_solution()
best_solution = copy of classes
for i = 1 to iterations do
local_search()
score = evaluate_solution()
if score < best_score then
best_score = score
best_solution = copy of classes
classes = copy of best_solution
function print_sol()
print lengthof classes
for each class in classes do
print class.ID, class.sol
function main()
classes, teachers, rooms = import_data()
solver = new Solver(classes, teachers, rooms)
solver.initial_solution()
solver.metaheuristic()
solver.print_sol()
main()
I'm curious about the Branch & Bound. I've tried some google search and chat gpt but I haven't found anything useful to me yet. Can someone explain how Branch & Bound works on this problem for me ? Thanks alot.