“Generating Timetable Schedule with Evolutionary Computing in 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!

Continue reading: Schedule generator with R

Scheduling optimization using R

The sample R code discussed in the text provides a possible solution to effectively generate timetable schedules. The process is founded on evolutionary computing methods, specifically the (1+1) evolutionary strategy and simulated hardening. This solution was developed to meet specific constraints and optimization criteria.

Implications and future Developments

The R code solution is designed to deal with a common scheduling problem in academia and businesses: scheduling meetings in a way that avoids overlapping and efficiently utilizes all available resources. The code deals with the assignment of resources, such as rooms and timeslots, for meetings that involve pairs of departments.

The potential future of this algorithm largely revolves around its versatility. Its applications are not limited to meeting scheduling, but can extend to other areas that require efficient allocation of resources, such as class scheduling in educational institutions, and job scheduling in manufacturing and production industries.

Actionable Advice

Further Refinement

To improve the functionality and broad applicability of the solution, the model can be significantly expanded. This may involve developing the solution to cater for meetings involving more than two parties, or to constrain certain departments to specific time slots or rooms only. Engaging a team to constantly refine and adapt the code increases its usability and functional application in different contexts.

Learning and improvements

A potential avenue of expansion is to incorporate machine learning techniques to the algorithm. Over time, the algorithm could ‘learn’ the preferred timeslots or rooms of departments, or find patterns in meeting schedules that work better than others. This enables it not only to produce valid timetables, but timetables that are optimal based on past successful schedules.

User-interface development

R developers with the skillset to develop user interfaces could create a GUI for input and modification of parameters. This would make the tool more user-friendly for non-tech savvy users who want to utilize this scheduling solution.

Contribution to Open Source Community

Contributing this solution as an open-source code on platforms such as GitHub could bring in inputs from developers around the world to enhance the functionality of the algorithm. New features and refinements could be added by the community, making it a better solution for scheduling problems.

Read the original article