I am currently working on software that deals with a specific type of scheduling problem, and I want to improve the scheduling algorithms that it uses.
However, when I tried to research algorithms the information I found deals mostly with a much different kind of scheduling problem.
In my problem, the givens are:
- A set of $J$ jobs. Each job $j$ has an availability interval with start and end times $[s_j,e_j]$.
- A reward function $R(j,t)$ which gives the utility of processing a job for a given amount of time.
- A changeover time function $C(j,j',t)$ which gives the amount of time required, starting at a time $t$, to switch from job $j$ to job $j'$.
- A set of $M$ minimum time constraints. Each constraint $m$ has an associated set of jobs $J_m$ and a minimum time $c_m$.
The solution is a list of jobs and intervals: $\{(j_1,I_1),(j_2,I_2),\ldots,(j_N,I_N)\}$.
The constraints are:
- Each interval must fall within the corresponding job's availability interval: $I_n\subseteq[s_{j_n},e_{j_n}]$.
- There must be adequate changeover time between jobs: $$\max I_n + C(j_{n},j_{n+1},\max I_n)\leq \min I_{n+1}$$
- The minimum time constraints must be met: $$\sum_{\substack{n=1 \\ j_n\in J_m}}^{N}\left|I_n\right|\ge c_m $$
The objectives are (multiobjective optimization):
- (Primary) Maximize the reward given by: $$\sum_{n=1}^{N}R(j_n,\left|I_n\right|)$$
- (Secondary) Minimize the amount of "idle" time (idle time is the "slack" in the changeover constraint): $$\sum_{n=1}^{N-1}\left(\min I_{n+1}-\max I_n\right) - C(j_{n},j_{n+1},\max I_n)$$
- (Secondary) Minimize the longest idle (same as previous with $\max$ replacing $\sum$).
Has this type of problem been studied? If so, what names is it usually called by?