Планирование работы с проблемой узкого места

11

Учитывая заданий , для выполнения каждого задания требуется раз.J 1 , J 2 , . , , , J п Г я > 0 , Т яNnJ1,J2,...,JnTi>0,TiN

Каждое задание должно быть предварительно обработано и постобработано одной машиной M, которая может обрабатывать только 1 задание за раз, и обе фазы требуют 1 единицу времени. После предварительной обработки задание отправляется на машину с неограниченной мощностью (которая может параллельно обрабатывать неограниченное количество заданий), и оно будет готово в момент времени , затем оно должно быть отправлено ( немедленно ) на машину M снова для Постобработка.T яJiTi

введите описание изображения здесь

Связанное решение проблемы является:

Входной данные : Время обработки из рабочих мест, целое число Вопрос: можем ли мы обработать все рабочие места во время , используя вышеупомянутую модель «узкого места»? N K 2 N KTi>0,TiNNK2N
K

У этой проблемы есть имя?
В чем его сложность? (он в или его -полным?) Н ПPNP

ОБНОВЛЕНИЕ 29 марта:
как правильно заметил М. Кафаро в своем ответе, проблема аналогична проблеме неограниченного минимального времени окончания (UMFT) (см. Главу 17 Руководства по алгоритмам планирования ), которая является -твердой (доказано). в W. Kern и W. Nawijn, "Планирование многозадачных заданий с задержками на одной машине", Университет Твенте, 1993). Как я вижу, есть некоторые различия, потому что в моей модели:NP

  • время до / после обработки постоянно (1 единица времени)
  • как только задание завершено, оно должно быть немедленно обработано (модель UMFT допускает задержки)

Я не нашел в Интернете доказательств Kern & Nawijn, поэтому я до сих пор не знаю, могут ли вышеуказанные ограничения изменить сложность проблемы.

Наконец, вы можете представить весь процесс как робот- одиночка с большой духовкой; робот может готовить разные типы продуктов по одному (все требуют одинакового времени приготовления), помещать их в духовку, и как только они приготовятся, он должен вынуть их из духовки и добавить холодные ингредиенты ... « проблема готовить робота » :-)

Вор
источник
Ницца. У меня есть ощущение, что узкое место должно упростить вещи.
Рафаэль
Ограничение всегда проверяется, поскольку затраты до и после обработки составляют 1 единицу времени, и у вас есть заданий. Вы уверены, что ограничение верно? nk2nn
Массимо Кафаро
Извините, я не понял, что имел в виду в предыдущем комментарии. Является явно задан на входе , как «крайний срок» или вы задаете для алгоритма , чтобы минимизировать ? кkk
Массимо Кафаро
@MassimoCafaro: задается в качестве входных данных (чтобы проблема оптимизации была решена). Как вы заметили, я написал потому что если ответ тривиально НЕТ. Но, возможно, это сбивает с толку, и я должен удалить его. k 2 n k < 2 nkk2nk<2n
Vor
1
W. Yu, H. Hoogeveen и JK Lenstra (2004) также подтвердили, что ваш вопрос доказан как NP-полный в статье «Минимизация времени простоя в поточном цехе с двумя машинами с задержками и операциями в единичное время». Керн и Навейн не решили это. Я цитирую: «Статус сложности особого случая с задачами на единицу времени обработки был открыт как для минимальных, так и для точных задержек. Статус сложности для случая с минимальными задержками представлен Керном и Навейном (1991) как открытый вопрос».
Питер Шор

Ответы:

5

W. Yu, H. Hoogeveen и JK Lenstra (2004) доказали, что этот вопрос доказан NP-hard в статье «Минимизация времени простоя в поточном цехе с двумя машинами с задержками и операциями в единичное время - NP-Hard» . Это доказано в разделе 9 статьи:

Теорема 24. Задача минимизации рабочего времени на одной машине с двумя операциями в единицу времени на задание с произвольными промежуточными задержками сильно NP-трудна.

