[gecode-users] First step in constraint progamming
Mailing List Email
mailinglistx at gmail.com
Mon Jun 24 14:44:26 CEST 2013
Attempt at a model:
Model each cpu as a rectangle where one dimension represents time and the
other how much "resources" the cpu has. By resources, we can put an upper
limit on how many tasks it can run in parallel.
Each task then defines how much cpu usage it consumes and how long time it
takes to complete. Each of these parameters is either width or height
depending on which dimension you choose to represent what.
Each task also defines what type of work it is.
Each task defines a priority.
Add constraints to each cpu that tells what type of work it can handle.
Order the tasks such that the highest priority must be before (to the left
or above) the one with the next lower priority.
Each task must be contained inside one of the cpu boxes.
Then make sure no cpu box overlaps, no task boxes overlap and that they are
constrained inside each cpu box (they don't span multiple cpu boxes).
Gecode contains a nooverlap propagator.
I haven't tested it, but maybe it will provide a starting point.
On 15 June 2013 10:24, Philippe K <aqwzsxaqwzsx at orange.fr> wrote:
> 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 at gecode.org
> https://www.gecode.org/mailman/listinfo/gecode-users
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.gecode.org/pipermail/users/attachments/20130624/490ed0fe/attachment.html>
More information about the users
mailing list