universiti putra malaysia a two-stage multi-objective...

25
UNIVERSITI PUTRA MALAYSIA A TWO-STAGE MULTI-OBJECTIVE ALLOCATION MODEL FOR STUDENTS’ ADMISSION INTO ACADEMIC DEPARTMENTS IN A MALAYSIAN PUBLIC UNIVERSITY NASRUDDIN BIN HASSAN FS 2007 62

Upload: others

Post on 27-Oct-2019

6 views

Category:

Documents


0 download

TRANSCRIPT

UNIVERSITI PUTRA MALAYSIA

A TWO-STAGE MULTI-OBJECTIVE ALLOCATION MODEL FOR STUDENTS’ ADMISSION INTO ACADEMIC DEPARTMENTS IN A

MALAYSIAN PUBLIC UNIVERSITY

NASRUDDIN BIN HASSAN

FS 2007 62

A TWO-STAGE MULTI-OBJECTIVE ALLOCATION MODEL FOR STUDENTS’ ADMISSION INTO ACADEMIC DEPARTMENTS IN A

MALAYSIAN PUBLIC UNIVERSITY

NASRUDDIN BIN HASSAN

DOCTOR OF PHILOSOPHY UNIVERSITI PUTRA MALAYSIA

2007

A TWO-STAGE MULTI-OBJECTIVE ALLOCATION MODEL FOR STUDENT’S ADMISSION INTO ACADEMIC DEPARTMENTS IN A

MALAYSIAN PUBLIC UNIVERSITY

By

NASRUDDIN BIN HASSAN

Thesis Submitted to the School of Graduate Studies, Universiti Putra Malaysia, in Fulfilment of the Requirements for the Degree of Doctor of Philosophy

July 2007

DEDICATION

Dengan nama Allah yang Maha Pemurah lagi Maha Pengasihani

Penulis ingin merakamkan jutaan terima kasih di atas pengorbanan serta jasa

kedua ayahanda dan bonda yang telah bersusah payah membesarkan penulis dengan

penuh kesabaran selama ini. Semoga Allah mencucuri rahmat ke atas arwah

ayahanda penulis yang telah kembali ke RahmatuLlah pada tahun 1999 sekembali

dari Tanah Suci Makkah selepas mengerjakan ibadah haji bersama bonda dan moga

Allah memelihara bonda dalam kesejahteraan tanpa ayahanda bersamanya lagi

untuk berkongsi suka dan duka. Moga kedua-duanya beroleh haji yang mabrur dan

kelak ditempatkan di kalangan orang-orang yang mukhlis dan soleh.

Dedikasi ini ditujukan kepada adinda Nur Azlina Abdul Aziz dan keempat-

empat anakanda Abdul Muhaimin, Aimi Nahdiah, Aimi Nadhirah dan Abdul Muiz

yang telah menjadi pendorong utama dan cabaran untuk berjaya. Moga kejayaan ini

menjadi rangsangan kepada mereka untuk tabah dalam pengajian akademik dan

lebih berjaya dalam kehidupan masing-masing.

Penulis juga tidak lupa jasa rakan-rakan pelajar master dan doktor falsafah di

Jabatan Matematik dan Institut Penyelidikan Matematik UPM yang tidak lokek

memberikan buah fikiran, pandangan dan kerjasama.

ii

Abstract of thesis presented to the Senate of Universiti Putra Malaysia in fulfilment of the requirement for the degree of Doctor of Philosophy

A TWO-STAGE MULTI-OBJECTIVE ALLOCATION MODEL

FOR STUDENTS’ ADMISSION INTO ACADEMIC DEPARTMENTS IN A MALAYSIAN PUBLIC UNIVERSITY

By

NASRUDDIN BIN HASSAN

July 2007

Chairman : Associate Professor Mohd. Rizam Abu Bakar, PhD Faculty : Science

We develop, formulate, verify and later validate a multiobjective model of student

admission. Through a two-stage optimization procedure the model seeks to

maximize student admission and student allocation into departments and academic

programmes respectively. In the first stage, we seek to determine the optimal

number of new student intake in all the departments of a given faculty by

observing the departments’ capacity limitations in terms of lecture rooms/halls

availability, budget constraints, number of faculty members and affirmative action

