I'm trying to model a linear job scheduling optimisation problem. There is a single machine and N jobs $J_1, J_2, ..., J_N$. Each job consists of one step with processing time $p_1, p_2, ..., p_N$. Each job also has a release date $r_1, ..., r_N$. I want to minimise the average completion time (defined as $startTime_i + p_i - r_i$). I have the normal constraints, such as $startTime_i > 0$, ordering constraints ($x_{ij} + x_{ji} = 1$ where $x_{ij}$ means task order), and I have $S_j >= S_i + p_i - M (1 - x_{ij})$ for the starting times. However, I want to add a constraint so that the machine cannot be idle. If a job finishes and there is one job, I want the machine to pick that job even if it would be shorter to wait until a short job arrives. How could I add that constraint?
$\begingroup$
$\endgroup$
1
-
$\begingroup$ math.stackexchange.com/questions/4910176/… $\endgroup$– RobPrattCommented May 4 at 23:49
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
25
Introduce binary decision variables $y_{ij}$ to indicate that job $i$ immediately precedes job $j$, and impose indicator constraints $$y_{ij} = 1 \implies S_j = S_i + p_i,$$ which you can alternatively linearize via big-M constraints $$-M(1-y_{ij}) \le S_j - (S_i + p_i) \le M(1-y_{ij}).$$ To avoid the solver returning $y \equiv 0$, introduce a dummy ending job $N+1$, and impose $$\sum_{j=1}^{N+1} y_{ij} = 1$$ for $i<N+1$ (that is, for all $i$ except the dummy). You don't need variables $y_{N+1,j}$ because no job follows the dummy.
-
$\begingroup$ Thanks! How can I activate those binary variables? $\endgroup$ Commented May 3 at 13:55
-
$\begingroup$ For your edit, what happens to the last job? $$\sum_j y_{ij} = 1$$ means that all jobs must have a preceding job. $\endgroup$ Commented May 3 at 14:03
-
$\begingroup$ No, that constraint forces each job $i$ (except the dummy) to have exactly one successor job $j$. The last real job gets the dummy as its successor. $\endgroup$– RobPrattCommented May 3 at 14:14
-
$\begingroup$ I see. But if I have a finite list of jobs, not all jobs will have one successor. There will be one job that is the last job of the sequence. Also, not sure I understand what you mean by each job $i$ except the dummy. $\endgroup$ Commented May 3 at 14:17
-
1$\begingroup$ @RalphMelish, would you please, elaborate more on
I want the machine to pick that job even if it would be shorter to wait until a short job arrives.? This phrase somewhat contradicts the release date. Also, if you have a release date, it should be normal to have the idle times in an optimal solution. In your case, an active schedule. Also, why not try to use $C_{max}$ function as the objective? It is naturally designed to force the schedule to be non-delay. $\endgroup$– A.OmidiCommented May 3 at 16:28