Search code examples
algorithmencodinggenetic-algorithmnp-completenp-hard

How to do Binary Encoding in Genetic Algorithm for better results in Timetable Scheduling Problem?

I have a problem of University Timetable Scheduling which I am trying to solve with Genetic Algorithm. I want to know the best encoding type for this problem that can also help me in satisfying few of the constraints. For this problem, the timetable will have the following structure,

  • There will be a total of 5 days in which the timetable will be scheduled (Monday to Friday).
  • Every day, there will be 5 different slots, and one slot will have one lecture.
  • However, Lab Lectures will be conducted over two consecutive slots.
  • Timetable will also tell the Room Number (or Lab number) of each lecture and also the name of Instructor for every lecture.

Now, the timetable looks something like this, (in the picture, there are multiple slots, but I will be considering only 5 slots instead of dividing the timetable into so many slots)

enter image description here

This is a timetable of only one section. There are around 25 sections in one single timetable.

Now, what I have done is written the data of every course, its section, and its instructor in one file in a format like this,

1
Object Oriented Programming 
CS-3B
Dr Ali Hassan 
,
2
Object Oriented Programming 
SE-3A
Dr Ali Hassan 
,
3
Remote Sensing and GIS 
CS-7F
Dr Tom Baker

And to represent the Timetable, I have made the file like this,

0
1
2 2 9
3 2 9
0
2
2 1 9
3 1 9
0
3
2 5 36
4 1 36
  • 0 is a separator, which separates one object from another.
  • First number is basically the ID of the course. "1" actually represents the first object in my first file (i.e. Object Oriented Programming, CS-3A, Dr. Ali Hassan).
  • Second row represents the first lecture of course (with id = 1) in the timetable. The format is as follows, First number is the day. Second number is the Slot. Third number is the Room Number.. So, in this case, it is saying that the first lecture of course id = 1 will be held on "Tuesday", in the "2nd Slot" and in "Room Number 9".
  • Third row represents the second lecture of the same course.

Now I need to encoding of this timetable. I have opted to go with Binary Encoding for now (obviously, I can shift to others but need to know which and how) and done the encoding like this,

00000001 00000010 00000010 00001001 00000011 00000010 00001001 
00000010 00000010 00000001 00001001 00000011 00000001 00001001 
00000011 00000010 00000101 00100100 00000100 00000001 00100100 
00000100 00000010 00000001 00001101 00000100 00000010 00000110 
00000101 00000010 00000010 00001101 00000011 00000001 00000011

Since the total number of courses are likely to fall between 200-220 so I went with 8-bit encoding.

Encoding is done in this format,

Course_ID First_Lecture_Day First_Lecture_Slot First_Lecture_Room 2nd_Lec_Day 2nd_Lec_Slot 2nd_Lec_Room

Now, I want to know few things regarding this,

  • Is this encoding the right approach? or should I have done this in any other way?
  • A serious issue with this is this that I have the following two constraints,

ss

  1. Lab Lectures must be conducted in two consecutive slots.
  2. Course Lectures must be conducted on different days, i.e. no course should have both lectures on same day.

Now, I can resolve the 2nd issue by implementing it in the fitness function (I assume. I haven't yet went there but I am thinking that I can solve this issue there)

However, I do not know how can I solve the first issue? Is there any particular way in which I can instruct the Genetic Algorithm to ALWAYS keep the lab lectures in consecutive slots? For example, I use another bit in my Binary Encoding, like maybe this,

00000001 00000010 00000010 00001001 00000011 00000010 00001001 00000000

00000010 00000010 00000001 00001001 00000011 00000001 00001001 00000001

Where the last bit will tell whether the course is of lab or of course.. And depending upon that bit, if you are changing the lecture slots, then if the lab bit is on, then change both the lecture slots so that they stay with each other and hence, lab is conducted over consecutive slots? How can I make sure of this? Can anyone guide me, please?

And also if any other approach I should have used in the Encoding Process for Genetic Algorithm? Thank you.

Solution

  • If your lab rooms are different from your normal rooms then you should be solving lab and normal courses separately.

    If you want a course to always use the same room than you don't need to encode the room twice just use a bit mask for the multiple slots that the course will take up.

    [Course Id][Room Id][Slot Bit Mask]

    [Course Id] is a byte 1-255

    [Room Id] is a byte, assuming less than 256 rooms

    [Slot Bit Mask] is a UInt32 bit mask, gives you 32 slots but you only need to use 25 (5 days * 5 slots/day)

    [Course Id] and [Room Id] correspond to your separate lists of Normal and Lab, Courses and Rooms.

    [Slot Bit Mask] for Normal Courses is constrained to 2^n (n = 0-24) BitwiseOr 2^m (m = 0-24), where Floor(n / 5) != Floor(m / 5). This equates to 2 unique days a week, 1 slot per day.

    [Slot Bit Mask] for Lab Courses is constrained to 3 * 2^n (n = 0-3, 5-8, 10-13, 15-18, 20-23), where Floor(n / 5) != Floor(m / 5). This equates to 1 day per week, 2 consecutive slots per day. edit only need 1 lab day

    Your fitness function is just the error score. An Error is when [Room Id A] == [Room Id B] AND ([Slot Bit Mask A] BitwiseAnd [Slot Bit Mask B]) > 0. Fitness = (Total - Error) / Total.

    EDIT Example encoding:

    Course Id = 1, Room Id = 2, Normal Course Slots = Monday 3rd slot and Friday the 4th slot. Monday 3rd slot (2^n, n = 2). Friday 4th slot (2^m, m = 23). Floor(n / 5) = 0 and Floor(m / 5) = 4, since 0 and 4 are not equal its a valid Normal Course Slot Bit Mask.

    Slot Bit Mask UInt32 Bit Index 31 to Bit Index 0

    (ZZZZZZZ5 43215432 15432154 32154321)

    (0000000F FFFFTTTT TWWWWWTT TTTMMMMM)

    Full encoding Course, Room, Slot

    00000001b 00000010b 00000000 10000000 00000000 00000100b