First off, this is for homework. Not looking for the answers but I would like to be comfortable with understanding this problem before I turn in my assignment.
Here's the text:
Given n jobs, each associated with a release time, a deadline, and a processing time on a machine M, is there a non-preemptive feasible schedule on M such that all jobs meet their deadlines?
For the following three instances of the RDS problem, determine whether there is a feasible schedule. If there is a feasible schedule, clearly indicate the schedule. The lists specify the atributes of jobs in order.
n=5, ProcessingTimes={3, 4, 1, 2, 3}, ReleaseTimes={4, 2, 7, 5, 0} and Deadlines={13, 8, 13, 9, 9}.
n=5, ProcessingTimes={3, 4, 1, 2, 3}, ReleaseTimes={4, 2, 7, 5, 0} and Deadlines={13, 5, 13, 9, 9}.
n=5, ProcessingTimes={3, 4, 1, 2, 5}, ReleaseTimes={9, 2, 7, 5, 0} and Deadlines={12, 8, 13, 9, 9}.
I have tried following along with this video but it doesn't explain deadlines.
So, for what I understand, ReleaseTimes is when the job starts, ProcessingTimes is how long it should take total, and Deadlines is when it should be done.
Looking at the first bullet, the first job starts at time 4, lasts for 3 units, and should be done by time 13. So, it goes from time: 4-7, with an empty time from 7-13.
The second job starts at 2, lasts for 4, ends by 8. So it is from 2-6 with an empty space between 6-8.
Now, based on the video, he mentions overlapping. So, because Job1 and Job2 overlap (4-7 and 2-6), they cannot be scheduled. But, since there is empty space in Job1 (7-13) maybe Job2 can be moved to that time?
I have contacted my professor, but they are busy and don't have office hours until after the assignment is due.
I would greatly appreciate it if someone could explain the steps for this problem, since I haven't found any that include deadlines. Again, don't give me the answer, but help me understand it.
Thank you.