ABSTRACT
In this work,we applied an Integer Programmingapproach to schedulingof resource
persons on National Board for Technical Education (NBTE) accreditation team to a
Polytechnic. The level of compliance of the institution to national minimum benchmark
for academic standards with respect tostaff mix was deduced.The use of Integer
Programming approach and Lingo software in solving the model developed, resulted in
considerable drop in accreditation cost from four million, seven hundred and forty
thousand naira only (N4,740,000.00) to two million, eight hundred and seventy three
thousand, eighthundred and twenty seven naira only (2,873,827). The adoption of
Integer Linear programming has eliminated the bias and bottlenecks associated with the
current spreadsheet approach used by the Board. In view of her inherent advantage, we
recommend the use of Integer Linear programming approach using Lingo Software for
future scheduling of resource persons on accreditation visits by the NBTE.
TABLE OF CONTENTS
Certification ……………………………………………………………………………………………………. ii
Dedication ……………………………………………………………………………………………………… ii
Acknowledgement ………………………………………………………………………………………….. iv
Abstract …………………………………………………………………………………………………………. v
Table of Content …………………………………………………………………………………………….. vi
Chapter one …………………………………………………………… Error! Bookmark not defined.
1.0 Introduction …………………………………………………………………………………………. vii
1.1 Statement of the Problem ………………………………………………………………………. ix
1.2 Objective of the Study ……………………………………………………………………………. ix
1.3 Scope of the Study …………………………………………………………………………………. ix
Chapter Two …………………………………………………………………………………………………… x
Literature Review ……………………………………………………………………………………………. x
NBTE accreditation framework and accreditation team …………………………………………. x
The Purposes of Programme Accreditation………………………………………………………….. x
Key Attributes of NBTE’s Accreditation team ……………………………………………………… xii
Definition of terms ………………………………………………………………………………………… xx
Chapter Three……………………………………………………………………………………………… xxiv
3.0 Methodology: …………………………………………………………………………………….. xxiv
3.1 Model formulation and General solution ………………………………………………….xxv
3.2 An Integer programming model approach …………………………………………….. xxviii
Chapter Four ………………………………………………………………………………………. xxxv
Data Analysis ……………………………………………………………………………………………… xxxv
4.1 Analysis of Integer Programme results……………………………………………………… 25
5.1 Summary and conclusion ……………………………………………………………………….. 33
5.2 Recommendation …………………………………………………………………………………. 33
5.3 Future Work ………………………………………………………………………………………… 34
Appendix A: Programme Algorithm ………………………………………………………………….. 35
References ……………………………………………………………………………………………………. 38
CHAPTER ONE
Introduction:
Workforce, labour, personnel scheduling or rostering is the process of designing work
timetables for employees to satisfy the demand requirements for its services as observed
by (Hillier and Lieberman, 2005). Different types of mathematical modelling approach
havebeen developed in order to help companies to solve the problemof staff scheduling.
The development of these mathematicalmodels and algorithms involves the following
steps according to Gabor(2004)
· a demand modelling study that collects and uses historical data to forecast
demand for services and converts these to the staffing levels needed to satisfy
service standards,
· consideration of techniques required for a personnel scheduling tool that satisfies
the constraints arising from workplace regulations while best meeting a range of
objectives including coverage of staff demand, minimum cost and maximum
employee satisfaction,
· Specificationof a reporting tool that displays solutions and provides
performancereports.
Effective staff scheduling takes into consideration the different peculiarities of various
staff needs for optimum performance. Scheduling has been applied to different facets of
life especially in the medical profession,police force, airline, transportation, telephone
companies,banksand hospitality industries, all these companies have an uphill task of
maintaining the delicate task of staff scheduling.
Following the advances and progress made in linear programming, we model
scheduling of resource persons that serve in National Board for Technical Education’s
(NBTE) ad-hoc programme accreditation team to Nigerian Polytechnics. The NBTE
currently uses a computer based spreadsheet for scheduling these resource persons for
accreditation visit; this approach has her draw backs and bottlenecks.Management has
expressed concern over the frequent use of some resource persons to the detriment of
others; this worry is shared by other stakeholders who felt that their not being featuredin
any accreditation exercise has a hidden undertone. In view of this, we assert that
adopting a mathematical based model will eliminate the question of bias and
favouritism. This model will provide an opportunity for every qualified resource person
on the Board’s database to participate in accreditation visit to Polytechnics that are due
for the exercise.
The National Board for Technical Education, Kaduna is a regulatory agency charged
with enforcing standards in all technical and technological based institutions outside the
university system. In performing these tasks, she carries out verification and
accreditation visits to institutions under her purview to ensure that standards are upheld
and maintained. When an institution prepares to run a programme either at the National
Diploma (ND) or Higher National Diploma (HND) level, she applies for license to
operate from the Board. The Board constitutes a verification team to ascertain the
resources on ground for the desired programme at the institution. Based on the team’s
satisfaction that the institution meets the minimal requirement to run such
programme(s), NBTE constitutes a team for an initial accreditation to the institution.
Accreditation visits are undertaken to these institutions either at the inception of the
institution or when they are mounting additional programmes in existing institution. If
successful, the NBTE conveys an interim accreditation status on the institution which
allows the institution to admit students for a period of two years only, and thereafter she
applies for final accreditation that is renewable after every five years. However, within
this period, application for new programmes can always be entertained, on the request
of the institution. Accreditation visits to institutions are at the National Diploma (ND)
or the Higher National Diploma (HND) levels or both for the respective programmes.
For every accreditation visits, a team is constituted comprising an NBTE staff (who is a
subject officer for the designated programme), member of a professional body/industry
and resource persons drawn from the academia who are conversant with programmes
that are due for verification or accreditation visits as resource persons. The Board
maintains an online database of resources persons in diverse discipline that she can
draw from for purposes of accreditation visits.
1.1 Statement of the Problem
· Determine effective means of selecting NBTE’s accreditation Team
· Determine the quality of assessors work
· Monitor the team’s performance at these institutions
· Determine minimum cost of accreditation exercise
1.2 Objective of the Study
· Develop a linear programming model for NBTE’s accreditation team that
minimizes the cost of accreditation.
· Develop a model for assessing the staff mix in the institution
1.3 Scope of the Study
This study covers accreditation team scheduling with particular reference to
National Board for Technical Education, Kaduna ad-hoc programme
accreditation team. Data of year 2014 from Delta State Polytechnic, Otefe-
Oghara, and the Board’s resource person database were used as case study.
CHAPTER TWO
LITERATURE REVIEW
2.1 NBTE accreditation framework and accreditation team
This Framework addresses the accreditation of Polytechnic programmes in Nigeria.
Accreditation is the primary assurance of quality in the preparation of students and
programmes in the respective institution across the country. The results of accreditation
exercise gives credence to quality assurance to all stake holders in the educational
sector and the general public.
2.2 The Purposes of Programme Accreditation
Programme accreditation is the process of verifying the quality of each programme
content, her staff, student and infrastructural requirement for the award of National
Diploma (ND) and Higher National Diploma (HND). The essence is to ascertain that
staff who teach, possess the requisite knowledge, skills and ability to impact knowledge
at the various programmes levels. It equally ensures that the institution conforms to the
set minimal standard for such programmes requiring accreditation.
The first primary purpose of programme accreditation is to ensure accountability to the
public, the students, the educational sector and the general public. The overall interest is
to establish that our various institutions are dynamic, conform to emerging trend in their
respective fields and are sensitive to her environmental needs by introducing
programmes with local content component into her curricula.
A second purpose of accreditation is to ensure that programmes are of high quality,
effective and provide experiences that are consistent with tertiary institution. The NBTE
has the statutory responsibility for adopting accreditation standards and benchmarks
which describe levels of quality that it deems necessary for quality assurance. The
accreditation team attempts to assess the assessor by ensuring that laid down standards
are followed in appointment, promotion and that evidence of requisite enhancement
training are undertaken for the purpose of growth and productivity.
The Accreditation system is oriented to issues of quality. During a review, reviewers
obtain evidence that relates to the educational quality of programmes and policies
governing the programmes. Through experience, expertise and training, the
accreditation team are skilled at discerning the important from the unimportant in
programme preparation. The findings and recommendations of accreditation team focus
on important matters of quality in the respective programmes. The findings of the team
are evidence based and afford the respective institution opportunities to rectify some of
the observed anomalies within a record time.
A third purpose of the accreditation team is to ensure adherence to standards. The
standards are designed to ensure that each programme is at tandem with current
curriculum in Nigeria. Through the accreditation process, sponsors of respective
institution’s programmes show evidence that their programmes conform to requisite
standards.
The fourth purpose of the accreditation programme is to support programme
development and enhancements. The NBTE accreditation team attempts to enforce
standards by harmonizing the various reviews and decisions of the various coordinators
that contributed to the preparation of programmes. Each institution strives to meet
NBTE’s minimal accreditation requirements. Where theirs is noticeable shortfalls,
appropriate suggestion are outlined, the essence is to ensure that respective institution
do the right thing always and not resort to cutting corners. When institutions fall short
of accreditation requirements, they are given opportunities to remedy such
shortcomings and invite the Board for verification.
2.3 Key Attributes of NBTE’s Accreditation team
These attributes pertain to the development of programme standards, the initial
accreditation, full accreditation and subsequent reviews.
First Attribute: The Character of Accreditation team.
Professional teachers drawn from respective tertiary institutions, professional bodies
and the industry should hold themselves and their peers accountable for the
enforcement of quality in any particular programme in the Polytechnic sector.
Practising professionals are involved in the entire accreditation process. They are
involved initially in the critique of curricula for the respective programmes before
adoption, at accreditation; they conduct reviews, and make accreditation decisions.
Participant in accreditation team have experience, expertise and training that are
appropriate for their specific roles in the team. During accreditation, decisions emerge
from consultative procedures that reflect the consensus of the professional participants
present for the exercise. The NBTE’s subject officer serves as a guide to the team and
takes custody of all emerging reports from the programme.
Second Attribute: Knowledgeable Participants.
The accreditation team relies on the quality of the decision making at each step in the
process by invited professional. Quality assurances are provided through the
participation of individuals who possess knowledge, skills and broad expertise and who
participate in the system in various roles, including policy development, policy
implementation, programme assessment, technical support, and professional
preparation. Periodically, the NBTE organises refresher workshops for resource persons
to keep them abreast of the Board’s requirement and policy adjustment in the
educational sector.
Third Attribute: Breadth and Flexibility.
For institution sponsors to be effective in a dynamic state, they must be creative and
responsive to the changing needs of prospective programmes, the communities and
students they serve. The NBTE seeks to enforce minimum standards in all her
programmes and encourages institution to develop local content that will meet the
peculiarity of their environment and further enrich her curricula. The Board encourages
innovation, expertise and ingenuity that are beneficial to students and the community.
Fourth Attribute: Intensity in Accreditation.
The Accreditation team focuses on educational quality and effectiveness. While
allowing and encouraging divergence, the process should also be exact in assembling
key information about critical aspects of educational quality and effectiveness. The
scope of accreditation team is comprehensive, the information generated by the review
processes should be sufficient to yield reliable judgments by policy makers in the
educational sector.
Accreditation team’s decisions are based on information that is sufficient in breadth and
depth for the results to be credible and dependable. Accreditation team understands the
components of the programme under review and the types of standards-based evidence
that substantiate its overall quality and effectiveness.
Fifth Attribute: Efficiency and Cost-Effectiveness.
The accreditation team seeks to fulfil its purposes efficiently and cost-effectively. She
reviews procedures, decision processes and reporting relationships are streamlined.
There are costs associated with establishing standards, training reviewers, assembling
information, preparing reports, conducting meetings and checking the accuracy of data
and the fairness of decisions. Minimizing these costs is an essential attribute of
accreditation exercise, but efficiency must not undermine the capacity of accreditors to
fulfil their responsibilities to the public and the Polytechnic sector. Accreditation costs
are borne by the institution and the regulatory body (NBTE). The stipends paid to
accreditation team members are reviewed periodically by Board in line the prevailing
Federal Ministry of Education guidelines.
Linear programming is a mathematical modelling technique designed for dealing
typically with problems of allocating limited resources among competing activities in
the best possible way in agriculture, engineering, social sciences, education, health
systems, military, industry, assignment, economics, government and transportation. It is
one of the techniques in the field of Operations Research developed for solving
problems that have a particular mathematical structure. In many of such problems in
Operations Research, the aim is either to maximize or minimize some objective
functions subject to certain constraints imposed on the resources available as observed
in (Sharma, 2009). For this study a special form of Linear Programming called integer
programming is applied, here all the decision variables are integers. We further consider
a special form of Integer Programming formulation called the binary integer
programming, where the values of the decision variables are zeros and one.
In this study we are looking at applying Linear Integer Proramming technique to
schedule staff to carry out specific assignment. We shall now review some related work
in the literature that will help us develop the model we plan to adopt in this study.
Gloyer (1986) studied a general employee scheduling problem using the technique of
management science and artificial intelligence. He generated solutions of exceedingly
high quality in very modest time. It is believed that similar gains may be possible for
other combinatorial zero-one applications.
Ipet al (2010) studied staff scheduling for airport service planning using integer
programming. Theydeveloped an optimization approach to improvethe manual
maintenance scheduling process in airport planning. They showed that planning and
scheduling can bring about a more efficient and effective process.
Sabet (2005) worked on web based staff scheduling, which demonstrated that online
web based scheduling involves assigning workers to task on a one-to-one basis; the
objective is to ensure that all jobs are completed at minimal cost within stipulated time.
Staff scheduling tools does a better job of balancing an organisation’s needs with staff
needs, gives staff greater access to scheduling, self-scheduling and staffing, and offer a
significant return on investment, while providing high level reporting and centralized
staffing for effective control.
Burke et al (2010) studied a hybrid model of Integer Programming (IP) and Variable
Neighbourhood Search (VNS) for highly-constrained nurse rostering problems in a
modern hospital environment. The basic variable neighbourhood search acted as a post
processing procedure to further improve the Integer Programme’s result solutions
obtained.Very promising results were reported compared with a commercial genetic
algorithm and the compared result demonstrates that our hybrid approach combines the
advantages of both the IP and the VNS to beat other approaches in solving this type of
problems.
Fernandez-Viagas and Framinan (2014) addressed the issue of simultaneously
scheduling tasks in a project and assigning staff to these tasks, taking into account that a
task can be performed only by employees with the requisite skills, and that the length of
each task depends on the number of employees assigned. They applied integer
programming model with extensions for the problem inquestion to cope with different
situations. Due to the complexity of the integrated model, a simple GRASP algorithm
is implemented in order to obtain good, approximate solutions in short computation
time.
Trilling et al (2006) studied Nurse scheduling using integer linear programming and
constraint programming, while trying to reduce cost and to optimize the use of
resources, hospitals were prompted to regroup facilities and human resources,
especially in the surgical suite. The team focuses on Anaesthesiology Nurse Scheduling
Problem(ANSP) which constitutes one of the most shared resources. The objective is to
maximize the fairness of the schedule.
Kassa and Tizazu (2013) In their work in hospitality industry applied integer
programming model that determines an optimal weekly shift schedule for the Hotel’s
engineering department personnel whichsatisfied several constraints including weekly
rest requirements per employee, rest requirements between working shifts per
employee, required number of personnel per shift, and other constraints.
The model was implemented on an excel solver routine that enabled the company’s
personnel department management to develop a fair personnel schedule as needed and
to effectively utilize personnel resources while satisfying several technical, legal and
economic requirements. These encouraging achievements showed the gains other
organizations can derive by introducing operations research approach in their
management planning and decision making systems.
Mohamad and Said (2013) used integer linear programming approach to scheduletoll
booth collectors’problem. Theydeveloped a general daily staff scheduling problem with
hourly requirement patterns with illustrative example for full and parttimers using
LINDO software.
Sigurðardóttir (2011) worked on near-optimal staff scheduling using mixed integer
programming, theyobserved that companies with employees working on irregular
schedules presents a challenge. They showed results from four Icelandic companies
and comparing it to a local-search based algorithm. The results showed that it was
possible to use mathematical programming techniques for staff schedules, though a bit
problematic with multiple and often changing objectives and goals.
Herowati (2005) worked on multi shifts and break windows in employees
scheduling.He utilized Integer Programming model for optimal shift scheduling with
multiple shifts and break windows to determine the optimal number of employees
needed in every shift and break assignment. Obtaining the optimal number of
employees helped the management in developing a recruitment plan.
Natashia (2010) studied the scheduling of maintenance for Hunter Valley Coal Chain.
Based on a network flow model of the system, a mixed integer programming
formulation was proposed for the planning task,the resulting large scale model obtained
could not be solved directly by a general purpose solver and they proposed two steps. A
reduction in the number of binary variables by choosing a representative subset of the
original variables of the problem and a rolling horizon approach that shortens the
problem.
Júdice et al (2005) studied workforce planning in a lotsizing mail processing
environment. Their work analysed a treatment area (registered mail) where mail objects
are treated in a chain production process. The objective is to minimize the costs with
human resources needed in the process, linked with the lot sizing production plan, by
matching staffto work requirements. An integer programming formulation was
proposed that considered small, average and high daily amounts of mails that arrived at
a particular treatment area.
Nissen (2009) worked on staff scheduling with Particle Swarm Optimisation (PSO) and
Evolution Strategies,he used a scenario from logistics to show that modern heuristics,
and in particular particle swarm optimization (PSO) can significantly add to the
improvement of staff scheduling in practice. Rapid, sub-daily planningwas the focus of
the research and it offered considerable productivity reserves for companies.
Davood (2015) studied the implementation of the theory of constraints (TOC) rules for
job-shop systems to advance the state of research on constraint scheduling. A number of
simulation scenarios were discussed providing insights into the master production
schedule (MPS), the drum–buffer–rope (DBR) scheduling method, the role of setup
times in scheduling, the impact of free products (those that do not use constraint
resources) on throughput and the effect of priority rules in resource assignment to free
products. Moreover, optimization techniques were used to find optimal and/or
satisfactory solutions for input variables in the simulation experiment. Their findings
suggested that the current rules of thumb should be modified for real-world applications
and complex job-shop systems.
Labidi et al. (2014) deployedscheduling to Information Technology Staff (IT) at a
Bank.Due to the large number of conflicting constraints, a multi-objective programming
model was proposed to automate the schedule generation process. The suggested
mathematical model was implemented using Lingo software. The results indicated that
high quality solutions can be obtained within a few seconds compared to the manually
prepared schedules.
Thomas (2013) based his work on scheduling algorithm with optimization of employee
satisfaction. He developed an algorithm for weekly workforce scheduling with 4-hour
discrete resolution that optimizes for employee satisfaction. Parameters of employee
availability, employee preference, required employees per shift, and employee weekly
hours were considered in a binary integer programming model designed for automated
schedule generation.
Beaulieu et al.(2000) while scheduling physicians in emergency room presented a
mathematical programming approach. They used multi-objective integer programming
theory to approach the problem. When the results of the mathematical models are
compared with schedules it produced and those generated by a human expert, the result
was remarkable. The mathematical programming approach accommodates more
variable and results turn out faster than previously obtained.
Sriram and Haghani (2003) showed that aircraft maintenance scheduling is an easily
understood but difficult to solve problem. Given a flight schedule with aircraft assigned
to it, the aircraft maintenance-scheduling problem is to determine which aircraft should
fly which segment and when and where each aircraft should undergo different levels of
maintenance checks as required law. The objective was to minimize the maintenance
cost and any costs incurred during the re-assignment of aircraft to the flight segments.
They opined that heuristic procedure provides good solutions in reasonable computation
time to the scheduling problem.
Christine(2013) noted that crew scheduling problem involves the process of assigning
crew to operate a designated route. They proposed a methodology to determine the most
efficient and least costly way of crew pairing optimization, using algorithm
optimization with Java programming language to solve the crew scheduling problems.
The algorithm was able to solve the main problem that is related to crew route
generation and balancing.
Chuin and Aldy (2012) worked on security patrol scheduling with the introduction of
elements of strategic randomness in the model on a mass rapid transit rail network.
Their mathematical model randomized the start – finish time, break time and frequency
of visits for improved efficiency.
Barnhart et al.(2003)showed that airline crew scheduling when delayed or has reached a
limit on its flying time for a duty or pairing would be highly desirable to have an
alternative crew available with which it could swap one or more flights. In addition to
the traditional objective of minimizing pairing costs, they introduced a new objective of
maximizing the number of opportunities for crew swapping. Thus, their model is a bicriteria
optimization model. Computational results showed that there are crew schedules
with only a slightly higher crew cost, it can be combined with stochastic models that
minimize expected cost or incorporate penalties.
In this work, we are adopting integer programming problem for finding the minimal
optimal amount of money that the NBTE will expend in recruiting resource persons for
accreditation exercise to Delta State Polytechnic, Otefe-Oghare.
Definition of terms
DECISION
VARIABLES
Decision variables are the known variables whose
values when determined influences the value of
the objective function and are used in making
viable decision on the problem in
question.Typically we will determine their
optimum values with an optimization method. In a
general model, decision variables are given
algebraic designations such as ıı, ıı, ıı,. . .ıı The
number of decision variables is n, and ı ıı is the
name of the jth variable. In a specific situation, it
is often convenient to use other names such
as ı ıı or ıı or ı(ı,ı) .
OBJECTIVE
FUNCTION
The objective function evaluates some
quantitative criterion of immediate importance
such as cost, profit, utility, or yield. The general
linear objective function can be written as
Here is the coefficient of the jth decision
variable. The criterion selected can be either
maximized or minimized.
CONSTRAINTS A constraint is an inequality or equality defining
limitations on decisions. Constraints arise from a
variety of sources such as limited resources,
contractual obligations, or physical laws. In
general, an LP is said to have m linear constraints
that can be stated as
One of the three relations shown in the large
brackets must be chosen for each constraint. The
number is called a “technological coefficient,”
and the number is called the “right-hand side”
value of the ith constraint. Strict inequalities (<
and >) are not permitted. When formulating a
model, it is good practice to give a name to each
constraint that reflects its purpose.
NONNEGATIVITY
RESTRICTIONS
In most practical problems the variables are
required to be nonnegative;
This special kind of constraint is called a nonnegativity
restriction. Sometimes variables are
required to be non-positive or, in fact, may be
unrestricted (allowing any real value).
LINEAR
PROGRAMMING
MODEL
Combining the aforementioned components into a
single statement gives:
The constraints, including non-negativity defines
the feasible region of a problem.
PARAMETERS The collection of coefficients for all
values of the indices i and j are called the
parameters of the model. For the model to be
completely determined all parameter values must
be known.
Do you need help? Talk to us right now: (+234) 08060082010, 08107932631 (Call/WhatsApp). Email: [email protected].
IF YOU CAN'T FIND YOUR TOPIC, CLICK HERE TO HIRE A WRITER»
