Building a School Schedule Generator

Question

I want to build an automatic school scheduler, but first of all, let me explain to you the details of the school. The school has a specific number of working days (6 for example) and has many grades or classes. Each class has specific subjects, a specific number of study days, and a specific number of daily lectures, as well. There are teachers, and each teacher has one or more subjects that he teaches in one or more classes, and each teacher has a number of days he teaches (2, 3...) and he can also be excluded from work on specific days (Mon, Tue...) of course, if the number His working days do not equal the total number of working days. As for subjects, each subject belongs to a specific class, has a specific teacher, and has a specific number of weekly lectures. I want to build an automatic scheduler that builds the weekly schedule for each class, under the following conditions:

1. The teacher’s weekly lectures are distributed in type and number (the total number of weekly lectures for the subjects taught by the teacher, of course the number of working days will be sufficient to complete the lectures during them) equally over the number of working days for the teacher, respecting the days in which the teacher is not available.
2. Teachers’ lectures are distributed equally and fairly so that no teacher is treated unfairly at the expense of another.

The previous details were to clarify the point I reached in solving the problem:

• I distributed the teachers’ lectures on their workdays successfully, but when I come to distribute the teacher’s lectures to the classes, I find a problem in how to distribute them so that I do not wrong one teacher at the expense of another, and that one teacher’s lectures are not always the first or always the last. For example: Teacher T1 has 6 working days and has 3 subjects (M1, M2, M3) that he teaches, each subject belongs to a different class. The total number of weekly lectures for these subjects is 21 lectures (7 lectures in each class) The distribution of lectures over the teacher's working days would be something similar to this:

Day1: M1, M1, M2, M2 Day2: M1, M2, M3, M3 Day3: M1, M2, M3, M3 Day4: M1, M2, M3 Day5: M1, M2, M3 Day6: M1, M2, M3

And so every teacher... But the problem arises when distributing these lectures to teachers on the days of different classes so that at least the mandatory conditions are met. For example, if I start distributing teacher T1’s lectures to the different classes, how can I ensure that he does not dominate the first lectures without his companions? Consider this the difficulty.

Additional Information:

I'm familiar with basic object-oriented programming concepts in JavaScript and have looked at some online resources on scheduling algorithms. However, they seem too complex for my needs.

Are there any efficient algorithms suitable for this scenario, or can you suggest an approach for distributing subjects effectively while considering the mentioned constraints?

Example Data:

const teachers = [
  {
    name: "Math-Teacher",
    id: "T1",
    workDays: 6,
    unavailableDays:[],
    subjects: ["M1", "M2", "M3"],
  },
  {
    name: "Quilting-Teacher",
    id: "T2",
    workDays: 2,
    unavailableDays:['Mon'],
    subjects: ["Q1", "Q2", "Q3"],

  },
  {
    name: "Italian-Teacher",
    id: "T3",
    workDays: 6,
    unavailableDays:[],
    subjects: ["I1", "I2", "I3"],
  },
  {
    name: "Biology-Teacher",
    id: "T4",
    workDays: 4,
    unavailableDays:[],
    subjects: ["B1", "B2", "B3"],
  },
  {
    name: "history-Teacher",
    id: "T5",
    workDays: 2,
    unavailableDays:['Sat', 'Tue'],
    subjects: ["H1"],
  },
  {
    name: "Phasics-Teacher",
    id: "T6",
    workDays: 5,
    unavailableDays:[],
    subjects: ["P1", "P2", "P3"],
  },
  {
    name: "Italian-Teacher",
    id: "T7",
    workDays: 3,
    unavailableDays:[],
    subjects: ["I1", "I2", "I3"],
  },
  {
    name: "Chemistry-Teacher",
    id: "T8",
    workDays: 3,
    unavailableDays:[],
    subjects: ["C1", "C2", "C3"],
  },
  {
    name: "English-Teacher",
    id: "T9",
    workDays: 4,
    unavailableDays:[],
    subjects: ["E1", "E2", "E3"],
  },
  {
    name: "Arabic-Teacher",
    id: "T10",
    workDays: 6,
    unavailableDays:[],
    subjects: ["A1", "A2", "A3"],
  },
];

