1
$\begingroup$

I have only intro CS under my belt, so I'm looking for some fast advice. I want to write a scheduling algorithm for the following scenario.

I have customers who have selected how many hours they want and what times they are available (choosing in 4 hour increments). I have 1 service person I then need to schedule to maximize the number of hours scheduled (so only 1 service person at a time). There is no ranking of preferences by customers, just a binary availability for each time slot and a number of hours. My thought was to start with the biggest job, schedule that, and then work downwards greedy-style. I also thought this must be a well-known problem. Can someone tell me the name of this 'problem' or what else I should be looking at? I can also restructure the inputs if that would help finesse this into an optimized algorithm that exists out there.

$\endgroup$
  • $\begingroup$ "so I'm looking for some fast advice" -- not always fast, but sure: literature. There's bound to be mounds of work on this, and "scheduling" is already the correct term to search for; add "single machine". $\endgroup$ – Raphael Mar 18 '15 at 7:07
3
$\begingroup$

Since a customer must either be assigned all the requested hours or none at all, this problem is $NP$-complete. This can be seen by reduction from Exact Cover.

A polynomial algorithm is unlikely to exist. Starting with biggest job first might be a reasonable heuristic for many cases, but there are no performance guarantees.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.