# Scheduling problem

Let us assume there are 50 candidates.

There are 3 companies:

Company1
Company2
Company3

who are interested in interviewing some of these candidates.

On a SINGLE day, there are 3 available slots:

morning
afternoon
evening

Company1 has 3 interviewers
Company2 has 1 interviewer
Company3 has 2 interviewers

This means on a SINGLE day:

Company1 can interview 3 x 3 = 9 candidates at most
Company2 can interview 1 x 3 = 3 candidates at most
Company3 can interview 2 x 3 = 6 candidates. at most

Suppose:

Company1 wants to interview candidates 1, 2, 3, 4, 5, 6, 7, 15, 17, 25, 26, 29, 33 ie MORE than 9 candidates.
Company2 wants to interview candidates 1, 2, 3, 34, 37, 45, 46, 47, 49 ie MORE than 3 candidates.
Company3 wants to interview candidates 15, 17, 18, 19, 27, 28, 33, 38, 45, 50 ie MORE than 6 candidates

so obviously some candidates will miss out.

Is there a way to create a schedule to maxmise the number of candidates to be interviewed for a single day?

Bear in mind, for example, if Candidate1 is interviewed by Compamy1 in the morning, he will not be able to be interviewed by Company2 in the morning also, so instead would have to take the afternoon or evening slot.

I suspect this is some sort of Linear Programming exercise but I cannot see how to convert the conditions from words into mathematical equations.
Original post by doogiedoogs
Let us assume there are 50 candidates.
There are 3 companies:
Company1
Company2
Company3
who are interested in interviewing some of these candidates.
On a SINGLE day, there are 3 available slots:
morning
afternoon
evening
Company1 has 3 interviewers
Company2 has 1 interviewer
Company3 has 2 interviewers
This means on a SINGLE day:
Company1 can interview 3 x 3 = 9 candidates at most
Company2 can interview 1 x 3 = 3 candidates at most
Company3 can interview 2 x 3 = 6 candidates. at most
Suppose:
Company1 wants to interview candidates 1, 2, 3, 4, 5, 6, 7, 15, 17, 25, 26, 29, 33 ie MORE than 9 candidates.
Company2 wants to interview candidates 1, 2, 3, 34, 37, 45, 46, 47, 49 ie MORE than 3 candidates.
Company3 wants to interview candidates 15, 17, 18, 19, 27, 28, 33, 38, 45, 50 ie MORE than 6 candidates
so obviously some candidates will miss out.
Is there a way to create a schedule to maxmise the number of candidates to be interviewed for a single day?
Bear in mind, for example, if Candidate1 is interviewed by Compamy1 in the morning, he will not be able to be interviewed by Company2 in the morning also, so instead would have to take the afternoon or evening slot.
I suspect this is some sort of Linear Programming exercise but I cannot see how to convert the conditions from words into mathematical equations.

It sounds like you could represent it as an integer LP, assuming youve covered that? So have a binary matrix with dimensions something like candidate, company, slot and think how to represent the objective and each constraint.
Original post by mqb2766
It sounds like you could represent it as an integer LP, assuming youve covered that? So have a binary matrix with dimensions something like candidate, company, slot and think how to represent the objective and each constraint.

Unfortunately I haven't covered LP / Discrete Maths in detail. Besides, this is a task for work, not a university coursework.

Can you eloborate a bit more on how to set up the equations?
Original post by doogiedoogs
Unfortunately I haven't covered LP / Discrete Maths in detail. Besides, this is a task for work, not a university coursework.
Can you eloborate a bit more on how to set up the equations?

Have you a proper description? The example you gave has a trivial solution.
But if its for work, are you trying to implement code? If so, what solvers can you access or ...?
Original post by mqb2766
Have you a proper description? The example you gave has a trivial solution.
But if its for work, are you trying to implement code? If so, what solvers can you access or ...?

Seems this is about 2 minutes work by hand (unless I'm misunderstanding). Schedule company 2 to interview 3 people no-one else wants to interview; it then looks easy (although I'd need to actually do it to be sure) to fully schedule the other interval slots.
Original post by DFranklin
Seems this is about 2 minutes work by hand (unless I'm misunderstanding). Schedule company 2 to interview 3 people no-one else wants to interview; it then looks easy (although I'd need to actually do it to be sure) to fully schedule the other interval slots.

The posted problem does seem to have a trivial solution. I guess it depends on what the actual data/problem really is.
Original post by mqb2766
The posted problem does seem to have a trivial solution. I guess it depends on what the actual data/problem really is.

I have tried various methods by hand and each time, i get a different solution. I don't know even if it's possible to arrive at the optimal solution.

If I have some equations defined, I'll attempt to use Excel's Solver.
Original post by mqb2766
The posted problem does seem to have a trivial solution. I guess it depends on what the actual data/problem really is.

