0
$\begingroup$

I have an optimization problem where there are $n$ activities and I want to find an optimal schedule of those activities.

The schedule is specified as $S=(\mathbf{t},p)$ where:

  • $\mathbf{t}=\left(t_{1},\dots,t_{n}\right)$ specifies the times allocated to the activities
  • $p$ is the ordering of the activities, so is a member of the set of permutations over $n$ elements.

The constraint is mainly that there is a finite total time, so $\sum{}_{i=0}^{n}t_{i}=T$. There is also the constraint that, for all $i$, $t_{i}>0$.

The objective function, to be maximized, is $F(\mathbf{t},p)$; to keep the question brief I'll mention the form of $F$, in case it is relevant, after the question.

The question is how to put this optimization problem into Mathematica. There would be tens of variables, so I cannot exhaustively go over all permutations, but some heuristic/local-search algorithm probably would do a fine job; I don't need the global maximum.

My main problem is with $p$, namely putting in the order of the activities. Without the order I can put it into Mathematica with NMaximize as follows:

NMaximize[
  { 
     u1[t1]+u2[t2]+u3[t3],
     {t1+t2+t3==365,t1>0,t2>0,t3>0}
  },{t1,t2,t3}
]

I just showed an example with 3 variables for brevity, but I can do a similar thing with tens of variables as well and it seems to work fine.

Extra idea: Perhaps another way to model it is by specifying $2n$ variables, a start time and end time for each activity, and somehow produce all the constraints that two activities should not overlap. This would leave the possibly of there being "dead time" without activity, but that should be fine.

Information about the form of $F$ (in case it is relevant)

$$ F(\mathbf{t},p)=\sum\limits_{i=0}^{n}\left(u_{i}\left(t_{i}\right)-p_{i}\left(s_{i}\right)\right) $$

where:

  • $u_{i}$ is a utility/benefit of putting $t_{i}$ time into activity $i$; I'll specify it for each activity and it would be some monotonically increasing function but not linear in general.
  • $s_{i}$ is the starting time of activity $i$, which equals the sum of the $t_{i}$ for the activities that come before it (as per the order specified by $p$). So, $s_{i}$ depends on both $p$ and $\mathbf{t}$.
  • $p_{i}$ is a penalty function which gives a decrease in utility/benefit due to the activity being delayed by $s_{i}$ time.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.