**THE DEPARTMENT TEAM TEACHING ASSIGNMENT PROBLEM USING ZERO-ONE INTEGER PROGRAMMING**
Syadatul Syaeda Mat Saleh1\*, Najihan Awang@Ali2, Nurul Husna Jamian3
1,2,3 Faculty of Computer and Mathematical Sciences (FSKM), Universiti Teknologi MARA,
Perak Branch, Tapah Campus, 35400 Tapah Road, Perak, Malaysia
Corresponding author: \*syada326@uitm.edu.my
Received Date: \*date
Accepted Date: \*date
ABSTRACT
*Nowadays, it is more important to be as efficient as possible. Most of the teaching institutions, one of the essential tasks that is carried out every year or every semester are to allocate teaching workload. Teaching workload allocation refers to the teaching staff teaches which subject and group classes. The task is a time-consuming process. The best allocation will be one of the contributing factors to the teaching quality. In current practice to this department, the teaching load allocates manually through a trial-and-error manner using Microsoft Excel. This may lead to unfavourable results.* *In this study, we aim to propose an innovative approach to allocate teaching load to group courses using integer programming which able to optimize the teaching allocation while satisfying the teaching staff preferences and based on department policies as constraints. Primary data were gathered using google form among 12 lecturers with 8 courses and 45 group classes considered. A feasible solution will be solved using LINGO unlimited software and the model serves as the best tool to assist the head of the department to allocate teaching workload. It found that the model proposes as a suitable tool to be employed for teaching allocation.*
*Keywords: integer programming, teaching load, an optimization problem*
# INTRODUCTION
The construction of the table for assigning teaching load that satisfies all constraints and needs in an academic institution and at the same time fulfills as many of the requirements of the teaching staff is an essential task. At most institutions, the task is doing by administrative staff who hold as the head of the department. Formally, assigning the teaching staff to specific courses based on their expertise, preference and experience of teaching is a process for the teaching load allocation. Many approaches have been explored for many years in the higher education sector for timetabling exams and assigning teaching load purpose and one of them is using optimization. Integer programming is one of the optimization approaches and it arises in practically every area of application of mathematical programming. It has been successfully applied to a wide range of problems, such as room assignment, capital budgeting, warehouse location and scheduling problems. Some optimization models have been proposed to get better in teaching load allocation. An integer programming model is a mathematical optimization in which some or all of the variables are restricted to be integers.
A variety of approaches have been undertaken to solve the assignment problem. Breslaw (1976) proposed a linear programming solution to the faculty assignment problem. There are considerable benefits to be gained by using optimization methods in the solution of the university scheduling problem. Waterer (1995) studied a zero-one integer programming model for room assignment at the University of Auckland. The model presented has shown promising results on stimulated data. Daskalaki et al. (2004) developed an integer programming formulation for a case study in university timetabling. They proposed a new integer programming formulation of a timetabling problem in engineering schools of Greek universities. Nordin (2006) described a zero-one integer programming approach to the assignments of lecturers to courses. Qamal and Ayob (2008) proposed a new model for the examination room assignment problem. AL-Abdulhameed (2011) used a linear programming formulation of job-machine assignment problems. The problems solved using transportation algorithms. Xiaobo et al. (2014) developed a teaching load allocation model to optimize the teaching quality taking into account the staff equity. Shohaimay et al. (2016) proposed teaching load allocation using linear programming to find an optimal allocation. Nang and Prabir (2017) studied about the faculty assignment and timetabling using optimization. They proposed an innovative two-steps approach which able to optimize the resource allocation while satisfying the faculty preferences using mathematical models. Fieldsend (2017) studied the university staff teaching allocation with many objective problems confronted by universities worldwide. Mat Saleh et al. (2019) proposed team teaching load using linear programming. The model was able to allocate the teaching load to the right teaching staff, based on their teaching preference.
**Problem Description**
Assigning table for teaching load must be prepare before the new semester begins. Some of the factors need to be considered such as the total number of existing lecturers, the number of courses offered and the total number of groups for each course which is based on the number of students enrolled for a course. Besides that, the table also must fulfill the preferences courses of teaching staff and the needs in an academic institution. However, teaching preferences sometimes are not taken into consideration due to various constraints appeared.
The table for assigning teaching load must develop by the head of the department before the semester started. In current practice, the teaching load allocates manually through a trial-and-error manner using Microsoft Excel. These may lead to bias judgement, get unfavorable courses and lack of standardization of the contact hours per week for academic staff (Mat Saleh and Ismail, 2011).
Therefore, to avoid this kind of problem, a survey was conducted using google form and distributes to all academic staff in the department to obtain the preference course since each lecturer have different expertise and experience in teaching. Primary data has been collected among 12 lecturers with the number of group listed. The contact hours and the number of groups are shown in Table 1 below.
**Table 1: Contact Hours and Number of Groups**
| XXX37 |
4 |
4 |
| XXX23 |
4 |
8 |
| XXX83 |
4 |
14 |
| XXX22 |
4 |
2 |
| XXX10 |
4 |
6 |
| XXX63 |
4 |
7 |
| XXX00 |
4 |
2 |
| XXX21 |
4 |
2 |
| Total group courses |
45 |
|
**The preference weights (rating) from 0 to 3 is elaborate as follows:**
**Weight 0 : The lecturers does not prefer and has no experience to teach the course.**
**Weight 1 : The lecturers does not prefer but has experience to teach that course.**
**Weight 2 : The lecturers prefer but has no experience to teach that course.**
**Weight 3 : The lecturers prefer and has experience to teach that course.**
**The preference weight is one of the contributing factor to teaching quality. Based on the preference weights, the teaching allocation aims to allocate the lecturer to the most suitable courses, based on their expertise, preference and experience. The dataset recorded as shown in the Table 2 below is the preference weight to the group courses.**
**Table 2: Preference Weights (Rating)**
**Application and optimization model**
We model the department assignment problem as an integer programming model which allocate the teaching staff to the group courses. This model was adapted from the basic model, which was developed by Nordin (2006) which allocate the lecturers to the courses. The objective for the model is to maximize the rating of assigning lecturer to the group courses . The rating allocate a teaching staff to a group courses is partially based on their preferences. Each teaching staff filled their preference weight for each course or subject to teach through google form survey. The model aims to assign the staff department to the group courses in order to increase the satisfaction level of the staff.
In order to find an optimal solution, a zero-one integer programming model was applied based on department policies as constraints. A feasible solution will be solved using LINGO optimization software and the model serves as a best tool to assist head of department to allocate teaching loads. T**here are few policies that have to be followed in the department as shown in Table 3.**
**Table 3: Policies**
| Hours of teaching |
12 |
18 |
| Number of classes |
3 |
4 |
To address the problem, we develop a mathematical optimization model. The notation formulation and decision variables is listed below.
Let
: the number of lecturers in the department.
: the number of courses offered.
: the index of the lecturer.
: the index for the course.
: the number of teaching hours for each course of the week.
: the rating given by lecturers teaching the course.
: the maximum number of hours taught by lecturers of the week.
: the minimum number of hours taught by lecturers of the week.
: the courses that have more than one group.
: the group of courses that should be taught by more than one lecturer.
: the number of members in .
The decision variables of the model defined below :
The model is formulated as follows.
Maximize Z = (1)
subject to
, (2)
, (3)
, (4)
, (5)
, (6)
The objective function (1) is to maximizes the total rating of assigning lecturer to the group courses. Equations (2) refers to the maximum contact hours per week for each lecturer and equations (3) refers to minimum contact hours per week for each lecturer . Equation (4) impose that each course is assigned to one lecturer only and equation (5) defines that the courses that have more than one group, it must be taught by at least two lecturers. It is a policy which has been designated by the management. The equation (6) impose the zero-one integer restriction on .
**FINDINGS AND DISCUSSION**
**The optimization model for assigning teaching staff to the group courses have been developed. The main benefit of using such an zero-one integer programming is the model can be efficently solved using LINGO unlimited software and a feasible solution was found. The optimization teaching load allocation is shown in Table 4. In the table, the number four (4) refer to contact hour for each group courses. For example, L1, he/she assigned 3 group courses for code XXX83 and 1 group courses for code XXX22. Meanwhile for L10, he/she assigned 1 group courses for XXX37 , 1 group courses for code XXX83 and 1 group courses for code XXX63.**
**Tabel 4: Optimized teaching load allocations**
**Table 5 below shows the** numbers of hours, group and codes for each lecturer. **It found that all the lecturer are assigned between 12 to 16 contact hours per week and they are allocated between 3 to 4 number of groups as well, as stipulated in department policies. This results revealed that most of the courses efficiently allocated to every lecturer based on their preferences weights and will reduced dissatisfaction among the lecturer.**
Table 5: Numbers of hours, group and codes for each lecturer
| Lecturer | Number of code | Number of group | Number of total hours |
| -------- | -------------- | --------------- | --------------------- |
| L1 | 2 | 4 | 16 |
| L2 | 2 | 4 | 16 |
| L3 | 2 | 4 | 16 |
| L4 | 3 | 4 | 16 |
| L5 | 3 | 4 | 16 |
| L6 | 3 | 3 | 12 |
| L7 | 2 | 4 | 16 |
| L8 | 2 | 4 | 16 |
| L9 | 2 | 4 | 16 |
| L10 | 3 | 3 | 12 |
| L11 | 2 | 4 | 16 |
| L12 | 2 | 3 | 12 |
**CONCLUSION AND RECOMMENDATION**
**One of the key focus to all teaching activities is allocating the successful teaching load among teaching staff in the department, with the same time fullfill the teaching preferences by each teaching staff.** Indirectly, it will enhance the understanding of the courses amongst students because the expertise of the lecturer. **As conclusion, the aim of the proposed zero-one integer programming model is to assist the head of the department to continually improve the construction of assigning table for teaching load. Moreover, the model is very useful and help in improving the teaching quality by allocating the most appropriate lecturers to teach the preference course. It also reduced the satisfaction amongst teaching lecturer when most of them get the same contact hours per week. It is hoped that this model can widely apply for other academic department where it also benefits the head of departments in assigning table arrangements. For further improvement, the mathematical model is suggested to consider many more contraints such as for a lecturer who share a group for only seven week for lecture.**
**REFERENCES**
AL-Abdulhameed F. F. K. (2011). A linear Programming Formulation of Assignment Problems. ***Journal of Basrah Researches (Sciences),* 37(2).**
Breslaw J. A. (1976). A Linear Programming Solution to the Faculty Assignment Problem. *Socio-Economic Planning Sciences*, *10*(6), 227-230. https://doi.org/10.1016/0038-0121(76)90008-2.
Daskalaki S., Birbas T. & Housos E. (2004). An Integer Programming Formulation for a Case Study in University Timetabling. *European Journal of Operational Research,* *153*, 117-135.
Fieldsend J. E. (2017). University Staff Teaching Allocation: Formulating and Optimising a Many-Objective Problem. *In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO’17).*
Mat Saleh S. S. & Ismail W. R. (2011). Pengoptimuman Masalah Umpukkan Pengajaran Berkumpulan Fakulti Menggunakan Kaedah Pengaturcaraan Integer 0-1. *Proceeding in International Seminar on the Application of Science & Mathematics 2011.*
Mat Saleh S.S., Jamian N.H. & Ali N.(2019). Team Teaching Load Using Linear Programming.
*Journal of Computing Research and Innovation (JCRINN), 4(1),8-15.*
Nang L. MA & Prabir, S. (2017). Faculty Assignment and Timetabling Using Optimisation. *International Journal of Computer Science and Information Security (IJCSIS)*, *15*, 29-35.
Nordin Hj. Mohamad. (2006). *A Zero-One Integer Programming Approach to the Assignments of Lecturers to Courses*. Kuala Lumpur: Penerbit UM.
Qamal M. & Ayob M. (2008). A New Model For Examination Room Assignment Problem: Case Study at Universiti Kebangsaan Malaysia. *Proceeding of the International Symposium on Information Technology (ITSim2008), 1193-1198.*
Qu, X., Wang, S., Easa, S., & Liu, Z. (2014). Teaching Load Allocation in a Teaching Unit: Optimizing Equity And Quality. In *Proceedings AAEE2014: Engineering the Knowledge Economy: Collaboration, Engagement & Employability*.
Shohaimay F., Dasman A. & Suparlan A. (2016). Teaching Load Allocation using Linear Programming: A Case Study in the Mathematics Department. *Business Management and Computing Research Colloqium (BMCRC2016)*.
Waterer H. (1995). A Zero-One Integer Programming Model for Room Assignment at the University of Auckland. In Proceedings of the 1995 ORSNZ Conference, 1995.
**Acknowledgments**
**
**The authors are indebted to anonymous reviewers whose comments significantly improve the quality of this work.