Not sure what you mean by "actual data / problem".

Original post by DFranklin
Seems this is about 2 minutes work by hand (unless I'm misunderstanding). Schedule company 2 to interview 3 people no-one else wants to interview; it then looks easy (although I'd need to actually do it to be sure) to fully schedule the other interval slots.

How might you schedule to the other interview slots?
Original post by doogiedoogs
Not sure what you mean by "actual data / problem".
Just pick the first 9 for company 1, the last 3 for company 2 and the last 6 for company 3. You interview the maximum possible 18 candidates and yes are quite a few solutions where you interview 18 candidates.
(edited 1 month ago)
Original post by mqb2766
Just pick the first 9 for company 1, the last 3 for company 2 and the last 6 for company 3. You interview the maximum possible 18 candidates and yes are quite a few solutions where you interview 18 candidates.

Thanks

I suppose if Company3 wanted to interview Candidate 49 (INSTEAD of 50), you would choose the last 6 for Company 3, EXCLUDING Candidate 49, ie Candidates 19, 27, 28, 33, 38, 45.

That's the tricky part.

My example happens that the Companies have chosen to have "few overlapping" Candidates.

If there were more overlaps, I would guess I need to formulate some algorithm to solve it.
Original post by doogiedoogs
Thanks
I suppose if Company3 wanted to interview Candidate 49 (INSTEAD of 50), you would choose the last 6 for Company 3, EXCLUDING Candidate 49, ie Candidates 19, 27, 28, 33, 38, 45.
That's the tricky part.
My example happens that the Companies have chosen to have "few overlapping" Candidates.
If there were more overlaps, I would guess I need to formulate some algorithm to solve it.

There are multiple solutions for this data the way youve posed the problem. If the data was more overlapping/larger, then yes youd probably need some form of (integer) optimization algorithm. But sometimes the time taken to implement it can be longer than simply solving a few simple problems.
Original post by mqb2766
There are multiple solutions for this data the way youve posed the problem. If the data was more overlapping/larger, then yes youd probably need some form of (integer) optimization algorithm. But sometimes the time taken to implement it can be longer than simply solving a few simple problems.

Yes, I understand.

The example I posted was a trimmed down version of the actual problem.

I was hoping to start of small, with only a few variables, to see how an algorithm might be created and then once (if!) I understand the logic, I can proceed with tacking a more complex problem.
Original post by doogiedoogs
Yes, I understand.
The example I posted was a trimmed down version of the actual problem.
I was hoping to start of small, with only a few variables, to see how an algorithm might be created and then once (if!) I understand the logic, I can proceed with tacking a more complex problem.

Hence the previous post where I was asking if its the actual data/problem. I dont have any experience of the excel solver so Im not sure whats its capable of, but an algorithm would go something like:

Create a matrix of binary cells of size number of companies by number of people they want to interview. Each 1 would represent an actual interview.

Each row has a constraint which is sum over the apprporiate columns <= 3*number of interviewers ( a company can interview at most slots*interviewers people).

Each column has a constraint which is the sum over the rows <= 1. (a person attends at most 1 interview).

The objective is to maximise the sum ofl the appropriate binary elements in the matrix (so sum over the elements which are company by wanted interviewees)

As far as I can see the 3 slots are fairly irrelevant for the algorithm, though as Im working from a simplified example, I cant be certain. Similarly, Ive not carefully checked the above.
(edited 1 month ago)
Original post by doogiedoogs
Not sure what you mean by "actual data / problem".

Original post by doogiedoogs
The example I posted was a trimmed down version of the actual problem.

These two statements are not exactly consistent.

The "best" approach will depend on exactly what the actual problem is (which you haven't told us).
Original post by mqb2766
Hence the previous post where I was asking if its the actual data/problem. I dont have any experience of the excel solver so Im not sure whats its capable of, but an algorithm would go something like:

Create a matrix of binary cells of size number of companies by number of people they want to interview. Each 1 would represent an actual interview.

Each row has a constraint which is sum over the apprporiate columns <= 3*number of interviewers ( a company can interview at most slots*interviewers people).

Each column has a constraint which is the sum over the rows <= 1. (a person attends at most 1 interview).

The objective is to maximise the sum ofl the appropriate binary elements in the matrix (so sum over the elements which are company by wanted interviewees)

As far as I can see the 3 slots are fairly irrelevant for the algorithm, though as Im working from a simplified example, I cant be certain. Similarly, Ive not carefully checked the above.

Thanks, I'll try your suggestion and see what I get.
Original post by DFranklin
These two statements are not exactly consistent.
The "best" approach will depend on exactly what the actual problem is (which you haven't told us).

As I said, I've posted a trimmed down version of the actual problem, hoping that if I can get some algorithm worked out, then hopefully I could have a go at the more complex problem myself.