0
$\begingroup$

This is real-world problem, but I need to model it with algorithm as I am going to implement it (probably with PostGIS and Google Maps).

Problem is:

Everyday I am receiving job offers, and I have to schedule interview with them. I have already noticed, that there are two "hot" areas, where is large amount of offices, and around $30-40\%$ of all interviews are taking place in those two spots. I want to go to all interviews, however I want to start working at the end of this month, and this means, I won't be able to meet all employers, if I won't cluster them.

My modeling approach:

The most simple version of this is of course Vehicle routing problem however, in real life I am not getting all $100$ offers with location at the same time, but rather smaller amount ($5-10$) every day, and at the same time so I cannot wait to gather all of them to start computing. This means that I need greedy solution. Additional constraint is that not every recruiter will accept any hour. It can be assumed, that I can do interviewing from $10:00$ to $19:00$, one interview takes $1$ hour, last interview can start at $18:00$. Given $2$ points, I am able (using Google Maps) to tell distance between them (counted in minutes). They can be broken down into three abstraction classes - near (0-15 minutes), medium (16-30), far (31-45). I am not accepting interviews farther than $45$ minutes away. Being late less than $10$ minutes, rescheduling meeting at most one time and offering recruiter less than four dates are constraints for professionalism, and can be exploited, only if this will allow me to schedule additional interview (being late $10$ minutes implies fact, that interview will end $10$ minutes later than expected). Interviews are taking place from Monday to Friday. It is also possible to hold response to offer for $24$ hours. From my empiric experiment, expected time to receive job offer by email is $10:00$ each day (most at Mondays), with standard deviation of $1$ hour.

Current algorithm:

I am pessimistically assuming, that I will be 15 minutes late for every interview and every two locations are at maximum distance, that is $45$ minutes. In addition to $1$ hour of interview, it given me two full hours per each interview. Considering hours, each day is broken down into five free sports for interviews, starting at $10$, $12$, $14$, $16$ and $18$. I am maintaining list of all open spots for all days in week (five working days) and I am sending full list to each and every recruiter. First recruiter that accepts free spot is assigned to it, and I am marking spot as occupied in Google Calendar, and telling every next recruiter, that he needs to pick other date. When I will see, that recruiter wants to meet somewhere near (0-$15$ minutes) other location, and in the same time, next spot is open, I am suggesting this spot. If he accepts, I am appending him there, and then shifting all starting hours after him by plus 1 hour. If he does not accept, I am offering all available dates. As You can see, this algorithm guarantees me $5$ days times $5$ spots, $25$ interviews each week, plus around $2-3$ more from clustering near interviews. I need at least $30$ guaranteed spots to attend all meetings, and it would be great if it could be $35$, so I could finish them faster and be able to offer more dates for last interviewers. I am also trying to reschedule interviews, so that no two interviews, that first is immediately after seconds, are far, however, rescheduling is transactional operation, that usually takes around $24$ hours.

Goal:

I am trying to figure out algorithm, that given current state of my Google Calendar (that includes start time and location of each interview) and set of buffered offers, will allow me to maximize amount of scheduled meetings. It can be assumed, that I am immediately informed about each offer (I have mobile Internet). I have same problem each year (as a full-time student, I am looking for job at the start of holidays and dropping it at the end of holidays), and as I suspect to study 5 more years, I need efficient solution.

$\endgroup$
  • $\begingroup$ Your description is quite long, I tried to emphasis a bit and make hours shorter (you are using 24h format, that is ok). Feel free to change something or if you can make it shorter it will be easier to read. $\endgroup$ – Evil Jun 27 '16 at 0:17
  • $\begingroup$ As a >>real-world<< problem, it's silly to plan your interviews this way. Prioritize the ones that you think are most likely to best advance your educational/career goals. And once you get a job, do a spectacular job, so you'll have good references and maybe even a future full-time job offer. And just >>don't<< be late -- "you never get a 2nd chance to make a 1st impression". If you're intellectually curious about this as a textbook/homework problem, that's fine. But scheduling your interviews this way is a >>big<< mistake. $\endgroup$ – John Forkosh Jun 28 '16 at 5:27
  • $\begingroup$ We are already talking about filtered interviews - not everyone. So all of them are able to advance my goals. I already have so much references, that only Google or Oracle can improve my CV, but I intentionally do not apply to them before I finish my studies, so I won;t have to dump them in the middle of semester. Algorithm like this is my only chance to meet and talk with all of them. $\endgroup$ – spam Jun 28 '16 at 20:19
  • $\begingroup$ Oh, okay, but your Problem Is: paragraph states "I want to go to all interviews...", without (unless I'm missing it) that "filtered" qualification. Anyway, suppose this algorithm allows you an additional $m$ interviews. But the time it takes to specify, design, code, debug, and enter all the data for it costs you $n$ interviews. I'd guess $n>m$. $\endgroup$ – John Forkosh Jun 30 '16 at 4:19
  • $\begingroup$ I didn't want to twist this question any more with filters. By "all" I mean "all filtered that we consider". I am going to use this algorithm for at least 6 years, so it is worth it. $\endgroup$ – spam Jun 30 '16 at 18:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.