Scheduling Problem

Source: Asked to me by Piyush Sao (EE IITM 2011 Alumnus, Georgia Tech Grad Student). He got it from IBM Ponder This May 2012 (http://domino.research.ibm.com/Comm/wwwr_ponder.nsf/Challenges/May2012.html)

Problem:

There are six sets of jobs. Each set is performed on a different server and each set contains jobs that take 1,2,3,...,10 minutes to run.
Obviously, all six sets would end up in 55 minutes.

Schedule all the sets such that if all six servers start together, on minute 0, a job would end on every minute from 1 to 54, and all six servers would end on minute 55 together.
Please supply the solution as six lines of ten numbers.

A solution for a smaller problem of four sets of six jobs ending every minute from 1 to 20 is:
2 1 5 4 6 3
1 3 6 4 5 2
5 2 4 6 3 1
6 3 4 2 1 5

Update: (19-07-2012)
Solution posted by Piyush Sao(EE IITM 2011 Alumnus, Georgia Tech Grad Student) in comments! I could not solve it.

Comments

  1. I have n't solved it yet but I got a little insight into the problem which I thought I should share:
    Since the problem is symmetrical seen from 0 minutes proceeding forward in time or from 55th minute going backrward in time, we can expect a symmetrical solution to exist. Proceeding thus satisfying constraints and doing what is mandatory to get a particular job-end, we can arrive at one such solution for the reduced case:
    1,3,6,4,2,5
    2,1,5,4,3,6
    5,2,4,6,3,1
    6,3,4,5,1,2

    Reply Delete

  2. Infact, I have a solution set obtained by hand:

    1 3 8 7 - - 5 4 6 10
    2 1 4 7 10 8 5 3 6 9
    5 1 7 9 - - 4 6 3 8

    Dashed slots can be filled with both possible pairs

    Reply Delete

  3. I just realised the previous solution is flawed.

    Reply Delete

  4. here is my solution:


    1, 5, 6, 2, 8, 9, 10, 3, 4, 7
    2, 6, 7, 4, 8, 5, 10, 9, 1, 3
    3, 6, 7, 4, 8, 2, 10, 5, 9, 1
    4, 6, 7, 8, 9, 3, 10, 2, 1, 5
    5, 6, 7, 8, 9, 3, 1, 4, 10, 2
    7, 6, 8, 2, 1, 5, 4, 3, 10, 9

    Reply Delete

  5. @piyush.. how did you come up with this solution? Thanks

    Reply Delete

  6. The solution on IBM's site:
    1 8 3 2 5 9 7 T 4 6
    2 5 T 9 7 1 6 4 8 3
    5 3 8 2 6 1 7 T 9 4
    4 9 T 7 1 6 2 8 3 5
    3 8 4 6 1 7 9 T 5 2
    6 4 T 7 9 5 2 3 8 1

    where T is 10 (used for formatting purposes):)

    http://domino.research.ibm.com/Comm/wwwr_ponder.nsf/solutions/May2012.html

    Reply Delete

  7. How are all these solutions arrived at? Heuristics?

    Reply Delete


  8. Wonderful blog & good post.Its really helpful for me, awaiting for more new post. Keep Blogging!








    Patient Appointment Scheduling

    Reply Delete

Post a Comment

[フレーム]

Popular posts from this blog

Buying Dimsums

Source: Alok Goyal (Stellaris VP, Ex-Helion VC) puzzle blog Problem: A fast food restaurant sells dimsums in boxes of 7 and 3. What’s the greatest number of dimsums a person cannot buy. Generalize it for p and q where p and q are relatively prime. I loved the puzzle. Hope you enjoy it too.

Polya's Urn Problem

Puzzle: There are two urns with one ball each. Each of subsequent n-2 balls is placed into one of these urns, with probability proportional to the number of balls already in that urn. What is the expected number of balls in the smaller sized urn? Source: P. Winkler's Puzzles book. (Chapter: Probability). Solution: Highlight the part between the * symbols for the answer. * This problem can be reformulated as the following problem. Suppose I have a stack of black cards and one red card. Initially I take red card in my hand. Now I add black cards randomly between any two cards (so, initially its either above or below red). Note that the probability that I add the card above the red card, when x-1 is the number of cards above red and y-1 is the number of cards below red is x/(x+y). Let the problem be if red card is dividing the black cards into two sets, what is the expected number of black cards in the smaller section. So, we see that the two problems are equivalent. No...

Fraction Brainteaser

Source: Sent to me by Gaurav Sinha Problem: Siddhant writes a Maths test and correctly answers 5 out of 6 Arithmetic questions and 20 out of 28 Geometry questions.  In total, Siddhant scores 25 out of 34.  Vaibhav writes another Maths test and correctly answers 20 out of 25 Arithmetic questions and 6 out of 9 Geometry questions. in total, Vaibhav scores 26 out of 34. Note that a) Vaibhav scores more than Siddhant b) Siddhant score better than Vaibhav in both individual topics -  5/6 > 20/25 and 20/28 > 6/9 How is it possible?