Динамическое программирование заданий с соблюдением сроков
Во-первых, это для домашней работы. Не ищу ответов, но мне хотелось бы понять эту проблему, прежде чем я выполню свое задание.
Вот текст:
При заданных n заданиях, каждое из которых связано со временем выпуска, крайним сроком и временем обработки на компьютере M, существует ли на M необязательный выполнимый график, так что все задания соответствуют их срокам?
Для следующих трех случаев проблемы RDS определите, существует ли выполнимое расписание. Если есть выполнимое расписание, четко укажите расписание. В списках указываются атрибуты заданий по порядку.
n = 5, ProcessingTimes = {3, 4, 1, 2, 3}, ReleaseTimes = {4, 2, 7, 5, 0} и Крайние сроки = {13, 8, 13, 9, 9}.
n = 5, ProcessingTimes = {3, 4, 1, 2, 3}, ReleaseTimes = {4, 2, 7, 5, 0} и Deadlines = {13, 5, 13, 9, 9}.
- n = 5, ProcessingTimes = {3, 4, 1, 2, 5}, ReleaseTimes = {9, 2, 7, 5, 0} и Крайние сроки ={12, 8, 13, 9, 9}.
Я пытался следить за этим видео, но оно не объясняет сроки.
Итак, насколько я понимаю, ReleaseTimes - это когда начинается работа, ProcessingTimes - сколько времени это занимает, а Deadlines - когда это должно быть сделано.
Глядя на первый маркер, первая работа начинается в момент 4, длится 3 единицы и должна быть выполнена в 13 раз. Таким образом, она идет от времени: 4-7, с пустым временем от 7-13.
Второе задание начинается в 2, длится 4, заканчивается в 8. Таким образом, это 2-6 с пустым пространством между 6-8.
Теперь, основываясь на видео, он упоминает перекрытие. Таким образом, поскольку Job1 и Job2 перекрываются (4-7 и 2-6), они не могут быть запланированы. Но, поскольку в Job1 (7-13) есть свободное место, возможно, Job2 можно перенести в это время?
Я связался со своим профессором, но они заняты, и у них нет рабочих часов до тех пор, пока не наступит срок.
Я был бы очень признателен, если бы кто-то мог объяснить шаги для этой проблемы, так как я не нашел ни одного, который включает крайние сроки. Опять же, не дайте мне ответ, но помогите мне понять его.
Спасибо.