Suppose you wanted to assign faculty to courses for an academic year given the f

Question

Suppose you wanted to assign faculty to courses for an academic year given the following information: you have n faculty F1 , F2 , . . . , Fn and m courses C1 , C2 , . . . , Cm. Each faculty member has a course preference, a subset of courses he or she is able to teach, and an assigned teaching load (number of courses to teach per year). Each course has an associated demand, the number of times it must be taught during the year.

Explain how you could use max flow-min-cut to 1) determine whether there exists an assignment of faculty to courses that can satisfy the demand requirements without violating their teaching loads and preferences, and 2) given an assignment is possible, report the assignment (a list of courses for each faculty member).

The problem in part a) asked for a solution that does not violate the faculty course load constraints, that is, no faculty teaches more than his or her assigned load. Suppose we want to modify the problem so each faculty member has a minimum as well as a maximum course load (so a feasible solution would have all courses taught, and each faculty member’s assignment no less than his or her minimum and no greater than his or her maximum load. Explain how you would need to modify what you did in the previous part to accomplish this.

Explanation / Answer

Hello user, I will answer your question gladly :D

Using the max-flow min-cut we can create a graph that will allow us to measure which faculty members are able to teach a course. Said graph would be composed by a source, and a sink, which represent the available faculty members and the available courses respectively. each faculty member will be represented by a vertex linked to the source, and each course will be represented by a vertex linked to the sink.

Now, from each faculty member vertex, will depart one or more edges, the quantity of these will be determined by the faculty member's course preferences.

After we have the graph all set, we apply the technique, to achieve the following:

a.-) "remove/cut" edges from faculty members to courses, until each faculty has reached their teaching load.

b.-) "remove/cut" edges until each course has reached their associated demand to be taught.

After doing that, if there is a possible way to achieve that with the given information, we can create a report of the assignment by going through the faculty nodes and returning the destinations of their edges.

If you have any doubts, you can contact me by this way. Have a nice day :D

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.