There is a well-known class of linear programming problems which are commonly referred to as the “assignment family”. The assignment family is a large class of problems which can generally be defined as an application used to assign “individuals” to “tasks” (or tasks to machines, etc.) subject to restrictions with the objective of minimizing the total cost of the assignment made (Kaye, 1985)  . The classical assignment problem (also referred to as the linear assignment problem) can be regarded as the most basic sub-class in the assignment family, the linear assignment problem requires all the tasks to be assigned to an agents on one-to-one basis, in the best combination in order to minimize cost. Therefore, it is assumed that each task can only be assigned once to an agent and each agent can only undertake one task. The other classes in the assignment family can be seen as an extension of the classical (linear) assignment problem. All classes of assignment problem have the following characteristics: 1) The overall objective is to minimize the cost of assigning tasks; 2) Binary decision variable are used to indicate when a task is completed; 3) Each task can only be assigned once; and 4) Functions must be linear or have the ability to be converted into a linear nature.
The assignment problem (AP) is used worldwide in solving real world problems. An assignment problem plays an important role in industry and other applications. It is one of the well-studied optimization problems in management science and has wide applications in both manufacturing and service system (Srinivas and Genesan, 2015)  . The assignment problem is one of the fundamental combinatorial optimization problem (or operation research) in mathematics, it is a particular case of transportation problem where the sources are assignee and the destinations are task (Ahmad and Ahmad, 2014)  .
Therefore, assignment problem is nothing rather than a balanced transportation problem in which all the supplies and demands are equal to one and involves efficient assignment of: jobs to machine, people to projects, contract to bidders, salespeople to territories, vehicles to routes, product to factories, development engineering to several construction site, etc. The objective is to minimize total cost or total time of performing the tasks at hand. One important characteristic of assignment problem is that only one job or worker is assigned to one machine or project. Each assignment problem has associated with a table or matrix, generally the rows contains the objects or people we wish to assign and the column comprise the things or tasks we want to assign to. The numbers in the table or entries in the matrix are costs associated with a particular assignment.
The specific problem in view is to model the staff-subjects allocation of Dutse Model International School of Jigawa State as an assignment problem and to find the optimal assignment (allocation) that will maximize the educational quality. The school existed for so many years as Dutse Capital School which later was renamed as Duste Model International School due to the advancement and the societal needs of the people in 2001. The Dutse Model International School was officially commissioned by his excellency General Ibrahim Badamasi Babangida (GCFR) the former president of the Federal Republic of Nigeria on Sunday 26th August, 2012 AD (9 Shawwal, 1433 AH). The school has a total enrollment of 1365 students comprising boys and girls. The school participated and received a numerous number of Mathematical medals and awards among which includes:
Ø National Cowbell Mathematics Competition Senior Category 2nd Position (2015).
Ø National Quiz Mathematics Competition on Nigerian Capital Market 2nd Position (2014).
The research is of paramount importance as it seeks to find the optimal assignment schedule of staff-subjects allocation that will helps in promoting Teaching-Learning Processes, thereby improving the educational quality and national development in general. The research covers Dutse Model International Secondary School of Jigawa State. Therefore, the broad aim of this research is to determine the optimal assignment (allocation) schedule of five subjects to five different staffs (Teachers), on one-to-one basis. By applying the Hungarian method and determining the best way of allocating subject-staff, it will, to a large extent enhance the number of mathematical medals and awards.
The paper is structured into six parts: part one cover the introduction; the second part dealt with literature review; the third part dwells on material and methods; the fourth part captures the analysis and results; fifth part concludes the paper.
2. Literature Review
Linear Programming (LP) can be defined as a mathematical method of determining an optimum assignment of interdependent activities, given the availability of resources (Loomba, 1964)  . Linear Programming formulations were first recognized in the late 1940’s when G. B. Dantzig designed the “Simplex method” for solving problems arising within the US Air Force (see Chevatal, 1983  ; Ignizio, 1982  ). Since then, the development of linear programming has made it an extensively used technique for solving a wide range of managerial problems. The linear programming model is a structured set of mathematical relationships (e.g. equalities, logical conditions), which represent an abstraction of the real problem under consideration (Williams, 1995)  .
The assignment problem as a class of linear programming problem was developed and published by Harold Kuhn in 1955, who gave the name “Hungarian Method” because the algorithm was largely based on the earlier work of two Hungarian mathematicians: Denes Koning and Jeno Egervary. However, Simon (2012)  used assignment problem techniques to model and solves the staff-subject assignment problem as an assignment problem. The objective of the model is to maximize the educational quality; the model developed could be adopted for any problem that can be modeled as an assignment problem. Furthermore, De and Yadav (2012)  studied two different types of assignment problem: conventional and fuzzy assignment problems and develops an approach to solve the fuzzy assignment problem where the cost is not deterministic numbers but imprecise ones. Here the elements of the cost matrix of the assignment problem are triangular fuzzy numbers. In conventional assignment problem, the cost is always certain. Also, Ghadle and Muley (2013)  introduced a new approach to assignment problem namely “Revised Ones Assignment Method (ROA)” for solving a wide range of problem. In ROA Method defines assignment matrix, then reduced the matrix till it has least one in each row and column.
Moreover, Thiruppathi and Iranian (2015)  presented an innovative method named by TVAM is proposed to find an optimal solution for any assignment problem in single stage. Here the assignment is solved to get optimal solution directly. Micheal et al., (2008)  considered the assignment problem in the context of network systems where the main challenge is dealing with the lack of global information due to the limited communication capabilities of agents. The algorithm is an extension to the parallel auction algorithm. Moreover, Majumdar (2013)  proposed interval Hungarian method and consider interval analysis concept for solving interval linear assignment problem in the cost matrix is not always crisp. Likewise, Ahmad and Ahmad (2014)  presented a new method for finding an optimal solution of a wide range of assignment problem directly. A numerical illustration is established and the optimality of the result yielded by this method is also checked.
Besides, Kotwal and Dhope (2015)  proposed a modified assignment model for the solution of assignment problem with the help of numerical examples or problem is solved to show its efficiency and also its comparison with the Hungarian method is shown. A new cost is achieved by using unbalanced assignment problem. Also, Srinivas and Ganesan (2015)  presented a fuzzy assignment problem has been transformed into Crip assignment problem in the linear programming problem form and solved by using Branch and Bound and Robust’s ranking method for the fuzzy numbers. Moreover, Semih et al., (2008)  considered a distribution-type warehouse assignment problem that various type of products were collected from different suppliers for storing in the warehouse for a determined period and for delivery to different customers. Their study was to design a multiple-level warehouse shelf configuration which minimized the annual carrying costs.
Similarly, Maxon and Bhadury (2001)  studied a multi-period assignment problem with repetitive tasks and tried to introduce a human element into the analysis. Their objectives was to minimize a combination of the assignment cost and the “boredom” that the results when a workers are required to repeat the same task in consecutive periods. A mathematical model was proposed and a simple iterative heuristic was developed and implemented in Excel. Furthermore, Mingfang (2010)  studied the Weapon-Target Assignment (W.T.A) problem, which has wide application in the area of defense-related operation research. This problem calls for finding a proper assignment of weapons to target such that the total expected damaged value of the targets to be minimized. The WTA problem can be formulated as a nonlinear integer programming problem which is known to be NP-complete. Also, Liong et al., (2006)  solve a special Quadratic Assignment Problem (Q.A.P) which consists of deciding the assignment of customers to loading positions as well as fulfilling their demands, i.e. a double problem. They applied the Greedy Algorithm to set a good initial solution, and then a modified Genetic Algorithm to find the best solution to the problem. Besides, Simon (2012)  modeled the staff subject’s assignment as an assignment problem. The developed model can be adopted for any problem that can be modeled as an assignment problem. A wrong decision may result in significant loss of value due to understaffing, under-qualification or over-qualification of assigned personal and high turnover of poorly matched workers.
However, Sarin et al., (2010)  develop the integer programming formulation for a university-timetabling problem with the objective of minimizing the total distance travelled by the lecturers from their offices to the classrooms. Similarly, Oladokun and Badmus (2008)  studied about assigning a number of courses to classrooms taking into consideration constraints like classroom capacities and the university regulations and using the integer linear programming (ILP) to solve the problem.
The limitations of previous works: Thiruppathi and Iranian (2015)  used single stage assignment problem while ours is multiple stage assignment; Micheal et al., (2008)  has limited communication capabilities of agents; Majumdar (2013)  used interval Hungarian method whereas Kotwal and Dhope (2015)  shows efficiency and comparison with the Hungarian method; also, Srinivas and Ganesan (2015)  presented a fuzzy assignment problem. While, Simon (2012)  is consistent to some extent with our work but a wrong decision may result in significant loss of value due to understaffing, under-qualification or over-qualification of assigned personnel and high turnover of poorly matched workers. The only difference is we consider staff-subject allocation which will help in promoting teaching-learning process, thereby improving educational quality.
3. Material and Methods
The study covers data gathered from the period of two academic sessions (2014/15-2015/16). One of the most widely used methods for solving assignments is called the “Hungarian Method” developed and published by H. W. Kuhn in 1955 (see Kuhn, 1955)  . This method is named after the Hungarian mathematicians D. Koning who in 1916 proved the theorem necessary for the development of the method.
The Hungarian method (also known as Flood’s Technique or the reduced matrix method) of assignment problem, it provides us with an efficient means of finding the optimal solutions without having to make direct comparison of every option. It operate on a principle of matrix reduction which means that by subtracting and adding appropriate numbers in the cost table or matrix, we can reduce the problem to a matrix of opportunity cost (opportunity cost show the relative penalties associated with assigning any workers to a job or least cost assignment). If we can reduce the matrix to a point where there is one zero element in each row and column, then it is possible to make optimal assignment, for example, assignment schedule are made in such a way that the opportunity cost for assignment is zero. The Hungarian method of assignment problem is typically minimization case (Singh et al., 2012)  .
3.1. Assignment and Allocation Problem
The assignment problem is a special type of transportation problem which is also a resources allocation problem. Here, we have n-jobs to be performed by n-machines and the problem is how to distribute the job to the different machines involved. This problem has extensive applications in allocation problem where different entities are allocated or assigned to other entities. The objective function in assigning different jobs to different machines is to find the optimal assignment (allocation) that will minimize the total cost or time taken to finish all the jobs by the machines.
The assignment problem can be formally stated as follows: Given n-tasks and n-machines, the problem is to assign or allocate the tasks and machine such that each task is assigned to exactly one machine and each machine to only one task. There is a cost of allocating ith task to jth machine which is denoted by [cij] and the objective is to minimize the total cost or time of this allocation.
3.2. General Formulation of Assignment Problem
Consider the problem of assigning n-jobs to n-machines, job i when assigned to machine j incur a cost of Cij for and and the objective function is to assign (allocate) jobs to machines on one-to-one basis (i.e. one machine one job), so that the total cost is minimum.
3.2.1. The Binary Decision Variables
The binary decision variable in assignment problem model holds only for the binary digits.
3.2.2. Objective Function
The function to be minimize subject to the given constraints is called the objective function and denoted by letter Z. Consider the allocation of n-jobs to n-machines which is associated with a cost Cij and let Xij be a binary decision variable for this assignment. Since we assumed that the total cost function is linear. Therefore, the total cost function of this assignment is given by Cij × Xij. The objective function to be minimized is given by:
The constraints are conditions that force the machine assigned to meet the demand of the job. However, an assignment problem is a special case of transportation problem model in which the workers (machine) represent the source origin and the tasks (jobs) represent the destination. In assignment problem the machines and the jobs constraint are unity (Ragsdale, 2010)  .
1) Machine constraint:
2) Job constraints:
for all and
The condition that is satisfied since or 1 for i, j.
Let Xij denote the assignment of ith job to jth machine and Cij denote the time or cost of effective assignment ith job to jth machine for and .
Then, the assignment problem can be formulated below:
= The cost or time of assigning job i to machine j (monetary unit, time unit)
n = Equal number of machines and jobs available
3.3. The Assignment Problem Matrix
Each assignment problem is associated with a table or a matrix called the cost or effectiveness matrix. Generally, the rows contain the workers or machines we wish to assign and the column comprise jobs or tasks we want to assign to them. Consider the problem of assigning n-jobs to n-machines and the overall objective function is to minimize the cost or time in such a way that each machine is associated with only one and only one job. The cost matrix [Cij] is given in the Table 1.
The cost matrix of the assignment problem is the same as that of a transportation problem except that the availability at each resources and the requirement at each destination is 1.
3.3.1. A Balanced Assignment Problem
The assignment problem is to be balanced if the cost matrix has equal number of rows and columns or equivalently, if the given problem is a square matrix (i.e. n × n matrix). Otherwise is said to be unbalanced, a dummy variable must be added to balance the problem.
Table 1. The matrix table for assignment schedule.
3.3.2. Method for Solving Assignment Problem
There are numerous methods for solving linear assignment problems from the general simplex algorithm to complex techniques. The most famous specific method for solving assignment problem is called the “Hungarian Method”. The method provides us with an efficient and effective way to get an optimal assignment that will minimize the cost or time.
According to Simon (2012)  assignment problem model comes under the class of linear programming model, which is similar to transportation problem model with an objective function of minimizing the time or cost of manufacturing the products by allocating one job to one machine or one machine to one job or one destination to origin or one origin to one destination only. Basically, assignment problem model is a minimization model. If we want to maximize the objective function, one of the two methods is possible; subtract the entire element in the matrix from the highest element in the matrix, or multiply the entire matrix by −1.
1) Balanced Assignment: Assignment problem is said to be balanced if there is equal number of rows and column or equivalently, if the given problem is a square matrix (i.e. n × n matrix).
2) Unbalanced Assignment: The assignment problem is said to be unbalanced if it is not balanced.
3.3.3. Solution Algorithm for Solving Assignment Problem
The algorithms for Hungarian method of assignment problem are summarized below:
Step 1: Find the cost matrix if it not given.
Step 2: Find the minimum cost of allocation in each row and column.
Step 3: Perform row reduction process that will create an equivalent cost matrix that has zero element(s) in every row by subtracting the smallest cost element(s).
Step 4: Perform a column reduction process if in the cost matrix has any column without zero elements by subtracting the smallest element in that column.
Step 5: If a single machine is assigned to more than one jobs, then go to step 6 else go to step 7.
Step 6: Carryout crossing of zeros by drawing minimum number of lines to cross all zeros. Then, select the smallest of uncrossed elements and subtract it from every other uncrossed element and add it to every element at the intersection of two lines.
Step 7: Make job allocation to machine.
4. The Analysis and Results
The head of the staff has the problem of allocating teachers to five different subjects which includes: Mathematics, English, Physics, Chemistry and Biology offered by science class in his school. He has availability of five staffs named A, B, C, D, and E graduates teachers who have handled or taught at least one of these subjects in the past two academic sessions and have been evaluated with a score from 0 to 100 (Basic rating = 100) regarding the ability of each staff to each subject respectively. The scores are shown in the Table 2, below.
The problem now is how the head should assign his staff to the subject on one-to-one basis so as to maximize the educational quality of his school in sciences. If he decide to apply the Hungarian method as a criterion for judging who should teach each subject. Since the assignment problem (Hungarian method) deals with minimization problems, the above maximization problem can be reduced to minimization problem by finding the opportunity or regret matrix, as shown in the Table 3.
Table 2. Staff rating scores.
Table 3. Opportunity matrix scores.
The problem can be modeled below as:
Xij ≥ 0 for all i = 1, 2, 3, 4, 5 and j = 1, 2, 3, 4, 5
Sij = the opportunity score of assigning teacher i to subject j
n = equal number of staffs and subjects
Hence, the problem becomes (as shown in Table 4):
This result is not optimal, so we cannot make assignment. We compute the next step in the algorithm as shown in Table 5.
Since, more than one subject is assigned to one teacher. Then we carry out crossing of zeros by drawing minimum number of vertical and horizontal lines to cover all zeros as shown in Table 6.
Table 4. Row reduction.
Table 5. Column reduction.
Table 6. Crossing of zeros.
The result is not optimal, now select the least of uncrossed element and subtract it from every other uncrossed element and add it to every element at intersection of two lines as shown in Table 7.
This result is optimal, so we can make the allocations.
(A, English) Þ Teacher A → English
(B, Mathematics) Þ Teacher B → Mathematics
(C, Biology) Þ Teacher C → Biology
(D, Physics) Þ Teacher D → Physics
(E, Chemistry) Þ Teacher E → Chemistry
Moreover, anywhere we see zero elements, it is possible to make allocation, i.e. we can allocate B Mathematics and find another possible space for C. We allocate only A to take English; B for Mathematics; C, we allocate Biology; staff D can be allocated either Physics or Chemistry; and staff E can be allocated either Chemistry or Physics.
The total minimum opportunity that will maximize the total educational quality is given below:
Using Equation (4.1) above we have: Z = 84. Therefore, the total maximum effectiveness that will maximize the educational quality is given in Table 8.
Therefore the total maximum effectiveness = 416.
The result from both Hungarian algorithm and that of LINGO computer software package yielded the same optimal outcome. The computer solution by LINGO software shows that the total minimum opportunity that will maximize the educational quality is 84 and the total maximum effectiveness that will
Table 7. The least uncrossed elements.
Table 8. Optimal assignment.
maximize the education quality is 416.
The staff-subject allocation problem of Dutse Model International School has been addressed. The Hungarian algorithm was used to solve the staff-subject allocation problem. The research focused on the use of the assignment problem for selection of staffs to a given subject in order to obtain the best quality results from a teacher. The Hungarian assignment algorithm and Linear Interactive & Discrete Optimization (LINGO) Software Package were used to maximize the total effectiveness of teaching-learning process of the school. The Hungarian algorithm and LINGO software package yielded the same optimal result. The research seeks to solve the real-life problem in the service (educational) industry of staff-subject allocation problem using the Hungarian algorithm. It was found that the solution that gave a minimum and maximum achievable result for assigning a teacher to a subject was 84 and 416 respectively.
The use of Hungarian algorithm approach gives a systematic and transparent solution as compared with LINGO computer software package which produced the same optimal allocation policy of the school staffs to various subjects to gives a better result. The management may benefit from the proposed approach for selection of staff to subject to guarantee optimal result from the staff. We therefore recommend that the assignment problem model should be adopted by the schools in staff-subject allocation so as to get better medal rewards in the future.