The hard constraints of exam seating problems are as follows:
H1: To prevent cheating (copying from another), no student of the same query set should allow to sit beside.
H2: Students having different query sets do not allow in nearest columns.
H3: As less as extra seats will be available in the exam hall during the exam.
H4: As many as seats will be used during the exam for student seating. H5: The minimum number of exams takes place in a room.
In this research, we are going to offer a model and some algorithm to solve exam seating problem. Our proposed system is applicable for I shape seat allocation system. The system needs two types of data as input, Room information and Exam information. The total number of students must have to be less than or equal to the total seats. For offering an optimum seating solution we followed some steps. These steps will be followed for each slot of examination.
Step 1: Two types of data sets are needed for exam seating, one is room information having room id, size of columns and rows; another is exam information with subject id and number of students. By processing room and exam information it will calculate total number of seats and students. Finally it will calculate the number of extra seats available after seating.
Step 2: When the amount of extra seats is greater than any room capacity, then it may possible of having one or more extra room. In this step it will search those rooms, which will be kept empty at the time of exam.
Step 3: Our main concept is to distribute column to the subject so at first it needs to calculate the number of columns and the capacity or number of rows for each column. To prevent copying from other it tries to ensure at least one column distance among students having same query set. That is why it will also calculate maximum usable column and its capacity for any subject.
Step 4: Then it will allot columns to the subjects. By using a combination of column size (row) we can ascertain the set of columns which will be assigned to subjects. After that it will provide a set of columns for each subject. In best case extra seats are not required, but in worst case it may require to assign some extra seats to subject for getting a set of column for exam seating.
Step 5: We have subject having different column size and number. We have also room identity which is represented by column number and row number as column size. So the common attribute is column size. By using this it assigns room and column number to the subject by maintaining one column distance between the columns having the same subject. After completing the column and room distribution it will provide a complete seating solution for the exam.
B.Problem formulation and Calculation
We have implemented those steps into three algorithms. In this section we are going to represent cost and complexity of our proposed algorithm.
List of parameters for both algorithm and calculation:
i=1. . . . . . . R
j= 1. . . . . . .S
R = number of rooms S= number of subjects
c[i]= Number of columns of room number i
r[i]= Number of rows of room number i
Capacity[i] = c[i]*r[i] students[j] = Amount of student of subject j
Max[x] = Total number of columns of x sizes row;
Min[x] = Maximum usable Max[x] for any subject; Row= it is an array which contains the row sizes
We have categorized this problem into three parts. The first part is room specification; second one is column distribution and last one is room and column assigning. We have written algorithms for those three parts separately. Each algorithm has some specific input and output, but all of those algorithms are working together to achieve one goal; that is proper seating arrangement.
1)Description of the pseudo code of Room specification
Algorithm:This algorithm can specify rooms for exam seating. To make proper exam timetabling sometime it necessary tokeep some empty seats. Sometime this number of seats is very large. It may larger then some room capacity. In this situation, it is essential to specify those rooms which will be kept empty at the exam for qualitiful exam seating arrangement. The room specification algorithm is doing this job. In this research
– Calculation of extra seats from room information and exam information is in step 1.
A function is used for specifying rooms for keeping empty at the time of the exam is in step 4. Step 4a is checking if extra seats are equal to the capacity of the room. 4b is used for the end of the loop; 4c and 4d keep record for the best solution andalso call this function again by setting new parameters by analyzing the current condition of extra seats and rooms. – Update the list of extra rooms if the extra seat doesn’t become zero in step 5. At the end of this algorithm we found the minimum extra seats and some extra rooms.
1)Description of the pseudo code of Column Allocation Algorithm:
This algorithm ascertains the column which will assign to the subject. At first it calculates the total and the maximum possible amount of columns for each subject. Then different sizes of columns will assign for each subject. To do so the algorithm takes one column size and calculatesmaximum number of seats that can be used to assign to the subject. If the exact amount of seats for one subject can be allocated by using one size of columns it is assigned otherwise another column size will be used. How many percentages of which column size have already been used is calculated before column allocation for each subject. Based on this result less used column will give priority for assigning to subjects.
-In step 2 it calculates the number of columns and maximum usable columns for any subject.
– Step 3 creates link the main column allocation unit and pre process the input set for that unit. 3a allots extra seats to subject if essential and possible. If extra seats are not available then 3b add a room for getting extra seats and add extra seats to the subject which require.
-A function who allocates the column to the subject is written in step 4. 4a and 4c are for checking the ends of this Frecursive function; 4d and 4e are for checking the column size that will be used, 4f is for calculating how many particular sizes of columns will be used.
3) Description of the pseudo code of Room Allocation Algorithm: From the previous algorithms we have the information about a subject and allocated column size. This algorithm assigns room and column number to the subject based on defined column size. This process will be done in two steps. First, it categorizes the subject based on allotted column size. Second, it assigns subjects to each odd column (based on position). After finishing all of the odd columns it will assign subjects to even columns.
– Step 2 creates from for stores results.
-Step 3b categorizes subjects based on assigned column size; 3c assigns subject to the even number of columns and 3d assigns subject to odd number of columns.