1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Scheduling problem

  1. Feb 28, 2016 #1
    Hi everyone,
    a problem that seems mathematical in nature came to my mind at work a few days ago, and I wonder if anyone can help me with it.

    Basically, we are given a schedule of when certain biological assays take place, e.g. assay A will take place each even week of the year starting on week 2, and assay B will take place every 4 weeks starting on week 1.
    It's relatively easy to write out the explicit cases:
    What I wanted to know was on which weeks there were no assays. Again, easy enough to write it out:
    And whether A and B could happen on the same week. Clearly not, as A only happens on even weeks, whereas B only happens on odd weeks.

    But I wanted to make this more systematic. I started by noting that A corresponded to a 2*n pattern, with n positive integer, and B to 2*m+1, with m positive integer or zero.
    Then I wondered how I could derive the pattern for no_assays (of course 4*k-1, with k positive integer) just from the patterns for A and B, without writing out the explicit cases.
    Maybe not in a simple case like this one, but in a more complicated one. E.g. if there were 3 assays A, B and C, with A on weeks 3*n+1, B on weeks 4*m, C on weeks 5*p, with n, m and p positive integers, how could I determine if+when+which assays happen on the same week, and if+when there are weeks with no assays?

    Is there an 'official' approach one may use for this kind of problem? Maybe something related to Diophantine equations?

    Thank you!
  2. jcsd
  3. Feb 28, 2016 #2


    User Avatar
    2017 Award

    Staff: Mentor

    If there would be an easy general approach you could use it to find prime numbers - and there is no easy way to find arbitrary prime numbers.

    It is sufficient to consider all weeks up to the least common multiple of all periods, e.g. 4 in the first example and 60 in the second one. Although 60 weeks are more than a year, so basically you are testing each week anyway.
    Sometimes it can be sufficient to check the intersection of (AB), (BC) and (AC), which gives 12, 15 and 20 weeks to check, so you save a bit compared to 52 checks. An additional trick: within those given lengths, the pairs will have a common exam week exactly once, and there are ways to calculate this week quickly.
  4. Feb 28, 2016 #3
  5. Feb 29, 2016 #4
    Thank you both very much!
    Much of the maths in the wikipedia article is above my level, but I think the algebraic solution by sequential substitution is something I could manage to use.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook