CSC/ECE 517 Fall 2014/final E1475 nrnn

E1475. Intelligent assignment of teams

This page discusses the requirements and design specifications of final project E1475. Intelligent Assignment of teams. It starts out by giving an introduction and discussing previous implementations and related work. It then details out the workflow of the proposed implementation and shows the use case diagrams and sequence diagrams associated with it. Finally the page mentions discusses the class design and database design that would go with the implementation of the project.

Problem Statement

According to the existing code workflow, the assignment of topics to teams are based on FCFS (first come first serve) basis, where a team which first signs up for a topic gets the topic while other teams are waitlisted on the same topic. Since ‘sign up time’ is the only factor considered for topic assignment this method causes problems such as:

1. The assignment of topics are FCFS, hence not completely fair.
2. Non-uniform distribution of topics among the teams in a class.
3. The current system fails to resolve the problem when many teams bid for handful of topics(among many topics) causing unnecessary additions to the waitlist.
4. The assignment of topics is more focused on individual selection and ‘sign up time’. Factors such as team size are not considered which are important while assigning a topic to the team and potentially can reduce many issues faced by the current system.

To address the above mentioned issues, we have designed an ‘intelligent assignment of topics’ system which tries to address the issues faced by the current system.

Introduction

Expertiza

Expertiza<ref>Expertiza</ref> is a project developed using Ruby on Rails<ref>Ruby on Rails </ref> platform. It provides features like peer review, team assignments and submission of projects. This can be achieved by submitting code base, URL of hosted code on remote server and Wiki submissions. It is an open source application and the code can be cloned from github<ref>github</ref>. This application provides an efficient way to manage assignments, grades and reviews. This makes the process easier and faster when the class strength is large.

Expertiza is supported by National Science Foundation under Grant No. 0536558. Additional funding from the NCSU Learning in a Technology-Rich Environment (LITRE)<ref>Learning in a Technology-Rich Environment (LITRE)</ref> program, the NCSU Faculty Center for Teaching and Learning, the NCSU STEM Initiative, and the Center for Advanced Computing and Communication.

Existing signup process

The signup process for group projects is observed by most students to be a troublesome task in expertiza. The current sign up process for topics is based on FCFS<ref>FCFS</ref> basis, where a student who signs up for a topic of his/her choice first, gets it. We have discovered some pitfalls with the current ‘topic assignment’ system in Expertiza which arises due to the below mentioned factors. Due to these reasons, we now try to propose an intelligent system which can addresses many issues faced with the current Expertiza system.

Pitfalls with the current system

1. One student can sign up only for a single topic. In cases where many topics are available, a student is forced to choose a single topic among many available topics which can be a difficult task. To select a single topic which best fits his/her choice among many available topics requires a pre-study of all topics prior to the signup process. Such a pre-requirement is not fulfilled by most students, which results in a student signing up for a topic which he/she has randomly selected OR because it was among the only available topics.
2. If a student is not able to sign up for a topic of his choice, he can waitlist himself for all the remaining topics, which causes unnecessary traffic in the waitlist queue of a topic.
3. If all the teams choose a handful of topics among many topics, it would also result in unnecessary additions in the waitlist queue for those few topics resulting in a situation where all the topics are not uniformly distributed among all the teams
4. Before, signing up, if more than one student forms a team and if each student belonging to the same team tries to signup for different topics, than those topics are allotted to individual students resulting in a situation where a team can hold more than one topic. Thus other teams are forced to choose from remaining topics which eventually results in longer waitlists.

After observing the above problems with the existing method of ‘topic assignment’ in expertiza, we have proposed and implemented an ‘intelligent assignment of topics’ method to overcome all the shortcomings of the existing system in expertiza.

Previous work

Previously in 2012, to address this issue of expertiza, a team proposed a possible solution of ‘lottery based topic assignment’<ref>Lottery based topic assignment</ref> algorithm. The algorithm works by considering every team as strength of 1, representing the student in the team. After sign up the topic would be allotted to the team based on a lottery system where a team is randomly selected for every topic. However this method failed to address the following issues:

1. It did not consider the case where a team could be of more than one member, hence it allowed every team member to bid for different topics resulting in the same problem as mentioned in point (4) of Pitfalls with the current system.
2. The topics were awarded based on a Lottery system and not based on any other criteria which resulted in topic assignment to be a game of luck factor rather than on individual’s choice.

