siddhartham
December 5th, 2006, 04:26 AM
I am currently working on a project where I got stuck with a progamming problem.
Please give your ideas on solving this one:
I have 16 links (maybe connecting two devices in a network).
The task is to allot slots out of 1 to 582 for each of these links so that their slot requirements are satisfied.
The constraint equation governing the slot requirements is given by :
ni - represents the total number of slots required by the ith link.
n1+n2+n3+n4 <= 582
n5+n6+n7 <=582
n8+n9+n10 <=582
n11+n12+n13 <=582
n14+n15+n16 <=582
n5+n8+n11+n14<=582
n1+n9+n15 <=582
n2+n6+n12 <=582
n3+n10+n16 <=582
n4+n7+n13 <=582
I solved these and got the slot requirement values as :
n1=85 n2=205 n3=205 n4=85 n5=6 n6=317 n7=168 n8=285 n9=221 n10=52 n11=285 n12=52 n13=221 n14=6 n15=168 n16=317
The objective is to assign slots to these links such that the links in a given constraint do not have overlapping slots.
i.e.
Let me explain with an example:
now n1 needs 85 slots
I have to assign it slots between 1 to 582 not neccesarily continuous...but make sure that none of these slots overlap with that assigned to n2,n3,n4,n9,n15
these i got from these equations :
n1+n2+n3+n4 <= 582
n1+n9+n15 <=582
suppose i assign for n1 slot no. 1 to 85...then none of n2,n3,n4,n9,n15 should be assigned a slot in this range....
The result I should get in the end is a 16x582 slot matrix with each row representing a link and column representing a slot.
If a link is active in a slot that column corresponding to it should be made 1 else 0.
The only solution I currently have for this is bruteforce which has complexity of 16! which I can never find the answer to.
Hope you understand the question that I am asking you.
Thanking you in advance for helping me out.. :)
Please give your ideas on solving this one:
I have 16 links (maybe connecting two devices in a network).
The task is to allot slots out of 1 to 582 for each of these links so that their slot requirements are satisfied.
The constraint equation governing the slot requirements is given by :
ni - represents the total number of slots required by the ith link.
n1+n2+n3+n4 <= 582
n5+n6+n7 <=582
n8+n9+n10 <=582
n11+n12+n13 <=582
n14+n15+n16 <=582
n5+n8+n11+n14<=582
n1+n9+n15 <=582
n2+n6+n12 <=582
n3+n10+n16 <=582
n4+n7+n13 <=582
I solved these and got the slot requirement values as :
n1=85 n2=205 n3=205 n4=85 n5=6 n6=317 n7=168 n8=285 n9=221 n10=52 n11=285 n12=52 n13=221 n14=6 n15=168 n16=317
The objective is to assign slots to these links such that the links in a given constraint do not have overlapping slots.
i.e.
Let me explain with an example:
now n1 needs 85 slots
I have to assign it slots between 1 to 582 not neccesarily continuous...but make sure that none of these slots overlap with that assigned to n2,n3,n4,n9,n15
these i got from these equations :
n1+n2+n3+n4 <= 582
n1+n9+n15 <=582
suppose i assign for n1 slot no. 1 to 85...then none of n2,n3,n4,n9,n15 should be assigned a slot in this range....
The result I should get in the end is a 16x582 slot matrix with each row representing a link and column representing a slot.
If a link is active in a slot that column corresponding to it should be made 1 else 0.
The only solution I currently have for this is bruteforce which has complexity of 16! which I can never find the answer to.
Hope you understand the question that I am asking you.
Thanking you in advance for helping me out.. :)