3
$\begingroup$

I'm trying to setup a primary and secondary on call schedule with 6 people.

I'm trying to schedule people to be on call, so that they will be paired with everyone and they have the longest "break" between their schedules.

Ex for one rotation: 

week:      1 2 3 4 5 6 7 8 9 10 11 ... 
primary:   1 2 3 4 5 6...?
secondary: 3 4 5 1 2 4...?

Week 1 has people are {1,3}
Week 2 has people are {2,4}

Person 1 has a two week "break" before they're on shift again.
Person 2 has a two week "break" before they're on shift again.

Also, a person can't be both primary and secondary on the same week, ex: {3,3}.

What's the best way to generate a sequence like this, for any number of people so that they have the longest "break" between their shifts, and they are paired with someone different as much as possible?

|cite|improve this question|||||
$\endgroup$
  • 2
    $\begingroup$ I don't understand your requirements. Can you formulate them using mathematical language? $\endgroup$ – Yuval Filmus Aug 22 '18 at 2:25
  • $\begingroup$ Is the following a good solution? The primary repeats 123456, and the secondary is 123456 234561 345612 456123 561234 612345, with a rotation of at least 5 (assuming I guessed the meaning correctly). $\endgroup$ – Yuval Filmus Aug 22 '18 at 2:28
  • $\begingroup$ What is a "rotation"? How is the length of a rotation defined? What are you trying to maximize? Is there a single quantity you're trying to optimize? $\endgroup$ – D.W.♦ Aug 22 '18 at 9:18
  • $\begingroup$ Is there a distinction between a primary call and secondary call? As far as I can check, we can substitute "two-person on call schedules" for "a primary and secondary on call schedule", changing the example to a sequence of unordered pairs {1, 3}, {2, 4}, {3, 5}, {4,1}, {5,2}, {6,4}, etc as well. $\endgroup$ – John L. Aug 24 '18 at 8:46
  • $\begingroup$ I think the unordered pairs is a good way to think about it. What would be the best way of having everyone be as far apart in in the sequence. Ex: week 1: {1,2}, week 2: {1,3} is not good because 1 has severed 2 consecutive weeks week 1: {1,2}, week 5: {1,2} is not great because 1 and 2 have severed together already. $\endgroup$ – Kevin Aug 26 '18 at 0:22
3
$\begingroup$

Given $n$ persons, this question is about a sequence of unordered pair of persons, called a two-person schedule(TPS). A TPS is good if any of its initial contiguous subsequences satisfies the following two conditions.

(fairness requirement) Any person cannot appear two times more than any other person.

(non-repeating requirement) Any unordered pair of persons can appear at most once.

This question asks the best way to generate a good TPS that is as long as possible.

Let us define a perfect TPS as a TPS that satisfies the following requirement.

(inclusive requirement) Each unordered pair of persons is included.

It turns out that a good TPS of the longest length must be a perfect TPS.

In fact, if each unordered pair of person compete with each other, this question is none other than the round-robin tournament as explained by Wikipedia, which has complete solutions. Because of the durability and reliability of wikipedia as well as the size of the solutions, readers are encouraged to check the wikipedia item as well as the references listed thereof. Also there are plenty of resource on the web if you search for "round robin tournament scheduling", such as a nice explanation of Round Robin Tournament Schedule and Javascript code to schedule round robin tournament.

A program that produces Perfect TPS

You can play with a scheduling algorithm in this Javascript playground. Modify the number of persons as you want to on the last line of the code, document.writeln(JSON.stringify(robin(8))). Hit Run code button. You will see output like the following.

[[[1,8],[2,7],[3,6],[4,5]],[[1,7],[8,6],[2,5],[3,4]],[[1,6],[7,5],[8,4],[2,3]],[[1,5],[6,4],[7,3],[8,2]],[[1,4],[5,3],[6,2],[7,8]],[[1,3],[4,2],[5,8],[6,7]],[[1,2],[3,8],[4,7],[5,6]]]

|cite|improve this answer|||||
$\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.