A subproblem of something I'm solving is to determine the optimal intermediate waiting times in a sequence of $n$ jobs. Each job $i$ has an associated waiting time $w_i$ followed by its processing time $p_i$ (the job $i$ is initiated at $\sum_{k=1}^{i-1}(w_k + p_k) + w_i$ and finishes at $\sum_{k=1}^{i}(w_k + p_k)$). Furthermore, each job has a time window $[a_i, b_i]$ such that if it starts outside of it, a penalty is incurred. Finally, the complete sequence of jobs has a due date $D$ such that a linear penalty is incurred if the makespan exceeds it. The full problem is (where the only variables are the $w_i$'s):
$\arg \min_{\mathbf{w} \in \mathbf{R}^n} \left(\lambda_0 \sum_{i=1}^n (w_i + p_i) + p(\mathbf{w}) + \lambda_{n+1} d(\sum_{i=1}^n (w_i + p_i))\right)$
$w_i \geq 0, i=1,\ldots,n$
$p(\mathbf{w}) = \sum_{i=1}^n \lambda_i \max(0, \sum_{k=1}^{i-1}(w_k + p_k) + w_i - b_i, a_i - \sum_{k=1}^{i-1}(w_k + p_k) - w_i)$
$d(s) = \max(0, s-D)$
Currently, I'm using an LP solver to find the solution to this problem, but I feel that there are some problems with this approach.
I plan to deploy my full script to the web, and I expect to not get great performance using an LP solver through Javascript (if that even exists).
This problem has to be solved repeatedly, and so every performance gain is welcome, and I suspect a specialized method to yield a significant gain.
I was able to use the subdifferential KKT conditions to solve the case of a single waiting time in the sequence of $n$ jobs, but was not able to generalize this. Can someone give me some pointers on approaches I could take to tackle this problem?