quota. The second stage concerns the application of the same procedure with the

objective of determining the optimal allocation of students obtained in the first

stage into the respective academic programmes within the same department with

constraints unique to each academic programme. Every constraint has its own

weightage besides its level of priority. We then describe the application of the

model to the Faculty of Science & Technology of the Universiti Kebangsaan

Malaysia with its five academic centres/departments and then to the Centre for

iii

iv

Mathematical Sciences with its three academic programmes. For both stages, we

compare the results of the preemptive goal programming model with the non

preemptive weighted goal programming model to analyse the adaptability of the

models to real situations. Sensitivity analyses of the results are done to gauge the

reliability of the model. We hope that the results of the application will

demonstrate the model’s capability to provide an optimal apportionment of student

admission policy with regard to the number of student intake and allocation into

the departmental academic programmes of a faculty, as well as recognizing the

capacity limitations of each academic programme.

Abstrak tesis yang dikemukakan kepada Senat Universiti Putra Malaysia sebagai memenuhi keperluan untuk ijazah Doktor Falsafah

MODEL AGIHAN PELBAGAI MATLAMAT DWI-PERINGKAT BAGI KEMASUKAN PELAJAR KE JABATAN AKADEMIK DI

UNIVERSITI AWAM MALAYSIA

Oleh

NASRUDDIN BIN HASSAN

Julai 2007

Pengerusi : Profesor Madya Mohd. Rizam Abu Bakar, PhD Fakulti : Sains

Satu model pelbagai matlamat bagi kemasukan pelajar baru dibentuk,

diformulasikan sebagai rumusan matematik dan akhirnya disahkan. Model ini dibina

untuk memaksimumkan kemasukan pelajar ke jabatan-jabatan di sesebuah fakulti.

Pelajar kemudiannya diagihkan secara maksimum dari jabatan ke program-program

akademik dalam jabatan tersebut melalui satu prosedur pengoptimuman dwi-

peringkat. Pada peringkat pertama, bilangan optimum kemasukan pelajar ke setiap

jabatan sesebuah fakulti harus ditentukan dengan mengambilkira had keupayaan

jabatan bagi mematuhi batas-batas kapasiti ruang, kekangan peruntukan kewangan,

bilangan tenaga pengajar dan kuota affirmative action. Pada peringkat kedua pula,

bilangan optimum pengagihan pelajar ke program-program dalam sesebuah jabatan

tersebut ditentukan dengan mengambilkira kekangan-kekangan khusus yang

terdapat pada setiap program akademik itu dengan mengapplikasikan prosedur

seperti pada peringkat pertama. Setiap kekangan mempunyai pemberatnya masing-

masing di samping mempunyai aras keutamaan yang harus dipenuhi. Kemudian,

model ini diaplikasikan di Fakulti Sains dan Teknologi, Universiti Kebangsaan

v

vi

Malaysia yang mempunyai lima pusat pengajian dan seterusnya diaplikasikan pula

di salah satu pusat pengajian fakulti berkenaan iaitu Pusat Pengajian Sains

Matematik yang terdiri dari tiga program akademik. Keputusan yang diperoleh dari

model premtif pengaturcaraan gol dibandingkan dengan model bukan premtif

pengaturcaraan gol bagi kedua-dua peringkat untuk menganalisis keupayaan model

berbanding dengan keadaan sebenar. Analisis kepekaan bagi hasil yang diperoleh

juga dilakukan untuk menguji kesahan model-model tersebut. Hasil aplikasi dwi-

tahap ini mempamerkan keupayaan model untuk menyediakan pengagihan optimum

selaras dengan polisi pengambilan pelajar berdasarkan kekangan yang ada pada

setiap jabatan sesebuah fakulti dan juga setiap program akademik dalam jabatan

berkenaan.

ACKNOWLEDGEMENTS

I would like to express thankfulness to the Almighty Allah who gave strength,

perseverance, thoughts and guidance to me so as to complete my thesis within the

stipulated time frame.

I am very much indebted to the Supervisory Committee, which chaired by Associate

Professor Dr. Mohd. Rizam Abu Bakar for his ever-helpful guidance and assistance

during the course of this research and support in presenting the findings in seminars

and colloqiuims which I attended and the findings published. I highly appreciate the

