0
$\begingroup$

Let's say that I have one task to perform $n$, $n<250000$ times and it takes $p$, $p < 700000$ time to complete it once.

I have list of time constraints ${t_1, t_2, ..., t_n}$ where $t_1<=t_2<=...<=t_n<=10^9$. This list says that $i$-th execution of task cannot be ended earlier than $t_i$.

I want to minimize following sum: $min\sum_{i=1}^{n} (e_i-t_i)$ where $e_i$ tells me when $i$-th execution of task has ended. So I want to minimize a sum of wait-times for each task execution. Example:

$n = 4$; $p=3$; $t=\{1,2,7,15\}$; Answer: 8

Explanation: We start doing first task at time 0 and we end at time 3 (wait-time so far is 2). We start doing second task at time 3 and end at time 6 (total wait-time is 6). We start doing third task at time 6 and end at time 9 (total wait-time is 8). We start doing last task at time 12 and end at time 15 (total wait-time is still 8).

I can easily calculate this sum in O(n) because it's equivalent to: $$\sum_{i=2}^{n} max(0, e_{i-1}+p-t_i) + max(0,p-t_1)$$ $$e_i=max(t_i, e_{i-1} + p)$$ $$e_1=max(t_1, p)$$ but let's say that I have $k$, $k<300000$ tasks, each task has it's own running time $p_j$ and I want for each task with running time $p_j$ calculate minimize above sum (time constraints remains the same for each $p_j$).

A naive approach would give me running time O(n*k). Is there a better way?

$\endgroup$
  • 1
    $\begingroup$ What's the context where you encountered this question? Can you credit the source in the question? What approaches have you tried? Have you tried all reasonable greedy strategies? Have you tried dynamic programming? $\endgroup$ – D.W. Nov 22 '17 at 1:26
0
$\begingroup$

From the description of your problem, it appears that what you are solving is a single machine scheduling problem with release times and no pre-emption. Although your problem description did not explicitly provide release times, one can calculate it by computing $t_i - p_i$ for each task $i$. You should be able to figure out the template of single machine scheduling problem that your problem falls under in the book "Computers and Intractability". For Single machine scheduling problems, minimizing certain objectives can be done in $P$ while for most objectives it is NP complete. I suspect the version of the problem you are interested may be NP complete. If my intuition is correct, then I suggest modelling the problem using CP (constraint programming), since CP is popular for solving sequencing problems.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.