1
$\begingroup$

I have a problem I've been dealing for the past few days, and I'm pretty stuck.

Each user has a schedule for a given week, such as Mondays 9:00-12:00 and 14:00-18:00, Tuesdays... and so on. Each provider has another schedule for himself.

The problem is: Get the best k (different) solutions such that each solution assigns the minimum amount of providers to cover the entire schedule from the user? Where a solution is a set of pairs (Provider, schedule he will cover) and two solutions are considered equal if they contain the same providers (and different if they are not equal).

Also, take into account that any day could be split in sub-intervals and assigned to different providers. An example for a solution for the schedule shown before could be: {(Provider1, Monday 9:00-12:00), (Provider1, Monday 14:00-16:00), (Provider1, Monday 16:00-18:00)}

I've been looking into the Interval Partitioning Problem, Bipartite Matching Problem, and Assignment Problem, and none of them seem to adjust to my case.

Any ideas on how I could model this problem?

$\endgroup$
  • $\begingroup$ Note that in general, scheduling problems are hard to solve. If it turns out that no efficient algorithms are known for your specific problem (or even that such algorithms are unlikely to exist), you could take a look at techniques such as constraint satisfaction, where you simply make a model without worrying about efficiency and leave the solving to specialized algorithms in existing software packages. $\endgroup$ – Discrete lizard Jan 23 at 17:51
1
$\begingroup$

I think your problem is actually not a scheduling problem but a set cover problem. Just cut the time line in the atomic time parts of providers and assign them indices.

For instance, considring only one day for user from 8h to 14h:

  • provider 1: 7h-10h
  • provider 2: 6h-9h
  • provider 3: 10h-16h

The cut-off is:

  1. 6h-7h
  2. 7h-9h
  3. 9h-10h
  4. 10h-16h

and your problem is solving the minimum set cover of {2, 3, 4} with:

  • provider 1: {2, 3}
  • provider 2: {1, 2}
  • provider 3: {3, 4}

with evident solutions providers 1&3 or 2&3.

Nevertheless, this is a NP-problem and you likely have to test most of combinatoric if you really want to get optimal solutions. Sometimes this type of application contain some constraints or patterns that may help you to reduce the problem.

$\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.