Timeline for Single Machine Job Scheduling With Release Dates and No Idling Constraint
Current License: CC BY-SA 4.0
31 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 8 at 19:22 | comment | added | Ralph Melish | @RobPratt, thank you! And if I add a deadline to the problem, are there any algorithms? | |
| May 8 at 16:23 | comment | added | RobPratt | I'm not aware of a specialized algorithm for this, but implementing a heuristic and using the resulting schedule as a starting solution could speed up the MILP solver. | |
| May 8 at 15:25 | comment | added | Ralph Melish | Thanks! The model takes a very long time to compute. Are there any optimal scheduling policies? Like Shortest Processting Time first? Or without preemptiveness and without idleness (unless forced) there is no optimal algorithm? | |
| May 8 at 13:30 | comment | added | RobPratt | To minimize the makespan, you can just minimize the start time of the dummy ending job. | |
| May 8 at 12:46 | comment | added | Ralph Melish | @RobPratt, ok, that makes sense. I would need to rewrite the model then. The main objective would be to minimise the sum of starting times? How could I define idle time? | |
| May 8 at 12:38 | comment | added | RobPratt | If it is not possible to achieve zero idle time, you could instead minimize idle time (equivalently, minimize the makespan) as a primary objective and then minimize average completion time as a secondary objective. | |
| May 8 at 8:10 | comment | added | Ralph Melish | Hi, @RobPratt. Thank you, the model now works well. I was wondering how would you change the constraint for when no jobs are possible continuously? Meaning, idleness is forced because the next job hasn't arrived yet. | |
| May 4 at 6:43 | comment | added | A.Omidi | @RalphMelish, If in your problem you do not define any kinds of weights on the tasks or there is no preemption you allowed in the schedule, what you mentioned should be done by default. (One task is being assigned to a machine and executed until its processing time is finished). In my tiny example in the comment, while there exists one unit of idle time, this is the best/optimal schedule to minimize idle time. Unless the planner wants to enforce whose own schedule that may cause the sub-optimal solution. | |
| May 3 at 20:17 | comment | added | Ralph Melish | @A.Omidi, what I meant by the sentence you highlighted is that I want the machine to never be idle. If only a very long job is available, I want the machine to pick that job even if a really short job is arriving in 1 unit of time. I hope this helps clarify | |
| May 3 at 18:59 | comment | added | A.Omidi | Dear @RobPratt, I think defining the model only based on assigning variables like $z_{j,m}$ and sequencing variables like $x_{i,j}$ can solve the problem with an active schedule as an optimal solution. Although, I am unsure how the questioner defined the rest of the problem. | |
| May 3 at 17:57 | comment | added | RobPratt | @A.Omidi The OP enforces only $S_j\ge$ rather than $S_j=$, and the $x_{ij}$ variable indicates whether job $i$ is processed some time (not necessarily immediately) before job $j$. | |
| May 3 at 17:53 | vote | accept | Ralph Melish | ||
| May 3 at 17:52 | comment | added | Ralph Melish | Thank you, @RobPratt! It was missing one constraint, tasks can only succeed other tasks one time, $\sum_{i = 1}^{N+2} y_{ij} = 1$, for all $j$ minus the dummies where $i != j$. That fixed it. | |
| May 3 at 16:45 | comment | added | A.Omidi | Dear @RobPratt, suppose there exist two tasks that should be scheduled on one resource. The processing times as well as release dates are $\{ (5,0), (3,6) \}$ respectively. In the optimal solution, it obviously executes $task_1$ first and $task_2$ in consequence. It yields an optimal (active, but not necessarily non-delay) schedule with a total compilation time equal to $9$. I think what the questioner mentioned as $x_{i,j}$ works to ensure task $i$ is immediately being processed before task $j$. Now, I am unsure understanding your idea to define dummy tasks and the new constraint. | |
| May 3 at 16:28 | comment | added | A.Omidi |
@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.
|
|
| May 3 at 16:23 | comment | added | RobPratt | I suspect that you omitted some of the indicator constraints, which should be imposed even if $i$ is the dummy start job or $j$ is the dummy end job. | |
| May 3 at 16:04 | comment | added | Ralph Melish | I tried that, but for some reason I get overlapping jobs. I added the 2 dummies and now have $\sum_{j = 1}^{N+2} y_{ij} = 1$ and forced $S_0 = 0$ | |
| May 3 at 15:28 | comment | added | RobPratt | To force starting the project at $0$, you can introduce a dummy start job $0$, with release date $0$ and processing time $0$, and fix $S_0=0$. That way, whichever job $j$ is the immediate successor of $0$ will have $S_j=S_0+p_0=0+0$. | |
| May 3 at 14:58 | comment | added | Ralph Melish | I added your constraint to the problem and it works well at not accepting idling time. However, now instead of starting at $startTime = 0$ it starts later. Is it possible to force start time to be 0? | |
| May 3 at 14:46 | vote | accept | Ralph Melish | ||
| May 3 at 15:18 | |||||
| May 3 at 14:31 | history | edited | RobPratt | CC BY-SA 4.0 |
added 72 characters in body
|
| May 3 at 14:28 | comment | added | RobPratt | Yes, immediate release date for the dummy. A processing time of $0$ would be more natural for the dummy, but $p_{N+1}$ will not be used in any constraints. | |
| May 3 at 14:23 | comment | added | Ralph Melish | Oh, I thinks I understand now! I need to create a dummy job (any particular way?). Let's say a job with a very long processing time and immediate release date. That way it forces it. Thank you very much! | |
| May 3 at 14:22 | history | edited | RobPratt | CC BY-SA 4.0 |
added 40 characters in body
|
| May 3 at 14:19 | comment | added | RobPratt | By successor, I mean immediate successor. Think of the dummy job as $N+1$, and $\sum_{j=1}^{N+1} y_{ij}=1$ is imposed for $i\in\{1,\dots,N\}$. | |
| May 3 at 14:17 | comment | added | Ralph Melish | 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. | |
| May 3 at 14:14 | comment | added | RobPratt | 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. | |
| May 3 at 14:03 | comment | added | Ralph Melish | For your edit, what happens to the last job? $$\sum_j y_{ij} = 1$$ means that all jobs must have a preceding job. | |
| May 3 at 13:56 | history | edited | RobPratt | CC BY-SA 4.0 |
added 139 characters in body
|
| May 3 at 13:55 | comment | added | Ralph Melish | Thanks! How can I activate those binary variables? | |
| May 3 at 13:54 | history | answered | RobPratt | CC BY-SA 4.0 |