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

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.