Requirements

1. The instructor should be able to create assignments which can utilize intelligent assignment of teams. (It is an optional feature)
2. The instructor should be able to set the maximum number of bids a team can make. Defaulted to 3.
3. The teams should be able place bids on different topics limited to the number set by the instructor for these assignments
4. The teams should be able to prioritize their bids.
5. The instructor should be able to kick off [what does that mean?] the intelligent assignment of teams.

Design Workflow

To address the issues faced by both, the current system and lottery based system, we propose a solution based on ‘intelligent team assignment’ algorithm. The algorithm is based on two important factors:

1. Team strength
2. Priority order of the topics submitted by the team.

The algorithm works on bidding process which can be explained as follows:

Before the bidding process

1. Initially, every student is a team of 1 member. Before the bidding process takes place, students can merge their teams to form a larger team. The person to whom they have merged becomes the team owner/captain.
2. Every team is given x bids (x is calculated based on the total class strength and total topics proposed), that they can place on each topic of their choice in a priority order where 1 being the highest priority.
3. Every topic is allowed ‘p’ number of maximum bids after which the topic is waitlisted in the system. [Describe the rationale for this. Is p just the number of slots?]
4. Teams can also place their bids on waitlisted topics. However, every topic has a threshold ‘q’ which signifies the maximum waitlisted bids allowed for each topic.
5. Thus, if the combined threshold of ‘p+q’ bids for a topic is reached then the topic is no longer available for bidding unless the topic is dropped by a team which reduces the ‘p+q’ threshold value.

During Bidding Process

1. Every team can place their bids on the available topics. Since every team is given ‘x’ bids, each team can bid for ‘x’ topics and list their bids in a priority order.
2. A team can also place their bids on waitlisted topics. The maximum allowed bids for waitlisted topics is ‘y’ where y is some portion of bids taken from total bids(x) allowed for each team. [I can guess how this might be implemented, but an example would help to clarify. Also, I am interested in the rationale.]

After the Bidding Process

1. After the bidding process is complete, the teams can continue to merge to form larger teams.
2. If team A merges with team B, the bids of team A would be lost. [It would be better to keep bids, insofar as possible. Losing one's topic is a "gotcha" of joining a team, and I wouldn't want to see that continue under this system.]
3. The merging of the teams is allowed till the topic assignment date when the teams would finally be assigned the topics by running an algorithm.
4. The teams can also change their submitted topic priority order any number of times before running the ‘topic assignment’ algorithm.

