algorithms – How to mathematically formulate the constrained planning problem next?

Let's say you have a period of time [p0, p1], a list of tasks l = [t1, …, tn] and a duration for each task d = [d1, …, dn]. In addition, each task is performed by a resource ri (as a first approximation, we could consider this resource as unique, but more generally, each task can have a different degree of "parallelism").

The goal is to group the largest number of these lists (not the largest number of tasks).

The constraints are as follows (I know some look like other goals, but be indulgent):

• minimize the waiting time between each task
• minimize the waiting time of the resource
• Some tasks must be performed at a location in the list (for example: task t1 must always be done first, but task t3 can be performed at any location in the list).
• no task can start or finish outside the period
• for each task, you can not use more than available resources

I'm trying to formulate this to make it solvable by a solver (eg, CPsolver). That's what I've done so far:

The data:

• m = number of tasks
• n = number of lists to be included in the period
• l = [t1, …, tn]
• p = [p0, p1]
• ls = [l1, …, lm] the lists to be wrapped in the period
• pi = number of resources for task i

variable:

• sij = timestamp of start of task ti for list lj

constraint:

• Struggling for this part (mostly because I can not easily express the waiting time)

objectives:

• Find the highest m of this constrained problem for which a solution exists

Could you help express the constraints?

If not, if you doubt my approach, could you dispute it?

Posted on