Schedule generator with R

This sample R code is an implementation one of possible solutions for generating timetable schedule. The proposed solution is based on methods of evolutionary computing, and it uses (1+1) evolutionary strategy and simulated hardening. The success of solution is estimated on fulfillment of given constraints and criteria. Results of testing the algorithm show that all hard constraints are satisfied, while additional criteria are optimized to a certain extent.

Problem:

Each meeting slot is represented as block (lasts arbitrary number of hours, mostly form 1 to 4). For conducting every block required are: pair of departmetns, room, time-slot. It is also know in advance which groups attend which class and all rooms are the same size.

Input data all departments names, room names and time-slots.
Output data are rooms and timeslots for pair of departments in a time-schedule.

Constraints:

1. Resources can not overlap time-wise
   • No department can hold two meetings at the same time
   
   
   • No department can be present in two rooms at the same time
   
   
   • No rooms can receive two meetings at the same time
2. Note: If the resource is busy at the moment T1 and the class lasts t1, then the resource can only be re-occupied at the moment T2 = T1 + t1.
3. All time slots and rooms should be fully utilized.
4. Each time slot and room hosts a meeting between a pair of departments.
5. Every possible pair from the departments must appear in the timetable.
6. Meetings occur concurrently in all rooms, with no department present in the same time slot in two different rooms.

Formula of all combinations of departments with two pairs and without repeatition and no order is:

C(n, k) = n!/( k! * (n – k)! ) (similar to Pascal’s triangle).

where n is the total number of items, and k is the number of items you are choosing,

So if I have 6 departments, and we want to pairs of two, we will use this numbers as C(6,2) = 6! / (2!*4!) which is equal to 15. So we have to arrange the 15 pairs into the schedule. in this case, the schedule can only be of size 3 * 5, unless we can have empty slots or rooms.

Another consideration to keep in mind is, when you want to have a schedule filled with all the combinations, is that there should not be more rooms (columns, where each department can be present in only one room per time-slot) than there are the possible combinations (with pairs of two).

For example: with 6 departments at any given time, maximum possible combinations per time-slots is 3. So 3 rooms is sufficient. If you decide for more rooms (columns), the algorithm will not converge with a solution, since we want to have all timeslots per rooms populated.

The function to generate the schedule for 6 departments, 5 time-slots and 3 rooms is:

rm(list = ls())

library(combinat)
departments <- c("DEP1", "DEP2", "DEP3", "DEP4", "DEP5", "DEP6")
time_slots <- 5
rooms <- 3

department_pairs <- combn(departments, 2, simplify = FALSE)

# seed: 124 converges 
# seed: 123 not converge

set.seed(124)  
department_pairs <- sample(department_pairs)

timetable <- matrix(list(), nrow = time_slots, ncol = rooms)

can_schedule <- function(pair, slot, room, timetable) {
  d1 <- pair[1]
  d2 <- pair[2]
  for (r in 1:rooms) {
    if (length(timetable[[slot, r]]) > 0 && (d1 %in% timetable[[slot, r]] || d2 %in% timetable[[slot, r]])) {
      return(FALSE)
    }
  }
  return(TRUE)
}


fill_timetable <- function(timetable, department_pairs) {
  used_pairs <- rep(FALSE, length(department_pairs))
  
  for (slot in 1:time_slots) {
    for (room in 1:rooms) {
      for (pair_index in 1:length(department_pairs)) {
        pair <- department_pairs[[pair_index]]
        if (!used_pairs[pair_index] && can_schedule(pair, slot, room, timetable)) {
          timetable[[slot, room]] <- pair
          used_pairs[pair_index] <- TRUE
          break
        }
      }
    }
  }
  return(timetable)
}


timetable <- fill_timetable(timetable, department_pairs)
is_complete <- all(sapply(timetable, length) > 0)


if (is_complete) {
  schedule <- matrix(NA, nrow = time_slots, ncol = rooms)
  for (slot in 1:time_slots) {
    for (room in 1:rooms) {
      if (length(timetable[[slot, room]]) > 0) {
        schedule[slot, room] <- paste(timetable[[slot, room]][1], timetable[[slot, room]][2], sep = ":")
      }
    }
  }
  #fancy stuff
  schedule <- as.data.frame(schedule)
  colnames(schedule) <- paste("Room", 1:rooms, sep = " ")
  rownames(schedule) <- paste("Time Slot", 1:time_slots, sep = " ")
  print(schedule)
  
} else {
  print("generate new seed to get schedule")
  print(as.data.frame(timetable))  
}

And the results is:

As always, the complete code is available on GitHub in  Useless_R_function repository. The sample file in this repository is here (filename: schedule_builder.R). Check the repository for future updates.

Happy R-coding and stay healthy!