The algorithm assigns the topic to each teams based on the following factors:
1. The team which is close to or has maximum possible team strength has a higher probability of winning the topic they had placed their bid on.
2. For a team which satisfies condition (1), a topic would be assigned to the team based on the priority order of the bids that the team specified. [I don't think that this defines an algorithm.  An algorithm needs to be a set of steps in order.  This just describes the result.]

Features

1. As each team can place their bids on the available topics based on their topic priority. Hence every team gets to choose more than one topic of their choice.
2. As every topic has a maximum number of allowed bids, after which the topic is no longer available for bidding, this method addresses the issue where many teams choose only a handful topics among all topics.
3. As the maximum allowed bids for waitlisting a topic is also limited for every team, hence the issue of unnecessary additions to waitlist is resolved by this method.
4. The teams are assigned topics based on modified Stable marriage problem<ref>Stable marriage problem</ref> algorithm which considers factors such as team size and priority ensuring that the topics are no longer assigned based on FCFS basis. Thus this method addresses the most important issue where a topic is not assigned to the team just because the team was late to sign up for the topic as compared to the other teams.

Sequence Diagram

Fig 1. Sequence Diagram

Fig 1. shows the sequence diagram for this feature. The diagram shows the sequences exclusive to this feature. Therefore, this assumes that the assignment/exercise has already been created. Once the assignment is created, the instructor can enable the 'intelligent assignment of teams' feature for the particular assignment. Enabling this feature would give the students(or teams) a view to place bids on the topics they like. They can associate each bid with a priority. Once the deadline has passed, the instructor can kickoff the process which performs the automatic assignment. This would in turn start assigning teams with topics based on their bid preferences.

Use Cases

Fig. Use Case Diagram

Use Case	Enable Intelligent Assignment
Primary Actor	Instructor
Preconditions	Instructor is logged into the Expertiza system. Instructor has created an Assignment and allotted the Assignment Topics
Postconditions	Intelligent Assignment option is enabled for the assignment. Students can place their bids for the assignment topics on commencement of the selection process
Basic Flow	The instructor selects the assignment for which the topic selection process has not yet started. The instructor checks the “Enable Intelligent Assignment” option and presses Save. The system saves the instructors choice for the assignment.

Use Case	Add bids
Primary Actor	Student (Team Leader)
Preconditions	Student is logged into expertiza system . SignUp sheet with the list of topics is available for the assignment.
Trigger	Student selects the assignment in the topic selection phase
Basic Flow	The student selects the topic of interest from the list of topics in the SignUp sheet. The student chooses the priority of the topic. The system saves the bid for the topic and the corresponding priority. The system presents the updated view with the chosen topic.
Alternate Flow	The student has already exceeded the maximum bid limit but still selects a topic. The system throws an error saying “Bid limit exceeded”

Use Case	Delete bids
Primary Actor	Student (Team Leader)
Preconditions	Student is logged into expertiza system . Student has already selected few topics for bidding.
Trigger	Student selects the assignment in the topic selection phase
Basic Flow	The student selects the topic for which the bid existed. The student clicks “Delete bid”. The system removes the bid for the topic. The system presents the updated view reflecting the changes.

Use Case	Reorder Priorities
Primary Actor	Student (Team Leader)
Preconditions	Student is logged into expertiza system . Student has already selected few topics for bidding.
Trigger	Student selects the assignment in the topic selection phase
Basic Flow	The student selects the topic for which the bid existed. The student changes the priority of the topic. The system updates the bid for the topic with corresponding priority. The system presents the updated view with reordered topics.

Use Case	Run Intelligent Assignment
Primary Actor	Instructor
Preconditions	Instructor is logged into the Expertiza system. Instructor has created an Assignment and enabled the intelligent assignment option. The due date for the topic selection has passed.
Postconditions	The topics are intelligently assigned to the teams
Basic Flow	The instructor selects the assignment for which topic selection process has completed. The instructor selects the run intelligent assignment option. The system performs intelligent assignment of topics and allots topics to teams.

Modified version of Stable Matching Algorithm

This flow chart illustrates the algorithm used to assign topics to teams based on the strength of the teams(bidder) and the priority in which they bid for the topic.

Modified version of Stable Matching

UML Design

The intelligent assignment controller is dependent on the AssignmentTopicController and other models like - Assignment, AssignmentTopic and Team. When the instructor starts the intelligent assignment of topics to teams, IntelligentAssignmentController triggers the assignment algorithm.

The students interact with AssignmentTopicView which lists down all the topics for the assignment and allows students to bid for topics with priority. AssignmentTopicController is responsible for recording all the bids and priorities correctly.

Following is the UML diagram of the O-O design focusing only on the component related to intelligent assignment of topics to teams.

UML Design

Database Design

In order to meet other solution requirement, new tables are added. The following diagram represents the new tables in Crow Foot's Notation<ref>Crow Foot's Notation</ref>. The user table mentioned is not new and is present only to explain the field - ownerId.

Earlier, all the information in AssignmentTopic and AssignmentTopicMetadata tables were in a single table called signup_topics. However, there was lot of data redundancy observed and we also required to add an extra field in the table signup_topics. Therefore, we decided to store the topics related to an assignment according to the diagram. One caveat to this design is that all the topics for an assignment are considered equal in terms of category, maximum bids allowed and maximum bids in waiting list.

The table bid is supposed to store all the bids on the topics with their priority. The owner of the bid will be recorded too. Current requirement is to have only one bid per topic by an owner. Therefore, we could have (ownerId, topicId) pair as the primary key. However, in order to support multiple bids in a future scenario, we have used a field id as the primary key.

Apart from the mentioned new tables, we will be using pre-existing tables to meet our requirements and design.

Database Design

Design Patterns

The following patterns are used:

1. DRY: Separating out the redundant data from SignUpTopic
2. MVC
3. Separation of concerns: The IntelligentAssignmentTopicController is separated from AssignmentTopicController as the former's functionality is specific and hence should not be part of the general AssignmentTopic Controller.

References

<references/>