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?


1 Answer 1


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$
    – RobPratt
    Commented 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.Omidi
    Commented May 3 at 16:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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