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.
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.
I have n't solved it yet but I got a little insight into the problem which I thought I should share:
ReplyDeleteSince 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
Infact, I have a solution set obtained by hand:
ReplyDelete1 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
I just realised the previous solution is flawed.
ReplyDeletehere is my solution:
ReplyDelete1, 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
@piyush.. how did you come up with this solution? Thanks
ReplyDeleteThe solution on IBM's site:
ReplyDelete1 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
How are all these solutions arrived at? Heuristics?
ReplyDelete
ReplyDeleteWonderful blog & good post.Its really helpful for me, awaiting for more new post. Keep Blogging!
Patient Appointment Scheduling