Designing a scheduling algorithm

Question

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.

• Raphael: "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".

Answer 1

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.