Hi Philippe, Unfortunately I cannot really answer your question as this is a general modeling question and not a dedicated Gecode question.
Best Christian -- Christian Schulte, Professor of Computer Science, KTH, www.ict.kth.se/~cschulte/ -----Original Message----- From: users-boun...@gecode.org [mailto:users-boun...@gecode.org] On Behalf Of Philippe K Sent: Saturday, June 15, 2013 10:25 AM To: users@gecode.org Subject: [gecode-users] First step in constraint progamming Hello Everybody, First of all, my apologize if I've posted this message in the wrong place. Apologies also for my poor english level. I just start in constraint programming and I have difficulties getting the right approach, the good reasoning, to pose my first problem (both mathematically and with geocode). Please, allow me to expose this quite interesting (and fun ?) problem. Given : -------- - A set of CPU - 'Prioritized' tasks (a priority of 1 is the highest priority) And knowing that : ------------------- - A CPU can treat in parallel N tasks - A CPU can only runs certain tasks We have to distribute theses N tasks among these CPU such that we maximize the number of allocated tasks.A distribution is invalid if there exist an allocated task T and an unallocated task T' that have priority. Example 1 : ----------- TASK1 TASK2 MAX // TASKS Priority 2 1 --------------------------------------------------------------- CPU1 affectable affectable 1 --------------------------------------------------------------- CPU1 : { TASK1 } is an invalid distribution since TASK2 has priority but is not affected. CPU1 : { TASK1 TASK2 } is an invalid distribution since the max number of parallel tasks is 1 CPU1 : { TASK2 } valid distribution CPU1 : { } Means 'no distribution', Not considered since we have a non empty valid distribution => CPU1 : { TASK2 } Example 2 : ----------- TASK1 TASK2 MAX // TASKS Priority 2 1 ------------------------------------------------------------- CPU1 affectable affectable 1 CPU2 not affectable affectable 2 ------------------------------------------------------------- CPU1: { } , CPU2: { TASK1 TASK2 }: invalid distribution, Task 1 not affectable to CPU2 CPU1: { TASK1 } , CPU2: { TASK2 } : valid distribution CPU1: { TASK2 } , CPU2: { TASK1 } : invalid distribution, Task 1 not affectable to CPU2 CPU1: { TASK1 TASK2 }, CPU2: { } : invalid distribution, only 1 tasks affectable to CPU1 CPU1: { } , CPU2: { } : Not considered since we have a non empty valid distribution Example 3 : ----------- Now let's take this final example and refine it step by step. TASK1 TASK2 MAX // TASKS Priority 2 1 ----------------------------------------------------- CPU1 affectable affectable 2 CPU2 affectable affectable 2 ----------------------------------------------------- CPU1: { } , CPU2: { TASK1 TASK2 } : valid distribution CPU1: { TASK1 } , CPU2: { TASK2 } : valid distribution CPU1: { TASK2 } , CPU2: { TASK1 } : valid distribution CPU1: { TASK1 TASK2 }, CPU2: { } : valid distribution CPU1: { } , CPU2: { } : Not considered since we have a non empty valid distributions. --------------------------------------------------------------------------- If we have multiple valid distributions, we prefer the one where the "Task (+ pending task) per CPU" is "well balanced" across CPUs for instance, with 3 CPU, the 'balance' of a distribution is : |(nbAffectations(CPU1)+nbPendingTask(CPU1))- (nbAffectations(CPU2)+nbPendingTask(CPU2))| + |(nbAffectations(CPU1)+nbPendingTask(CPU1))- (nbAffectations(CPU3)+nbPendingTask(CPU3))| + |(nbAffectations(CPU2)+nbPendingTask(CPU2))- (nbAffectations(CPU3)+nbPendingTask(CPU3))| --------------------------------------------------------------------------- TASK1 TASK2 MAX // TASKS NB_PENDING_TASK Priority 2 1 ----------------------------------------------------------------------- CPU1 affectable affectable 2 0 CPU2 affectable affectable 2 0 ----------------------------------------------------------------------- CPU1: { } , CPU2: { TASK1 TASK2 } : rejected, not the best balance |0+0 - 2+0| = 2 CPU1: { TASK1 } , CPU2: { TASK2 } : best balance|1+0 - 1+0| = 0 CPU1: { TASK2 } , CPU2: { TASK1 } : best balance : |1+0 - 1+0| = 0 CPU1: { TASK1 TASK2 }, CPU2: { } : rejected, not the best balance |2+0 - 0+0| = 2 ---------------------------------------------------------------------------- But since we have more than one potential distribution, we prefer the one where the "global affinity" is maximized. The "global affinity" of a distribution could be expressed as : Sum(CPUi) (Sum(Taskj) (isAffected(CPUi,Taskj)*Affinity(CPUi,Taskj))) ---------------------------------------------------------------------------- TASK1 TASK2 MAX // TASKS Priority 2 1 ---------------------------------------------------------------------------- CPU1 affectable, affinity = 3 affectable, affinity = 1 2 CPU2 affectable, affinity = 2 affectable, affinity = 4 2 ---------------------------------------------------------------------------- CPU1: { TASK1 } , CPU2: { TASK2 } : affinity= (1*3 + 0*1) + (0*2 + 1*4) = 7 CPU1: { TASK2 } , CPU2: { TASK1 } : affinity= (0*3 + 1*1) + (1*2 + 0*4) = 3 Final solution : CPU1 : { TASK1 } , CPU2 : { TASK2 } ---------------------------------------------------------------------------- To speak honestly, I've absolutely no idea of how to express this problem in a 'programming constraint' way. Is this can be expressed using geocode ? Any help would be greatly appreciated to prototype this. Philippe _______________________________________________ Gecode users mailing list users@gecode.org https://www.gecode.org/mailman/listinfo/gecode-users _______________________________________________ Gecode users mailing list users@gecode.org https://www.gecode.org/mailman/listinfo/gecode-users