suggestions and recommendations given by Associate Professor Dr. Azmi Jaafar and

Dr. Mansor Monsi as members of the Supervisory Committee.

I would also like to extend my gratitude to the Mathematics Department of

Universiti Putra Malaysia and the Institute for Mathematical Research (INSPEM) of

Universiti Putra Malaysia for the facilities and laboratory equipments provided for

the research, and most of all to Universiti Kebangsaan Malaysia and Jabatan

Perkhidmatan Awam Malaysia, which financially sponsored the research

undertaken.

vii

I certify that an Examination Committee has met on 10th of July 2007 to conduct the final examination of Nasruddin bin Hassan on his Doctor of Philosophy thesis entitled “A Two-Stage Multi-Objective Allocation Model for Student’s Admission into Academic Departments in A Malaysian Public University” in accordance with Universiti Pertanian Malaysia (Higher Degree) Act 1980 and Universiti Pertanian Malaysia (Higher Degree) Regulations 1981. The Committee recommends that the candidate be awarded the degree of Doctor of Philosophy. Members of the Examination Committee were as follows: Mat Rofa Ismail, PhD Associate Professor Faculty of Science Universiti Putra Malaysia (Chairman) Malik Hj.Hassan, PhD Profesor Faculty of Science Universiti Putra Malaysia (Internal Examiner) Leong Wah June, PhD Lecturer Faculty of Science Universiti Putra Malaysia (Internal Examiner) Zuhaimy Hj.Ismail, PhD Associate Profesor Faculty of Science Universiti Teknologi Malaysia (External Examiner) ___________________________________ HASANAH MOHD GHAZALI, PhD Professor and Deputy Dean School of Graduate Studies Universiti Putra Malaysia Date: 17 December 2007

viii

This thesis was submitted to the Senate of Universiti Putra Malaysia and has been accepted as fulfilment of the requirement for the degree of Doctor of Philosophy. The members of the Supervisory Committee were as follows : Mohd. Rizam Abu Bakar, PhD Associate Professor Faculty of Science Universiti Putra Malaysia (Chairman) Azmi Jaafar, PhD Associate Professor Faculty of Computer Science and Information Technology Universiti Putra Malaysia (Member) Mansor Monsi, PhD Lecturer Faculty of Science Universiti Putra Malaysia (Member) __________________________ AINI IDERIS, PhD Professor and Dean School of Graduate Studies Universiti Putra Malaysia Date: 22 January 2008

ix

DECLARATION I hereby declare that the thesis is based on my original work except for quotations and citations which have been duly acknowledged. I also declare that it has not been previously or concurrently submitted for any other degree at UPM or other institutions. _____________________ NASRUDDIN HASSAN Date: 8 November 2007

x

TABLE OF CONTENTS

Page

DEDICATION ii ABSTRACT iii ABSTRAK v ACKNOWLEDGEMENTS vii APPROVAL viii DECLARATION x LIST OF TABLES xiii LIST OF FIGURES xiv CHAPTER 1 INTRODUCTION 1.0 Introduction 1.1 1.1 Problem Background 1.1 1.2 Problem Statement 1.2 1.3 Research Objective 1.2 1.4 Significance of Research 1.4 1.5 Methodology 1.5 1.6 Summary of Thesis 1.6 2 LITERATURE REVIEW 2.0 Introduction 2.1 2.1 General Literature Review 2.1 2.2 Literature related to the Problem 2.6 3 RESEARCH METHODOLOGY 3.0 Introduction 3.1 3.1 Optimization 3.1 3.2 Linear Programming 3.6 3.2.1 Linear Programming Formulation 3.6 3.2.2 Methods of Solution 3.8 3.3 Goal Programming 3.10 3.3.1 Goal Programming Formulation 3.11 3.3.2 Significance of Deviational Variables 3.16 3.3.3 Solution Tools 3.17 4 MODEL DEVELOPMENT 4.0 Introduction 4.1 4.1 Problem Background 4.1 4.2 The First Stage Model 4.3

xi

xii

4.2.1 Summary of The First Stage Model 4.12 4.2.2 The General Formulation of The First Stage Model 4.15 4.3 The Second Stage Model 4.16 4.3.1 Summary of The Second Stage Model 4.23 4.3.2 The General Formulation of The Second Stage Model 4.25 5 ANALYSIS OF RESULT 5.0 Introduction 5.1

