Search code examples
algorithmschedulingjob-schedulingbin-packing

Algorithm for technician time window scheduling

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

Solution

  • 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).