VIETNAM NATIONAL UNIVERSITY HO CHI MINH CITY UNVERSITY OF INFORMATION TECHNOLOGY ADVANCED PROGRAM IN INFORMATION SYSTEMS NGUYEN HOANG LONG —- NGUYEN SON LAM STUDY ON EXAM INVIGILATOR BACHELOR OF ENGINEERING IN INFORMATION SYSTEMS HO CHI MINH CITY, 2020 VIETNAM NATIONAL UNIVERSITY HO CHI MINH CITY UNVERSITY OF INFORMATION TECHNOLOGY ADVANCED PROGRAM IN INFORMATION SYSTEMS NGUYEN HOANG LONG - 16520688 NGUYEN SON LAM- 16521708 GRADUATE THESIS STUDY ON EXAM INVIGILATOR BACHELOR OF ENGINEERING IN INFORMATION SYSTEMS ADVISOR DR. DO TRONG HOP HO CHI MINH CITY, 2020 ASSESSMENT COMMITTEE The Assessment Committee is established under the Decision. ; date 26/01/2021 by Rector of the University of Information Technology. Đỗ Phúc - Chairman 2 Dr.
Cao Thi Nhan - Secretary 3 _ Dr. Ngé Đức Thanh - Member ACKNOWLEDGMENT Throughout the completion of this project we have received a great deal of support and assistance. First, we would like to express our dearest gratitude to our advisor Dr. Đỗ Trọng Hop, and our mentor Dr.
Nguyén Thanh Binh for providing guidance and feedback throughout this project. They continuously provided encouragement and were always willing and enthusiastic to assist in any way they could throughout the research project. Second, we want to give our special thanks to Bsc. Huynh Thién Y, whose support as part of his science paper allowed our studies to go the extra mile.
We are also thankful to the Faculty of Information System and all its staff for all the considerate guidance. To conclude, we cannot forget to thank our family and friends for all the unconditional support, as well as providing a happy diversion to rest our mind outside of our research. Once again, we sincerely thank you! TABLE OF CONTENTS ACKNOWLEDGMENTT. HH ni 0 0000960004 80896 i LIST OF TABLES .- c5 <5 G55 99 9099900308080 000040490895690880 886 vii LIST OF FIGURES.
00080001000 00004004004048180850 viii LIST OF ABBREYVIA TIONNS. HH nọ cọ.00000000950509 00 xii Chapter 1: INTRODUCTION. ch nh Thu TH TH HH HT Hi HH Hà 1 1.2 Objectives of the r€S€arCTh.- c1 31119911191 nh HH HH rớt 2 1.3 Target and scope of the r€S€aCH .- «6 111 E23 9119911191 HH ng rkp 2 1.-- G5 2 231111 1 1 HH TT HH HH TH TT HH rệt 3 IS) nao. 3 Chapter 2: BACKGROUND AND THEOlRYY.1 Overview of assignment prObÌ€1m.2 Exam invigilator assignment prObÌÏ€1m.3 Related methods in solving the scheduling problem.- -- << H111 HH HH HH kệ 5 2.3 Methods summary and ConCÏUSIOI.- -- 5 s11 91199119 991 1 vn rệt 5 Chapter 3 EXAM INVIGILATOR ASSIGNMENT PROBLEM.1 Describe the problem 1n.3 Genetic Algorithm (6/ V0 mằmàăằăỔỎ.1 Individual TeDT€S€TAfIOT.ó- ó6 1 311112301 911211901 vn ng nh ng nh ng nh nh 9 3.2 Individual adaptive function (CalculafION).2 Fitmess ẨUC[IOHI.- 6 2G 31T TH TH HH HH 14 3.3 G€n€fIC OD€TAfOTS .- ch TH ng HH HH tưy 16 3.
- G11 TH HH HH ky 16 3.2 CrossOVer OD€TAÍOT-.4 Brute-force S€ATCH.- G1119 11T ng ng TH HH nh nghệ 22 3.5 Genetic algorithm €X€CU(OTI.-- -- c5 s1 11v HH HH HH ky 28 3.1 The mathematical model of the problem.2 Finding solution for target ÍUnCfIOII. 41 Chapter 4: APPLICATION ANALYSIS AND IMPLEMENTA TION.1 Requirement analysis occ .1 Functional TeQUIT€ITTIES.-- 6 5c 22118231 11 911 1 1 2 ng ng nh ng 43 4.2 Non-functional requirements .2 Use case đÌ14ðTAIM.- 2G 0 0101119111919 111 TH HH He 44 4.1 General Use Case C1aØTAIH. G5 10111210190 90101 vn ng ngờ 44 4.2 List Of US CASES ốc h.3 Main activity (14ØTA1T. - Gv HH HH kh 46 4.1 Import invigilator (afAS€K.
HH nh TH HH gi ng, 46 4.2 Import exam schedule dataset .3 Arrange roster for 1TVIEIÏAEOT. -- cv TT HH KH HH kh 50 4.1 Entity relationship điaØTaIm. 1911391 19119 HH ky 50 CỔ VY 0) 12 vi 0.1 invigilator_db taÌ€.- - - sa SH HH HH rưy 51 4.2 schedule_db table. - - - << EEEE CC E1 E119 6253335111111 EE SE gg 555 1 kkker 51 4.3 assign_db fabÏ€.
HH HH TH TH TH ng nh 52 4.4 convert_ShiftOD table. ---- 22311111111 1EE ng 5551 1k krer 52 4.5 Application 1mpÏem€nfAfIOTA. - -- ¿+ +5 1xx vn nh vn TT TH nh 54 4.3 Review data UL.4 Review teacher data ÏT.-- 5 «+ kg HH nh 57 4.5 Review exam schedule data Í.6 Genetic Algorithm ÙÏ.- --- - «6 5+ xe x11 E9 91 ng ng 59 Chapter 5: CONCLUSION AND FUTURE WOIRK.2 Strong points, drawbacks and future WOTK. GỌI 0 00040104000198090000 080 62 VI LIST OF TABLES cleo Table 3.1 Duration of each shift per đayy.2 Two-dimensional array of each chr0I10SOI©.3 the results of 2 methods .1 List of use case faÌ€.2 invigilator_db description table.
-- <5 << 5< << sex n8 sms”51 Table 4.3 schedule_db description table .4 assign_db description table .5 covert_ShiftOD description table. o5 G5 G555 5 555 99 55995559495952 vil LIST OF FIGURES cleo Figure 3.1 Weight compute function flowWCHarFÉ.2 Compute fitness function floWCHirFẨ.3 Check function flOWWCÌhaTF.6 Mutation ẨlOWCÌl41TFK.7 Brute force search flowchart .8 Genetic algorithm fÏOWwCiaTFẨ.9 Import pulb CO(C.10 Define needed afa.12 Create a one-dimensional array containing the variable MAX.13 Create a one-dimensional array containing the variable MIN.14 Create a two-dimensional array containing variable X.16 Max COIST3ÏTIÉS.17 Output of max Constraints .19 output of min COTISẦTAÏTIf.20 Supply COIISẨT3ÏTIÉS.21 output of supply Constraint .23 output of demand constraint .26 output array Of variables ẤÃ.27 comparison between the days at school of invigilators of 2 methods.28 the days at school distribution chart of invigilator for LP, with more time limited .1 General use case diagram .2 Import invigilator dataset activity đỉaØra1m.<5-< s55 se<sssseessee 46 Figure 4.3 Import exam schedule dataset activity điagraim.4 Arrange roster for invigilator activity diagram.5 View data activity ỈØT21T1.6 Entity relationship đÏagr1T. This is the first window you see when opening the DDÌÏCØAÏOTA. This is the window when you click Get Started from the welcomeUI (all needed data must be imported in order to click Get Started).9 Review data UI.
This is the window when you click Review data from the HomeUI. The results table only appear if you have run the algorithm or this is the second time you open the apps.10 Review teacher data UI. This is the window when you click Teacher from the ReviewUI. The teacher(invigilator)’s information only appear if you have run the algorithm or this is the second time you open the apps.11 Review exam schedule data UI.
This is the window when you click Courses from 81/08.13 Genetic algorithm UI. This is the window when you click Run algorithm from the Hommel.8 59 LIST OE ABBREVIA TIONS cleo GA Genetic algorithm LP Linear programing UI User Interface DB Database xi ABSTRACT We propose a model for a decision support problem: exam invigilator assignment problem. For this problem, a wide range of schedules will be assigned for our invigilators; each person only performs a single task at a certain point in time. Meanwhile, the distance between exam days, assigned to each invigilator, is as little as possible.
Regarding the solution, we first try to derive the problem with 2 sets of constraints: hard constraint and soft constraint. Based on the constraints, we design a genetic algorithm for finding solutions for this problem. The results are compared with findings of linear programming. Finally, we build an application that can run the algorithm and display the acceptable results from the algorithm.
xil Chapter 1: INTRODUCTION 1.1 Motivation In life we often encounter problems related to scheduling such as scheduling machine operation, work (staff) schedules, sports competitions, and scheduling for the implementation of a project. With this kind of problems, we need to find a scheduling scheme that satisfies all constraints as well as efficiently exploits available resources, reducing implementation time and cost. The scheduling problem belongs to the NP-complete problems, so it may not be possible to find the optimal solution. This is not a new problem and many algorithms have been introduced to solve such as hill climbing algorithm, graph coloring algorithm, approximation algorithm,.
However, these algorithms are often not generalized and only apply effectively on a small scale, with little data constraints. The problem of assignment or scheduling work, especially in a university, is one such problem. There are many constraints to consider in this problem such as constraints on participants (invigilators, students), time constraints (number of shifts, number of shifts each day). Assigning invigilators is possible, but the results will likely make the invigilators unhappy.
The schedule assigned to the invigilators can take several days during the exam, so they must be present at school only to supervise one or two subjects per day, which is time consuming, especially for those who far from school. So, it is necessary to build a timetable that satisfies all the above constraints and at the same time minimize the number of days that invigilators have to come to school and effectively exploits the resources for the exam invigilator assignment problem.2 Objectives of the research We focus on researching and applying genetic algorithm and linear programing to exam invigilator assignment problem to propose an optimal solution that satisfies the constraints and efficiently exploits human resources in a short time. To achieve the above-mentioned objectives, we concentrate on the following specific tasks: - Analyze the problem and then give reasonable solutions in building and implementing the system. - Research the above algorithms and its applications to effectively solve the optimization problem.
- Apply the algorithms to the scheduling assignment problem for invigilators. - Analyze and evaluate and compare the results obtained after applying them to sample dataset.3 Target and scope of the research Study the characteristic features of genetic algorithms, basic components of genetic algorithm such as population initiation, evaluation of fitness function, and genetic operators (selection, crossover, mutation), stop conditions and then compare the findings with the results of linear programing. Apply genetic algorithm to the problem of assigning exam invigilators in universities with constraints and basic requirement and then build an application to display the acceptable results. Because of the limited time and knowledge about Technologies, in this thesis, we only used some technologies: - Programing languages: Python - Database System: SQLite - Software: PyCharm, Jupyter Notebook 1.4 Expected result Fully aware about the exam invigilator assignment problem.
Fully aware of the strengths of genetic algorithms and linear programming in solving optimization problems. Represent the problem in the form of integer programming. Successfully implement the genetic algorithm to a working application.5 Thesis structure The thesis is organized as follows. This introduction summarized the motivation, the objectives, the target, the scope, and the expected result of this graduate thesis.
Chapter 2 describes the theoretical background of the assignment problem that we need to research and discusses about the method choices. Chapter 3 proposes the solutions for our problem with its components. Chapter 4 explains the implementation detail of the application, including the descriptions, inputs, output, and the graphical user interface of the apps. Finally, Chapter 5 presents the conclusions of this graduate thesis and future developments that we will do in the future.
Chapter 2: BACKGROUND AND THEORY 2.1 Overview of assignment problem Assignment or scheduling problems can be defined as a search for the optimal solution to perform various types of works or tasks bounded to a set of constraints. The main objective of these problems is to increase the appropriateness or satisfaction between resources and their assigned tasks under a number of constraints. Therefore, the scheduling problem is a very complex problem as the number of constraints that need to be satisfied increases. Properties of the assignment problem: - Resources: these are the input data of the problem.
- Tasks: assessed by performance criteria such as execution time, cost, resource consumption. - Constraints: These are the conditions that need to be met in order for the problem to give the best solution - Objective: to evaluate the optimal solution of the problem. When the goals are met, the constraints must also be fulfilled.