Algorithms – Optimal Combination of Two Variables

The NP-Hard domain of problems means that, as far as current mathematical knowledge goes, the problem can only be solved by trying every permutation and choosing the correct answer.

If you can solve the problem more efficiently than the brute force method, you will win a Noble Prize in mathematics as a bonus. The best mathematicians have been working on a general answer to this problem for decades.

Perhaps as you are wanting to create a test data-set for your NP-Hard problem solver, your approach may be to design the test data backwards - rather than solve the NP-Hard problem, create an NP-Hard problem with a known answer - I don't even know if that is a NP-Hard problem on it's own.

I have some experience with the sort of scheduling problem you present, and the technical stack you're using, and so I can speak from authority and say this is a database problem and belongs in SQL Server, not Excel!.

Assuming that these are regular visits that are already scheduled and you only need to allocate your staff to the various tasks, (and staff have to return to their home office between visits), I recommend the following process:

1. Migrate your staff list to a normalized table structure, with separate Employee and Availability tables.
2. Do the same to your service users, with Customer and Visit tables. (How you populate the visits is a different question.)
3. Create a distinct Assignment table, that reflects the assignments you give your staff. This table will include both actual shifts, and necessary non-visit assignments (such as "drive across town"). Your program will generate suggestions, but you need to allow a human to revise the list.
4. Generate a "complexity" score for each visit, by adding all the necessary requirements together. ("Must be seen by two certified women for 3 hours" may be seven points, for example.)
5. For the highest complexity value, make all assignments for your time period for all visits on that assignment. Do this one row at a time, with tie-breakers based on the visit length and start-time. Select staff who meet the needs based on availability and then some sensible sort value (seniority or "times done this shift.")
6. Mark a travel time entry for the assigned staff between the customer's location and the employee's central location.
7. Repeat from #5, above, until all visits are satisfied.
8. Return to Excel two lists, one of Customer Visits that indicates the assigned employees(s), and one of Employee assignments that notes the times each employee will be assigned. Include any highlight in both any unassigned items.

There are professional Workforce Management systems that will much of this for you, but such require several tens of thousands of dollars to purchase and assume you'll have an employee doing much of the work manually. If they were doing this in Excel by hand, any automation will be an aid, and you can improve as you go on.

(And take a look at .NET or Access to replace Excel in some instances; round-tripping data from Excel back to SQL Server is significantly harder than just making a form for a SQL server table in Access.)