HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Primary/Secondary On Call Rotations

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
secondarycallrotationsprimary

Problem

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?

Solution

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 this 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]]]

Context

StackExchange Computer Science Q#96484, answer score: 3

Revisions (0)

No revisions yet.