const subjects = [
  //1-sec subjects
  {
    name: "Math",
    class: "1-sec",
    id: "M1",
    weeklyLectures: 7,
  },
  {
    name: "Biology",
    class: "1-sec",
    id: "B1",
    weeklyLectures: 4,
  },
  {
    name: " Quilting",
    class: "1-sec",
    id: "Q1",
    weeklyLectures: 3,
  },
  {
    name: "Isramic Culture",
    class: "1-sec",
    id: "I1",
    weeklyLectures: 3,
  },
  {
    name: "Phasics",
    class: "1-sec",
    id: "P1",
    weeklyLectures: 5,
  },
  {
    name: "History",
    class: "1-sec",
    id: "H1",
    weeklyLectures: 3,
  },
  {
    name: "English",
    class: "1-sec",
    id: "E1",
    weeklyLectures: 5,
  },
  {
    name: "Arabic",
    class: "1-sec",
    id: "A1",
    weeklyLectures: 6,
  },
  {
    name: "Chemistry",
    class: "1-sec",
    id: "C1",
    weeklyLectures: 3,
  },

  //2-sec subjects
  {
    name: "Math",
    class: "2-sec",
    id: "M2",
    weeklyLectures: 7,
  },
  {
    name: "Biology",
    class: "2-sec",
    id: "B2",
    weeklyLectures: 4,
  },
  {
    name: " Quilting",
    class: "2-sec",
    id: "Q2",
    weeklyLectures: 3,
  },
  {
    name: "Isramic Culture",
    class: "2-sec",
    id: "I2",
    weeklyLectures: 3,
  },
  {
    name: "Phasics",
    class: "2-sec",
    id: "P2",
    weeklyLectures: 5,
  },
  {
    name: "English",
    class: "2-sec",
    id: "E2",
    weeklyLectures: 5,
  },
  {
    name: "Arabic",
    class: "2-sec",
    id: "A2",
    weeklyLectures: 6,
  },
  {
    name: "Chemistry",
    class: "2-sec",
    id: "C2",
    weeklyLectures: 3,
  },

  //3-sec subjects
  {
    name: "Math",
    class: "3-sec",
    id: "M3",
    weeklyLectures: 7,
  },
  {
    name: "Biology",
    class: "3-sec",
    id: "B3",
    weeklyLectures: 4,
  },
  {
    name: " Quilting",
    class: "3-sec",
    id: "Q3",
    weeklyLectures: 3,
  },
  {
    name: "Isramic Culture",
    class: "3-sec",
    id: "I3",
    weeklyLectures: 3,
  },
  {
    name: "Phasics",
    class: "3-sec",
    id: "P3",
    weeklyLectures: 5,
  },
  {
    name: "English",
    class: "3-sec",
    id: "E3",
    weeklyLectures: 5,
  },
  {
    name: "Arabic",
    class: "3-sec",
    id: "A3",
    weeklyLectures: 6,
  },
  {
    name: "Chemistry",
    class: "3-sec",
    id: "C3",
    weeklyLectures: 3,
  },
];

const classes = [
  {
    name: "1-secondary",
    id: "1-sec",
    DailyLectures: 7,
    subjects: ["M1", "Q1", "I1", "A1", "E1", "H1", "C1", "B1", "P1"],
  },
  {
    name: "2-secondary",
    id: "2-sec",
    DailyLectures: 7,
    subjects: ["M2", "Q2", "I2", "A2", "E2", "C2", "B2", "P2"],
  },
  {
    name: "3-secondary",
    id: "3-sec",
    DailyLectures: 7,
    subjects: ["M3", "Q3", "I3", "A3", "E3", "C3", "B3", "P3"],
  },
];

const daysOfWeek = ["Sat", "Sun", "Mon", "Tue", "Wed", "Thr"];

Expected Output:

I expect the output to be a weekly schedule for each class, with lectures of teachers evenly distributed across the working days.

For example(like this but in a efficient way):

1-sec: {
  Sat: [
    { name: 'Math', class: '1-sec', id: 'M1', weeklyLectures: 7 },
    { name: 'Math', class: '1-sec', id: 'M1', weeklyLectures: 7 },
    { name: ' Quilting', class: '1-sec', id: 'Q1', weeklyLectures: 3 },
    { name: 'Biology', class: '1-sec', id: 'B1', weeklyLectures: 4 },
    {
      name: 'Isramic Culture', class: '1-sec',  id: 'I1' weeklyLectures: 3
    },
    { name: 'Biology', class: '1-sec', id: 'B1', weeklyLectures: 4 },
    { name: 'History', class: '1-sec', id: 'H1', weeklyLectures: 3 },
  ],
  Sun: [
  another 7 lectures....
  ],
  Mon: [
    ...
  ],
  Tue: [
....
  ],
  Wed: [
    .....
  ],
  Thr: [
    .....
  ]
}

2-sec:{
.....
}

3-sec:{
.....
}

Answer 1

A precise definition of the problem:

The input specifies teachers and subjects.

A teacher has:

