0
$\begingroup$

I am trying to design an algorithm to solve a workshop scheduling problem.

The problem is as follows: I have to schedule a workshop consisting of a finite number of time slots, and a finite number of students. Each time slot has a capacity, which must be fulfilled. Each student has a list of preference corresponding to a set of time slots, where he/she wants to work.

For instance picture the following work shop: where time slot 1,1 has capacity 3 and time slot 1,2 has capacity 4 and so on.

I want to optimize my scheduling so that students has the least overhead as possible. Overhead is defined as having to "wait" between work. For instance the following picture shows a student, that can work all three time slots in a day, but is only assigned to the first and the last, thus having one time slot overhead. Thus: My objective function is to find a feasible solution while minimizing the students' total overhead.

My idea on how to solve it, is to construct a graph (see underneath), run a max-flow algorithm to determine a feasible solution, compute the total overhead (penalty), introduce some sort of randomization to change the schedule and compute the new overhead. Repeat the last 3 steps an arbitrary number of times to find the local minimum.

Graph: Explanation of graph: The above graph shows 5 students, which each can be connected to up til 3 time slots. Each edge between a student and a time slot symbolizes that the student wants to work on that specific time slot. Each of these edges has a capacity of 1. The source node, S has edges to every student with the capacity of infinite, because each student can work as much as he/she wants. Each edge from a time slot to the sink node T, has a capacity, of the specific time slot's capacity.

Pseudo code

function solve-this(timeslots, students) {
    create graph from time slots and students
    run ford-folkerson max-flow algorithm to determine a feasible solution
    while(local optimal solution not found) {
        compute penalty / overhead
        if(computed penalty < current solution) {
            current solution = this solution
        }
        change schedule based on some sort of randomization factor
    }
    return solution
}

I also thought about modify the min-cost-max-flow algorithm, and then dynamically change my costs for non-directly-adjacent edges. For instance if we pass flow through student1 and time slot 1, then we should modify all other edges from student 1 to the non-directly-adjacent edges to have a cost or penalty.

Is there any smarter way to do this? Is this the best way to find an somewhat optimal solution, without checking every possible schedule?

Any help, comments and/or feedback is greatly appreciated.

$\endgroup$
  • 1
    $\begingroup$ Please refrain from adding multiple "EDIT:" blocks to your question. Your question should be structured so as to cater for first-time readers; scattering information across it goes against that goal. When editing it, rewrite it as it should have read at the time you first posted it. $\endgroup$ – dkaeae May 29 at 7:16
  • $\begingroup$ Hint: Consider taking each chair (literally) in a timeslot as a node, and make [timeslot] number of copies of each student, fully connected to all chairs in the respective timeslot. Do max-flow. $\endgroup$ – Pål GD May 29 at 8:50
  • $\begingroup$ I'm not quite certain i understand. In this image: imgur.com/P3IC2dj, the top left graph shows the optimal solution. The top right shows a feasible solution, but not optimal. The bottom graph is my understanding of what you are saying above @PålGD, but I don't get how that would solve my problem $\endgroup$ – JohnDoe May 29 at 9:09
  • $\begingroup$ if I understand well, by student list of preference, you mean list of slots the student accept to do ? $\endgroup$ – Vince May 29 at 11:36
  • $\begingroup$ Yes. Couldn't think of a more fitting word $\endgroup$ – JohnDoe May 29 at 11:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.