5.1 Results of the Non Preemptive First Stage Model 5.2 5.1.1 Analysis of Results 5.3 5.1.2 Error Analysis 5.5 5.1.3 Sensitivity Analysis 5.6

5.2 Results of the Non Preemptive Second Stage Model 5.7 5.2.1 Analysis of Results 5.8 5.2.2 Error Analysis 5.9 5.2.3 Sensitivity Analysis 5.11 5.3 Results of the Preemptive First Stage Model 5.11 5.3.1 Analysis of Results 5.13 5.3.2 Error Analysis 5.15 5.3.3 Sensitivity Analysis 5.16 5.4 Results of the Preemptive Second Stage Model 5.17 5.4.1 Analysis of Results 5.18 5.4.2 Error Analysis 5.20 5.4.3 Sensitivity Analysis 5.21 5.5 Conclusion 5.22

6 RESULTS AND DISCUSSION 6.0 Introduction 6.1

6.1 Validation of the First Stage Model 6.1 6.1.1 Validation of the Non Preemptive First Stage Model 6.3 6.1.2 Validation of the Preemptive First Stage Model 6.9

6.2 Validation of the Second Stage Model 6.16 6.2.1 Validation of the Non Preemptive Second Stage Model 6.18 6.2.2 Validation of the Preemptive Second Stage Model 6.21

6.3 Conclusion 6.25 7 CONCLUSION 7.0 Introduction 7.1 7.1 Summary 7.1 7.2 Conclusion 7.3 7.3 Future Studies 7.4 REFERENCES R.1 APPENDICES A.1 BIODATA OF THE AUTHOR B.1

LIST OF TABLES

Table Page 5.1 Tabulated Results of the Non Preemptive First Stage Model 5.2 5.2 Error Calculations for the Non Preemptive First Stage Model 5.5 5.3 Tabulated Results of the Non Preemptive Second Stage Model 5.8 5.4 Error Calculations for the Non Preemptive Second Stage Model 5.10 5.5 Tabulated Results of the Preemptive First Stage Model 5.12 5.6 Error Calculations for the Preemptive First Stage Model 5.16 5.7 Tabulated Results of the Preemptive Second Stage Model 5.17 5.8 Error Calculations for the Preemptive Second Stage Model 5.20 6.1 Weights of the Non Preemptive First Stage Model 6.2

6.2 Weights of the Preemptive First Stage Model 6.2 6.3 Priority Ranking 6.3

6.4 Tabulated Results of the First Trial Run 6.4 6.5 Tabulated Results of the Second Trial Run 6.5 6.6 Tabulated Results of the Third Trial Run 6.6 6.7 Tabulated Weights of the Fourth Trial Run 6.8 6.8 Tabulated Results of the Fifth Trial Run 6.9 6.9 Tabulated Results of the Sixth Trial Run 6.11 6.10 Tabulated Results of the Seventh Trial Run 6.12 6.11 Tabulated Results of the Eighth Trial Run 6.14 6.12 Weights of the Non Preemptive Second Stage Model 6.16

6.13 Weights of the Preemptive Second Stage Model 6.16

xiii

xiv

6.14 Priority Ranking 6.17 6.15 Tabulated Results of the Ninth Trial Run 6.18 6.16 Tabulated Results of the Tenth Trial Run 6.19 6.17 Tabulated Weights of the Eleventh Trial Run 6.20 6.18 Tabulated Results of the Twelfth Trial Run 6.21 6.19 Tabulated Results of the Thirteenth Trial Run 6.23 6.20 Tabulated Results of the Fourteenth Trial Run 6.24 6.21 Summary of Tabulated Results 6.26

LIST OF FIGURES

Figure Page 1.1 A Diagrammatical Summary of the Problem 1.3 7.1 Allocation of Students into Malaysian Universities 7.5

xv

CHAPTER 1

INTRODUCTION

1.0 Introduction

In this chapter, we discuss the problem background and problem statement in

allocation of students to emphasize the research excellence in academia. The goals

and constraints are stated and the research objective refined. The significance of

research and the research methodology are also discussed in this chapter. The

chapter is then concluded by the summary of thesis.

