Approach to solve delimited scheduling

Question

I'm facing a problem and I'm having problems to decide/figure-out an approach to solve it. The problem is the following:

Given N phone calls to be made, schedule in a way that the maximum of them be made.

Know Info:

• Number of phone calls pending

• Number callers (people who will talk on the phone)

• Type of phone call (Reminder, billing, negotiation, etc...)

• Estimate duration of phone call type (reminder:1min, billing:3min, negotiation:15min, etc...)

• Number of phone calls pending

• Ideal date for a given call

• "Minimum" date of the given call (can't happen before...)

• "Maximum" date of the given call (can't happen after...)

• A day only have 8 hours

Rules:

• Phone calls cannot be made before the "Minimum" or after the "Maximum" date

• Reminder call placed award 1 point, reminder call missed -2 points

• Billing call placed award 6 points, billing call missed -9 points

• Negotiation call placed award 20 points, Negotiation call missed -25 points

• Phone calls to John must be placed by the first person to ever call him. Notice that it does not HAVE TO, but, that call will earn extra points if you do...

I know a little about A.I. and I can recognize this a problem that fits the class, but I just don't know which approach to take... should I use neural networks? Graph search?

PS: this is not an academic question. This a real-world problem that I'm facing.

PS2: Pointing system is still being created... the points here sampled are not the real ones...

PS3: The resulting algol can be executed several times (batch job style) or it can be resolved online depending on the performance...

PS4: My contract states that I will charge the client based on (amount of calls I place) + (ratio * the duration of the call), but there's a clause about quality of service, and only placing reminders calls is not good for me, because even when reminded, people still forget to attend their appointments... which reduces the "quality" of the service I provide... I don't know yet the exact numbers

Answer 1

It is similar to a knapsack problem, where you would replace in call duration and call points for weight and price.

But you could also try to "brute force" an optimum solution:

• Use the Combinatorics library (it's in NuGet too) to generate every permutation of calls for a given person to make in a given time (looking one week into the future, for instance).

• For each permutation, club the calls into 8-hour chunks by estimated duration, and assign a date to them.

• Repeat through the chunks - if you get to a call too early, discard that permutation. Otherwise, add or subtract points based on whether the call was made before the end date or not. Store the total score as the score for that permutation.

• Choose the permutation with the highest score.