# I'ld like a better algorithm for scheduling tutors to fill a set of shifts

Computer Science Asked by maogenc on January 4, 2022

My problem is as follows:
I have a set of shifts at various locations that need to be filled by tutors. A simple example would be basic math in room A on M, W, F from 9-11am and Sa from 12-3 pm.
Locations can have a priority.
Skills can have a priority.
Tutors have a set of times when they are available.
Tutors set a minimum and maximum number of hours they want to work for.
Tutors can choose the longest consecutive duration they want to work for.
A tutor’s shift should be for at least an hour.
A tutor’s shift is preferred to be around 2 hours but filling the schedule is more important than having a shift be an exact number of hours.
Having as many tutors work as possible is preferred to having fewer tutors work more hours.
A tutor can be required to fill a particular shift.
For any shift, prefer assigning a tutor with fewer skills so that shifts that require more advanced skills can be assigned to shifts that need them.
Scheduling needs to keep track of unassigned periods in a shift.

Shifts, skills, and tutors each number at about 100-200.

My approach has been to break the shifts into 2 hour chunks, sort them according to the various priorities, and use a scanline algorithm to schedule tutors for shifts. For each shift chunk, I sort the tutors’ availability list by priority, assign the tutor and mark the shift duration used in the availability and shift lists. When this is done, I re-run the scheduling algorithm on unfilled shifts that have irregular hours.

In looking for alternatives, I’ve glanced at particle swarm optimization, network flow, linear programming, and the assignment problem. I’ve also wondered if a knapsack or priority queue might work, but I’m not sure how to handle the multiple (sometimes conflicting) priorities.

I’m wondering which algorithms would be more efficient for scheduling without being overly complicated to implement. I feel the current solution has become overly complicated and is beginning to become slow at the current problem size.

## Related Questions

### DFA for every run of a’s=2 or 3

3  Asked on December 17, 2021 by matt-mowris

### Is there a way to determine whether a list of integers can be a prefix function?

1  Asked on December 17, 2021 by mchl

### ‘Half-Close’ figure of Data Communications and Networking, 5/e

1  Asked on December 14, 2021

### Proof that $L={a^ncb^n| n in mathbb{N}}$ is not regular

2  Asked on December 14, 2021

### Merge two sorted arrays without using additional memory

1  Asked on December 10, 2021 by guy-kahlon

### Uniform generation of random bipartite bi-regular graphs?

2  Asked on December 10, 2021

### How to solve recursion with two separate converges rates

1  Asked on December 10, 2021 by ofir-gordon

### Context free languages invariant by “shuffling” right hand side

1  Asked on December 10, 2021 by vor

### Object algebras without anonymous inner classes

0  Asked on December 10, 2021 by byteeater

### Does $20n$ belong to $O(n^{1-epsilon})$ for some $epsilon > 0$?

1  Asked on December 7, 2021

### Bit times and propagation delay

1  Asked on December 6, 2021 by brazen

### Enumerate all valid orders of subset sums

1  Asked on December 6, 2021 by xskxzr

### “Knapsack problem” with repetition, “lesser or equal” constraint, and recording all valid combinations

1  Asked on December 6, 2021

### How do compilers assure stability?

4  Asked on December 4, 2021

### If we prove that there is an NP-complete problem that is P, Can we consider that P=NP?

2  Asked on December 4, 2021 by mwit30-room8

### Is it possible to uniformly shuffle N items into a deque of size N where you can only modify the first or last elements?

1  Asked on December 4, 2021

### Spanning tree in a graph of intersecting sets

2  Asked on December 4, 2021

### Is the two-color leapfrog problem in P?

0  Asked on December 2, 2021

### Problem with proving that $RP subseteq NP$ : a non-deterministic TM for a language $L in RP$

1  Asked on November 30, 2021 by pedro-costa

### A monad is just a monoid in the category of endofunctors, what’s the enlightenment?

1  Asked on November 30, 2021

Get help from others!