1.1 Problem Background

A number of important developments have taken place in the study of mathematical

programming in academic scheduling and assignments. The priority of certain

courses to emphasize the research excellence of an academic institution, the number

of students’ intake and the consequent fees collected are important administrative

tasks that must be performed in academic departments each semester. In such an

academic environment, there exist some organizational, as well as individual goals

that influence the assignment problem. The goal of administrators are driven by

changes in student demand for courses, and hence the desire of involved

administrators to provide these necessary courses. In addition these courses have to

reflect the thrust of research of the faculty in the departments. Other factors

influencing the assignment problem might have to do with certain limited resources

such as the limited number of faculty expertise in certain fields and the number of

lecture halls and classroom availability. Other factors are related to policy, such as

number of preparations (Tillet, 1975), and the racial quota system of entry into

public universities. Another consideration in the assignment process is the personal

preferences of the faculty staff in specific course assignments (Schniederjans and

Kim, 1987) due to their varied expertise.

1.2 Problem Statement

This study is done to develop a goal programming model which will optimize the

departmental preferences in student allocation given the varied expertise of the

faculty members subject to the availability of lecture halls and seminar rooms,

students’ entry policies, collection of tuition fees and the thrust of research

excellence within the department. We regard the capacity requirements of first year

students admission, capacity requirements of academic centers and academic

programmes, affirmative action ratio, student-staff ratio and budget allocation to

academic centers, as conflicting constraints. We then undertake to develop, verify

and validate a multiobjective allocation model of students’ admission into academic

departments based on the given constraints and criteria.

1.3 Research Objective

Multicriteria assignment or allocation problem in academic institutions are often

solved using various mathematical programming methods. However, many of those

academic problems do not address the constraints such as student fees, subsidies,

programmes offered and the main thrust of the departments. Literature reviews on

research conducted are confined to simple models. The academic allocation and

scheduling in high institutions is becoming more complex due to complexity of the

academic advancement, social expectation and academic management. This research

is an attempt to present a methodology for modeling student admission into

1.2

academic departments. The model may then be applied to solving real world

problem.

Faculty of Science and Technology, UKM

Priority; • Deviational variables are

weighted or prioritized preemptively.

Ranking; • For each set of variables

prioritized, the deviations are ranked base on academic centers requirement.

Constraints in each academic center;

• Capacity of first year intake.

• Capacity of total number of students.

• Affirmative action ratio. • Students-faculty ratio. • Budget expenditure.

Priority; • Deviational variables are

weighted or prioritized preemptively.

Ranking; • For each set of variables

prioritized, the deviations are ranked base on academic programme requirement.

Allocation to academic programs of the Centre of Mathematical Sciences.

Second Stage Model

Constraints in each academic programme;

• Capacity of first year intake.

• Capacity of total number of students.

• Affirmative action ratio.

• Students-faculty ratio.

Allocation to five academic centers of the Faculty of Science and Technology.

First Stage Model

Figure 1.1 : A Diagrammatical Summary of the Problem

1.3

We further refine the objective as follows:

• To study current practices of student assignment and allocation at Universiti

Kebangsaan Malaysia.

• To model and solve student assignment and allocation problem using goal

programming method.

• To develop model with multi-criteria requirements and solving them using

preemptive goal programming and non-preemptive weighted goal

programming.

To obtain these objectives, the research framework of this study is designed as in

Figure 1.1 above.

1.4 Significance of Research

The application of the multi-stage assignment problem will demonstrate the

possibility of structuring the main problem into relatively small models not

impossible to be solved. Else the problem will definitely involve too many

constraints with too many conflicting objectives such that the solution to the

problem will be elusive. This study will benefit academic institutions in coping with

their budgeting problems under restrained government grants, establishing the

correct racial balance of enrollment, reflecting the main thrusts of research

excellence and provide a fair distribution of faculty assignment in terms of

programme offering and student-faculty ratio. The scope of this study is the

allocation of student admission into a faculty of a university with five academic

centres, each with their own academic programmes.

1.4

Of course this study can be further extended in such a manner where the Ministry of

Education can optimally allocate students into Malaysian public universities based

on constraints unique to these universities and other constraints deemed necessary

by the Ministry of Education, as illustrated in Figure 7.1. These universities will

