الگوریتم تخصیص پروژه پویا برای یک سیستم کارشناسی توزیع شده

One of the major concerns of a distributed expert system is to provide optimal solution to a business process characterized by an operations research model. Based on the concept of dynamic programming, the paper presents an efficient computer algorithm which solves an Integer Programming Model for optimally allocating Final Year Projects to more than 200 fourth year BSc students in Department of Civil Engineering (CE), National University of Singapore (NUS), subject to the operation constraints of students' ranking, personal preference and project availability. Having been implemented as part of a distributed project allocation system, the algorithm has improved tremendously the operation efficiency of FYP allocation, by a factor of more than 600 times with a flawless accuracy as compared to its counterpart generated by a previously-adopted manual processing procedure. In light of the dynamic programming pattern abstracted from this system, the allocation algorithm has the potential of being extended to building other distributed merit-based expert systems.

The latest development in internet/intranet server technology has empowered us to develop powerful distributed expert systems (Grove, 2000 and Li, 2002) that have revolutionized the conventional way of information collecting, processing and decision-making. One of the key concerns of such an information system is its ability to collect the relevant data and to process them in such a way that generates the optimal solution to a business process characterized by an operations research model. Traditionally in Department of Civil Engineering, National University of Singapore, the Final Year Project (FYP) allocation process was accomplished manually in three stages: (1) Academic Staff contributed their FYP proposals and submitted them to Department Office before certain deadline; (2) Fourth year students wrote down the titles of 10 FYP proposals in a form, prioritized and returned them to Department Office before certain deadline; (3) Members of a committee manually allocated a FYP to a student based on the student's ranking number, his/her personal preference and the availability of the FYP. Then the committee would announce the allocation outcome to all the students. The manual processing sequence was very time-consuming and very inconvenient to the parties involved. For instance, a student had to do a lot of manual search for finding the relevant projects and then prioritizing them in a form that was difficult to modify after submission. Academic Staff claimed it was troublesome for them to keep track of the FYP proposals submitted and make changes later on. For the committee members, it was very stressful and tedious to manually assign FYPs to students one by one, because they were under enormous pressure to do a good allocation job for several hundreds of students in a couple of days time. It was under such a circumstance that the request of developing a distributed expert system was studied, which aimed at computerizing all the three stages of FYP processing. The distributed expert system consists of (a) three user interfaces to support the system-user interactions in the above-mentioned FYP processing stages; (b) an expert engine to perform optimal FYP allocation based on the relevant data collected; and (c) a relational database management system for creating database tables and managing data transactions. At the core of such an expert engine is a computer algorithm based on dynamic programming concept, which applies expert knowledge (derived from an operations research model) to processing the content of backend database tables. This computer algorithm was intended to find an optimal allocation scheme that best matches a student's preference to the student's eligibility for the corresponding project, subject to the constraints in the student's ranking, his/her prioritized project selections and available project spaces. In other words, the implementation of the algorithm enables a student to be assigned to the most preferable project which the student's ranking and the associated project availability allow. In processing the relational database of students online-submitted FYP selections, the algorithm was applied uniformly across the whole student population to ensure the impartiality and fairness of the merit-based allocation mechanism. As compared to the results of manually processing of FYP assignment, the computerized allocation system had brought about tremendous improvement on operational efficiency (by more than 600 times) and achieved an impeccable accuracy as compared to the results of an independent manual processing procedure. The paper aims at describing how an efficient computational algorithm had been developed and implemented, in light of a dynamic programming concept, to enable the optimal solution to the integer programming model which characterizes the FYP expert system mentioned above.

In this paper, an Integer Programming Model was first derived to mathematically simulate the problem of ‘allocating the most desirous projects to the most qualified students’. A constraint-based multidimensional search algorithm for finding the optimal solution to the model was then presented, based on the dynamic programming concept of sequence of stages. Subsequently the paper presented the distributed FYP system as a vehicle to implement the optimal algorithm for solving the FYP allocation problem. The implementation results of the system have testified the effectiveness of the algorithm both in terms of computer-processing efficiency and accuracy. The computer algorithm presented here can be adapted to solve other business processes whose optimization solutions can be found through a dynamic programming pattern similar to the one described in this paper. For instance, it can provide valuable insight to the mathematical programming of a computerized university/secondary school admission system, etc.