# Single Machine Job Scheduling With Release Dates and No Idling Constraint

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?

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 (that is, for all $$i$$ except the dummy). You don't need variables $$y_{N+1,j}$$ because no job follows the dummy.
• For your edit, what happens to the last job? $$\sum_j y_{ij} = 1$$ means that all jobs must have a preceding job. Commented May 3 at 14:03
• 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. Commented May 3 at 14:14
• 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. Commented May 3 at 14:17
• @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. Commented May 3 at 16:28