allocate students to their various faculties. The faculties will then allocate these

students to their respective academic departments and programmes within those

departments.

1.5 Methodology

The existing structure on goal programming for multi-objective function is used in

developing and constructing the necessary goals and related constraints. A goal

programming model involves an overwhelming number of decision variables and

goal constraints. A study is conducted on one of the faculty and its academic

departments and programmes in University Kebangsaan Malaysia. The study

produced a goal programming model and was run on a personal Pentium IV

computer using LINDO version 6.1 programming. This LINDO programming has

the advantage of allowing weights to be attached to the positive and negative

deviations of each goal to be optimized. The multistages structure will enable the

model to capture the dynamic aspects of the problem. Moreover the number of

decision variables and constraints will be drastically reduced. In the first stage, the

core of the procedure is formed by a matrix of the coefficients of variables and

weights. The output of the first stage is then utilized as inputs to the second stage.

The process can be further repeated for the following stages.

1.5

1.6 Summary of Thesis

This research was done to optimize the allocation or assignment of students into the

departments or academic centers of a university based on given system and goal

constraints. Having found the optimal number of students allocated into the

departments, these students were then channeled into the respective academic

programmes within the particular department subject to further system and goal

constraints unique to those programmes in the department, thus giving rise to a two-

stage multicriteria goal programming problem. The introduction and background to

this problem was explained in the beginning of Chapter 1, followed by the problem

statement, objective, the significance of research, the methodology used in the

research being undertaken and the synopsis of the thesis.

The literature review in Chapter 2 will enlighten the reader on developments and

applications of goal programming in academic management and the two-stage

procedure. This chapter is divided into two parts. The first part deals with the

general literature while the second part explains in great detail those literatures

related to the undertaking of this study.

The underlying concepts of mathematical programming are explained in Chapter 3.

The linear programming and the goal programming are explained here. The

formulation and methods of solution of these programming are also discussed in this

chapter. The discussion of these programming will provide a prerequisite

understanding of the formulation of the problem at hand to develop the objective

function, goal and system constraints.

1.6

1.7

The problem is formulated in Chapter 4. The system and goal constraints are also

formulated in this chapter. Each constraint is reasoned out. The weights attached as

coefficients to the deviation variables, along with the priority factors in the objective

function to be optimized are explained in this chapter.

The results are displayed in Chapter 5 followed by the discussion and the analysis of

results. The positive and negative deviations of each constraints are discussed in

order to give meaning to the results obtained. Sensitivity analysis is conducted to

test the stability of the results obtained in the previous chapter.

The model is tested and verified in Chapter 5. Error analyses are conducted to

determine the improvement of student allocation made possible by the

implementation of the model. The model is then further validated in Chapter 6. The

model is applied to fourteen trials of simulated data to compare its reasonableness of

results. It is shown that this model can be reasonably applied to situations where

changes in coefficients and constants of the constraints were made to suit its

application to different environments.

The summary and conclusion of the research undertaken is elaborated in Chapter 7.

The model expansion to several stages and extensions for further investigation are

also suggested in this chapter.

CHAPTER 2

LITERATURE REVIEW

2.0 Introduction

In this chapter we will discuss the general literature review regarding Operations

Research, its origins and extended applications. We then proceed with the discussion

on mathematical programming models developed for academic institutions which

then brings goal programming in resource allocation into focus. Models developed

by Elimam (1991), Bafail and Moreb (1993) and Badri (1996) are discussed in great

detail. Thse discussions lead to our proposal in developing a two-stage allocation

model for students’ admission into academic departments.

2.1 General Literature Review

Operations Research or simply OR is a subject that use mathematical models,

algorithms and statistics to aid in decision-making. It is often used to analyze

complex real-world systems, typically with the goal of improving or optimizing

performance. The terms operations research and management science are often used

synonymously. When a distinction is drawn, management science generally implies

a close relationship to the problems of business management and industrial

engineering. Industrial engineering takes more of an engineering point of view, and

industrial engineers typically consider OR techniques to be a major part of their

toolset. Some of the primary tools used by operations researchers are statistics,

optimization, stochastics, queueing theory, game theory, graph theory, and

simulation. Because of the computational nature of these fields OR also has ties to

2.1