2

I am looking for an algorithm (and hopefully a .net implementation) that can do the following: I have the following data:

  1. a list of technicians each one with different skills (could be more than one).
  2. a service time window (e.g. 8-12)
  3. a list of all previously scheduled jobs within this time window (each with it's required skills)

given a new job (with required skills), I am supposed to check if the new job and be assigned to any of the technicians available (previous jobs may be moved between technicians as long as their skills support it). also the service time window cannot be exceeded so a 1 hour job cannot scheduled for 11:30

Initially I thought about doing bin packing FFD variant were I pre-load the bins (technicians) and when looking for a bin to place a job I would also check for skill matching. The job list would contain all previous jobs and the new one (sorted descending by size) and either the code stops because a job cannot be placed in any bin or it finishes after all jobs have been scheduled.

In theory it could work but then I thought of the following scenario:

  • Technicians: T1(with skills S1 & S2), T2(with skills S2 & S3)
  • Previous jobs: J1 (requires skill S2), Duration the whole time window.
  • New Job J2 (requires skill S1)

A case could happen that J1 is assigned to T1 and then J2 has no place to fit.

So I thought about adding a second sort to the job list: Jobs will be sorted by size descending and then by the number of resources who can actually do them ascending. This would place J2 to be scheduled first as fewer technicians can do it.

Is there a specific algorithm for solving this or is my approach good enough?

Thanks

Codor
  • 17,447
  • 9
  • 29
  • 56
Dani Avni
  • 423
  • 5
  • 14
  • 1
    Seems like a classic class scheduling problem to me, where the technicians are teachers (that can teach multiple subjects). This problem is NP-Hard. Some related questions that solved it by reduction to SAT and using SAT Solver: Class Scheduling to Boolean satisfiability, [\[part 1\]](http://stackoverflow.com/q/28983729/572670), [\[part 2\]](http://stackoverflow.com/q/29140280/572670), [\[part 3\]](http://stackoverflow.com/q/29251041/572670). Though not a dupe, these approaches might help you as well. – amit Apr 30 '15 at 06:30
  • In contrast to class schedules, his technicians might be able to start at just some point in time during service intervals. Not only half-hourly. Does this turn the problem into some "pack blocks of different colors into a box of length L (8-12 service time)"? – BitTickler Apr 30 '15 at 06:39
  • actually this is only the first part of our system. A customer calls the help center and asks a technician sent over. The help center needs to schedule a technician based on the skills needed and availability. So they tell you the tech will come Monday from 8-12. We don't know who the tech will be yet and do not assign the task to anyone. We just take a spot on the schedule. and the only data we have is how many technicians we will have of each skill set on Monday. the day before -Sunday we run route optimization on all available technicians and all jobs (this part is already done and works) – Dani Avni Apr 30 '15 at 06:47
  • What if no worker in the pool has all skills needed for a job? Do you send over more than one worker? – BitTickler Apr 30 '15 at 08:01
  • If no tech has the required skill the code will decide that this time window is not suitable and will try another time window (maybe other technicians are available on it). If no time window was found then the help center will have to decide what to do. We do not intend to be a full scale time window scheduling system. I need to provide a good enough solution for most of our users. If some cannot use this part of our app they can always go to a professional scheduling system and use our system for the rest (route optimization and other features we have) – Dani Avni Apr 30 '15 at 09:44

1 Answers1

2

Take a look at the Constraint Satisfaction Problems. Your problem falls in that category.

Also, for a quick review of the problem class and some toy examples take a look here.

This is the (publicly available) chapter where the slides were taken from.

The constraint you will need are more or less the following (written in an informal way):

  1. A problem needs a set of skills to be solved.
  2. A problem has a time window needed to be solved.
  3. A problem can be assigned to a technician only if the technician has all the needed skills.
  4. A problem can be assigned to a technician only if the technician has a time slot greater than or equal to the time needed to solve the problem.

Then there are the constraints regarding the technician and the available time slots and, eventually, the constraints regarding the technician and the location (where the problem should be solved).

Gentian Kasa
  • 776
  • 6
  • 10
  • Since my only concern is to squeeze all existing jobs + new one on the time window can I assume the model for such a CSP would be something along the lines of: 1 decision variable per job (which tech does it), constraints are: sum of job length per tech<=time window size, all jobs are done by tech with correct skills. Am I correct? I just downloaded from solver.com their SDK. hope it's easy enough to learn to use it as a solver – Dani Avni Apr 30 '15 at 09:02
  • I have edited the answer to add some constraints that popped in my mind. Regarding the SDK you mentioned I can't really say anything because when i managed a similar problem I didn't use any external SDKs or APIs. – Gentian Kasa Apr 30 '15 at 10:09