Точная модель, изучаемая здесь, состоит в том, что задание состоит из двух операций, которые занимают единицу времени, разделенную некоторым временем задержки . Проблема является строго NP-полной, как в том случае, когда точное значение задержки указано для каждого задания, так и в тех случаях, когда для каждого задания указано некоторое минимальное время задержки.T я T яiTiTi

Питер Шор
источник
5

Это похоже на так называемую модель планирования «главный-подчиненный», представленную Сахни . В частности, ваша проблема относится к системам с одним главным мастером и подчиненным. Вы можете выделить несколько случаев:

1) Если вы не добавляете каких-либо дополнительных ограничений на порядок выполнения задания (как в вашем случае), проблема называется проблемой безусловного минимального времени окончания (UMFT) и, как было показано, является NP-трудной;

2) Одинаковые заказы до и после обработки: возможно разработать алгоритм для построения расписания с сохранением порядка с минимальным временем окончания (OPMFT);O(nlogn)

Следовательно, в случае 1 ваша проблема - трудная, а в случае 2 - вПNPP

Дополнительные связанные проблемы:

3) Постобработка в обратном порядке: для любой заданной перестановки предварительной обработки, , можно построить график обратного порядка, называемый каноническим графиком обратного порядка (CROS). При заданной перестановке перестановок соответствующий CROS является уникальным. Легко установить, что каждый минимальный график обратного заказа на конечное время (ROMFT) является CROS.σσσ

4) ограничение отсутствия ожидания в процессе:

a) [MFTNW] Минимизировать время окончания с учетом ограничения на отсутствие ожидания в процессе; b) [OP-MFTNW] Это версия MFTNW, сохраняющая порядок. Таким образом, минимизируйте время окончания с учетом ограничений, связанных с отсутствием ожидания в процессе и сохранением заказа; c) [RO-MFTNW] Минимизировать время окончания с учетом ограничений по времени ожидания и обратного порядка.

Задачи и являются NP-сложными, а допускает решение за полиномиальное время.б вabc

Дополнительные подробности в Руководстве по планированию , глава 17.

Массимо Кафаро
источник
Спасибо, это похоже (у меня нет книги, но я нашел эту статью ). Я прочитаю это внимательно позже. Просто вопрос после прочтения его введения, кажется, что он использует рабов (после предварительной обработки), но в моей модели есть неограниченное количество рабов; это правильно? Я прочитаю доказательство NP-твердости UMFT и посмотрю, использует ли он гипотезу, что число рабов ограничено. n
Vor
Сахни показал, что вы всегда можете использовать ровно ведомых: «Доступные процессоры делятся на две категории: ведущие и ведомые. Если обозначает количество заданий, то никакое расписание не может использовать более ведомых. Следовательно, мы можем предположить, что точно рабы. Таким образом, ваша проблема легко переводится на этот параметр: вы просто отбрасываете и не используете дополнительных рабов, имеющихся в машине с неограниченным количеством рабов. н н н нnnnn
Массимо Кафаро
2
Мне кажется, что доказательство твердости NP Сахни критически использует тот факт, что время предварительной обработки и время последующей обработки могут быть произвольными. У задачи ОП все эти времена равны 1. Работает ли доказательство в этом случае?
Питер Шор
Vor, документ, на который вы ссылаетесь, является просто выдержкой со многими недостающими частями из главы 17 книги. Тем не менее, недостающая часть помешает вам правильно понять (отсутствует обозначение и т.д.).
Massimo Cafaro
Питер, я не уверен , и мне нужно , чтобы проверить доказательства; если он просто требует времени предварительной обработки> 0, он должен включать проблему OP при рассмотрении проблемы минимального времени окончания без ограничений. По той же причине, это должно привести к вместо полиномиальный алгоритм времени для того , сохраняющей проблему минимального времени закончить. O(nlogn)
Massimo Cafaro