• a unique id,
• a list of subjects to which it can be assigned
• a maximum number of days worked per week
• a list of week days when it does not work

A subject has:

• a unique ID,
• a number of lectures per week

The purpose of the application is to assign teachers to all the subject lectures and subject lectures to a day of the week, subject to constraints:

• teacher must only be assigned to lectures of the subjects in its list
• teacher must only be assigned to lectures on days when it works
• teacher must only be assigned to lectures on the number of different days it works in a week

The output shows the lectures and teacher assigned to them for each day of the week****

---

---

This problem is often called 'assigning agents to tasks'. There are several algorithms that can solve this. I use the Ford-Fulkerson Maximum Flow Algorithm ( theory.stanford.edu/~tim/w16/l/l1.pdf )

The trick is, as always, adapting the algorithm to your particular constraints so that the max flow algorithm operates without violating any of them.

The particular problem here is that many of the teachers ( = agents ) are constrained to work only a few days per week, but many subjects are specified to be taught 6 or even 7 times a week. Obviously, each subject may have to be assigned more than once per day and for subjects with many lectures per week and teachers constrained to a few days, sometimes many times a day.

Experimentation shows that constraining to 5 the maximum number of lectures per day for one subject works well. There is a reason for this: the Q subject needs 9 lectures ( three classes * three lectures ) but the only teacher, T2, is constrained to 2 working days, so the Q lectures must be assigned over just two days -> 5 on one and 4 on the other.

Here is the result:

Sat:
T1 assigned M1, T1 assigned M1, T1 assigned M1, T1 assigned M1,
T9 assigned E1, T1 assigned M2, T1 assigned M2, T1 assigned M2,
T1 assigned M2, T6 assigned P2, T9 assigned E2, T1 assigned M3,
T1 assigned M3, T1 assigned M3, T1 assigned M3, T6 assigned P3,
T9 assigned E3,

Sun:
T1 assigned M1, T1 assigned M1, T1 assigned M1, T6 assigned P1, 
T10 assigned A1, T10 assigned A1, T10 assigned A1, T10 assigned A1,
T6 assigned P2, T6 assigned P2, T6 assigned P2, T6 assigned P2,
T1 assigned M3, T1 assigned M3, T1 assigned M3, T9 assigned E3,
T9 assigned E3, T9 assigned E3, T9 assigned E3,

Mon:
T4 assigned B1, T4 assigned B1, T4 assigned B1, T4 assigned B1,
T10 assigned A1, T10 assigned A1, T1 assigned M2, T1 assigned M2,
T1 assigned M2, T9 assigned E2, T9 assigned E2, T9 assigned E2, 
T9 assigned E2, T10 assigned A3, T10 assigned A3, T10 assigned A3,
T10 assigned A3,

Tue:
T2 assigned Q3, T2 assigned Q3, T2 assigned Q3, T2 assigned Q1,
T2 assigned Q1, T2 assigned Q1, T4 assigned B2, T4 assigned B2,
T4 assigned B2, T4 assigned B2, T10 assigned A2, T10 assigned A2,
T10 assigned A2, T10 assigned A2, T6 assigned P3, T6 assigned P3,
T6 assigned P3, T6 assigned P3,

Wed:
T5 assigned H1, T5 assigned H1, T5 assigned H1, T3 assigned I1,
T7 assigned I1, T3 assigned I1, T9 assigned E1, T9 assigned E1,
T9 assigned E1, T9 assigned E1, T2 assigned Q2, T2 assigned Q2, 
T2 assigned Q2, T10 assigned A2, T10 assigned A2, T4 assigned B3,
T4 assigned B3, T4 assigned B3, T4 assigned B3, T10 assigned A3,
T10 assigned A3,

Thr:
T6 assigned P1, T6 assigned P1, T6 assigned P1, T6 assigned P1,
T8 assigned C1, T8 assigned C1, T8 assigned C1, T3 assigned I2,
T7 assigned I2, T3 assigned I2, T8 assigned C2, T8 assigned C2,
T8 assigned C2, T3 assigned I3, T3 assigned I3, T3 assigned I3,
T8 assigned C3, T8 assigned C3, T8 assigned C3,

T1 works 3 days, 21 total lectures
T2 works 2 days, 9 total lectures
T3 works 2 days, 7 total lectures
T4 works 3 days, 12 total lectures
T5 works 1 days, 3 total lectures
T6 works 4 days, 15 total lectures
T7 works 2 days, 2 total lectures
T8 works 1 days, 9 total lectures
T9 works 4 days, 15 total lectures
T10 works 4 days, 18 total lectures

The complete C++ code for this can be seen at https://github.com/JamesBremner/78250368