2
$\begingroup$

I have a scheduling problem as follows. At each time $t=1,2,\ldots,T$, a set of $n$ jobs arrives where job $j$ has a cost $c_{j,t}$ and a budget $b_{j,t}$ which are revealed to the decision maker for all jobs. The cost $c_{j,t}$ is sampled from the cdf $e^{-A/x}$ for given positive $A$. The budget $b_{j,t}$ is sampled from the cdf $1-e^{-\lambda x}$ for given positive $\lambda$.

At each time $t=1,2,\ldots,T$, the decision maker has to either accept the job $j$ and schedule it at $t$ or discard it and it can accept at most one job for each time $t$. The decision maker can accept the job $j$ at time $t$ only if $c_{j,t}\leq b_{j,t}+\sum_{s=1}^{t-1}(b_{j,s}-x_{j,s}c_{j,s})$, where $x_{j,s}=1$ iff the job $j$ was accepted at time $s$.

The objective is to minimize the sum of the largest gaps, that is, if the job $j$ is accepted at times $t_{j,1}, t_{j,2}, \ldots, t_{j,n_j}$, then the objective is to $\text{minimize } \sum_{j=1}^n\max_{i=1,\ldots,n_j-1}(t_{j,i+1}-t_{j,i}-1)$.

A gap is the number of consecutive idle times. An idle time is where no job was accepted.

Here is an example: If no job is ever accepted, then the largest gap for each job is $T$ (I may assume that jobs are accepted at $t=0$ and at $t=T+1$). Thus, the objective is $nT$.

Let me give an example. If the following decision is made: $x=[0,1,1,2,0,1,3,2,0,1,2,3]$ where there are $3$ jobs and $T=12$. In this case, job $1$ is scheduled at times $2,3,6$, and $10$, job $2$ is scheduled at times $4,8$, and $11$, and job $3$ is scheduled at times $7$, and $12$. Thus, the gaps for job $1$ are $1$ (it is not accepted at time $1$), $2$ (it is not accepted at times $4$ and $5$), $3$ (it is not accepted at times $7$, $8$, and $9$), and $2$ (it is not accepted at times $11$ and $12$). Thus, the largest gap is $3$. Similarly, the largest gap for job $2$ is $3$ and the largest gap for job $3$ is $6$.

I am trying to solve this problem optimally (or suboptimally at least) in an online fashion. Online fashion here means that at time $t$, the decision maker knows only the values of $c_{j,1}$, $c_{j,2}$, $\ldots$, $c_{j,t}$, and $b_{j,1}$ ,$b_{j,2}$, $\ldots$, $b_{j,t}$ and $x_{j,1}$ ,$x_{j,2}$, $\ldots$, $x_{j,t}$ (It does not know future values of $c_{j,t+1}$, $c_{j,t+2}$, $\ldots$, $c_{j,T}$, and $b_{j,t+1}$ ,$b_{j,t+2}$, $\ldots$, $b_{j,T}$.)

I solve this problem using integer programming (in an offline fashion) and obtained the optimal offline solution.

I implemented a deep q learning solution that performed very badly compared to the optimal offline. The MDP that I used is as follows. The state is given by the actual time $t$, the cost $c_{j,t}$ and the budget $b_{j,t}$ and the decision variables $x_{j,t}$ for all jobs $j=1,2,\ldots,n$. So there are $T$ states. The action is either $0$ (do not accept any job) or $j$ (accept job $j$). The reward is $nT$ minus the sum of the largest gaps (since the sum of the largest gaps is at most $nT$, the reward is non-negative). The transition is deterministic, so I move from one time $t$ to the next $t+1$ after choosing an action.

My deep q learning algorithm is trained for $H$ episodes where each episode has $T$ steps to finish. I have used Adam optimizer and changed a lot the hyperparameters. Still, I did not get good results compared to the optimal offline algorithm. Even worse, I have implemented an online heuristic method that performed much better than the proposed deep q learning (though, both the deep q learning and the heuristic are still far from the optimal offline).

Should I change anything in the modelling or should I choose another deep reinforcement learning tool?

$\endgroup$
  • $\begingroup$ Your objective function appears to score a minumum of zero if no jobs are ever accepted. Are you sure it is correct, it appears to have another odd property which is that once there is a large delay, the cost of any future delay, no matter what the size, is fixed as the maximum delay so far, multiplying up the cost regardless of decisions (in fact it is better to wait longer and do less work). Also the subscript $j$ appears a lot of times but does not appear to be doing anything - AFAICS $j=t$ always? $\endgroup$ – Neil Slater Oct 20 at 7:16
  • $\begingroup$ If no job is ever accepted, then the largest gap for each job is $T$ (I may assume that jobs are accepted at $t=0$ and at $t=T+1$). Thus, the objective is $nT$. I give an example in the edit. Also, for $j$, it is used to denote that each job $j$ has its own cost and budget. We cannot have $j=t$ because for each $t$, there are $n$ jobs that arrive and we must accept one of them. $\endgroup$ – zdm Oct 20 at 9:14
  • $\begingroup$ OK, I think there is still a problem with your question description because that is not very clear. For instance in the first sentence you use "a job" singular to explain what happens, when from your comment you mean "n jobs". I'm also having a lot of trouble understanding what the subscript $j$ in $n_j$ could stand for? $\endgroup$ – Neil Slater Oct 20 at 10:33
  • $\begingroup$ Thanks. I corrected the word "a job". The $n_j$ is used to mean that each job may be scheduled in different times. For the example I gave, job $1$ has $n_1=4$ because it is scheduled at times $t_{1,1}=2$, $t_{1,2}=3$, $t_{1,3}=6$ and $t_{1,4}=10$. Job $2$ has $n_2=3$ because it is scheduled at times $t_{2,1}=4$, $t_{2,2}=8$, and $t_{2,3}=11$. Job $3$ has $n_3=2$ because it is scheduled at times $t_{3,1}=7$ and $t_{3,2}=12$. May be it is possible to use different notations. I will try to improve the notations if it is still not clear. $\endgroup$ – zdm Oct 20 at 12:01
  • $\begingroup$ Query on your example: "Thus, the gaps for job 1 are 1 (it is not accepted at time 1)" That should be 2 by my reckoning, because you assume each job was accepted at t=0, and job 1 is first accepted at t=2, and 2-0=2? $\endgroup$ – Neil Slater Oct 20 at 12:58

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.