0
$\begingroup$

I could use some help coming up with the best way to solve this problem. I've been curious as to how something like this would work, as the worst case seems way too bad.

Problem

Given a group of students and the courses they are enrolled in, and a schedule with 8 class blocks in it, how could you place them in specific classes?

Keeping in mind you can have as many classes for a specific course as long as there is a teacher who is free to teach the class.

Specifics

There are 8 class "slots" where you can put any class, but a teacher can not teach two classes at once.

Inputs and outputs

The input is a list of students each with data on which courses they are taking. There is not specific data structure I have in mind, the problem is more theoretical than literal.

The output would be assigning a value 1-8 to each class, specifying when they would take it.

Improve this question
$\endgroup$
4
  • 3
    $\begingroup$ I can't understand what you're asking. What is the input? What is the output? $\endgroup$
    – quicksort
    Commented Feb 14, 2017 at 14:04
  • $\begingroup$ I still can't understand the problem statement. What is the relevance of the statements about "a teacher can not teach two classes at once" and "as long as there is a teacher who is free to teach the class"? The inputs don't include any information about teachers. Are you sure you've given us the entire problem statement? Also, what are the constraints on when a course can be scheduled? Is there some implicit requirement that if a student is taking two courses, then they must be scheduled at different times? Please state all constraints explicitly. How many courses will there be? $\endgroup$
    – D.W. ♦
    Commented Feb 15, 2017 at 22:44
  • $\begingroup$ What's the context in which you encountered this problem? Is this from a textbook or course? What concepts is it covering now? What have you tried? What algorithms paradigms or approaches have you considered? Where did you get stuck? We're happy to help you understand concepts, but just solving exercise-style problems for you is unlikely to achieve that. You might find this page helpful in improving your question. $\endgroup$
    – D.W. ♦
    Commented Feb 15, 2017 at 22:46
  • $\begingroup$ This problem can be modelled as a mixed integer program (MIP), though the problem needs more information/interpretation. Have you thought of modelling as a MIP? The first question to ask is, what is the objective? Do you wish to meet students' preferences with respect to their preferred timetable (the stable matching problem is a good approach which can be modelled as a MIP), or is this simply a feasibility problem? Both options can be modelled as MIPs and if you would like more information please comment. $\endgroup$
    – Dylan Black
    Commented Feb 16, 2017 at 8:05

1 Answer 1

Reset to default
-1
$\begingroup$

At first glance, the stable matching problem's solution is discussed in the following pdf. https://www.cs.princeton.edu/~wayne/kleinberg-tardos/pdf/01StableMatching.pdf

It would be hard to cast the course assignment problem as stable matching because he fact that the courses have a finite capacity

However, the following pdf states that, http://dss.in.tum.de/files/bichler-research/2014_diebold_matching_course_allocation.pdf

The allocation of students to courses is a wide-spread and repeated task in higher education, often accomplished by a simple first-come first-served (FCFS) procedure. FCFS is neither stable nor strategy-proof, however. The Nobel Prize in Economic Sciences was awarded to Al Roth and Lloyd Shapley for their work on the theory of stable allocations. This theory was influential in many areas, but found surprisingly little application in course allocation as of yet. In this paper, we survey different approaches for course allocation with a focus on appropriate stable matching mechanisms. We will discuss two such mechanisms in more detail, the Gale-Shapley student optimal stable mechanism (SOSM) and the efficiency adjusted deferred acceptance mechanism (EADAM). EADAM can be seen as a fundamental recent contribution which recovers efficiency losses from SOSM at the expense of strategy-proofness. In addition to these two important mechanisms, we provide a survey of recent extensions with respect to the assignment of schedules of courses rather than individual courses. We complement the survey of the theoretical literature with results of a field experiment, which help understand the benefits of stable matching mechanisms in course allocation applications.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Why do you think that the problem in the question is solved by stable matching? I don't think that's the case at all. Just because it has to do with courses and matching/allocation doesn't mean it's the same problem you refer to. $\endgroup$
    – D.W. ♦
    Commented Feb 16, 2017 at 7:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.