Fpij1sumwu — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(не показаны 4 промежуточные версии 2 участников)
Строка 4: Строка 4:
 
Дано <tex>m</tex> станков, на которых нужно обработать <tex>n</tex> деталей. Каждую деталь нужно обработать по очереди на всех станках. Любая работа на любом станке выполняется единицу времени. Для каждой работы есть дедлайн <tex>d_i</tex> {{---}} время, до которого она должна быть закончена, и штраф <tex>w_i</tex>, который нужно будет выплатить в случае, если работа была закончена после <tex>d_i</tex>. Необходимо минимизировать суммарный штраф, который придется выплатить.
 
Дано <tex>m</tex> станков, на которых нужно обработать <tex>n</tex> деталей. Каждую деталь нужно обработать по очереди на всех станках. Любая работа на любом станке выполняется единицу времени. Для каждой работы есть дедлайн <tex>d_i</tex> {{---}} время, до которого она должна быть закончена, и штраф <tex>w_i</tex>, который нужно будет выплатить в случае, если работа была закончена после <tex>d_i</tex>. Необходимо минимизировать суммарный штраф, который придется выплатить.
 
}}
 
}}
==Эвристика NEH==
 
  
Одним из наиболее известных алгоритмов решения этой задачи является эвристика Наваза, Энскора и Хама (Nawaz, Enscore, Ham)
+
==Алгоритм==
  
Первое что нужно сделать это упорядочить требования по <tex>\sum\limits_{j = 1}^n p_{i j}</tex> и пронумеровать их в соответствии с этим порядком. Затем нужно определить порядок обслуживания двух первых требований так, чтобы минимизировать время их обслуживания. После этого использовать алгоритм
+
===Описание алгоритма===
 
 
  '''for''' <tex> i = 3</tex> '''to''' <tex>m</tex> '''do'''
 
      Поместить требование <tex>i</tex> на позицию <tex>k \in [1 , i]</tex> которое минимизирует общее время обслуживания первых <tex>i</tex> требований.
 
 
 
==Описание алгоритма==
 
  
 
{{Утверждение
 
{{Утверждение
Строка 25: Строка 19:
 
После устранения каждого разрыва получим расписание без разрывов, в котором каждая работа заканчивает выполняться не позже, чем в изначальном.
 
После устранения каждого разрыва получим расписание без разрывов, в котором каждая работа заканчивает выполняться не позже, чем в изначальном.
 
}}
 
}}
 +
 +
В [[Flow shop|flow shop]] показано как можно получить оптимальное расписание сведя задачу <tex> 1 \mid p_{ij} = 1 \mid ? </tex>  к  <tex>F \mid p_{ij} = 1 \mid ?</tex> , теперь рассмотрим как <tex>F \mid p_{ij} = 1 \mid \sum w_iu_i</tex> сводится к  <tex> 1 \mid p_{ij} = 1 \mid w_iu_i</tex>.
  
 
По этому утверждению, если работу <tex>i</tex> начали делать в <tex>t(i)</tex>, то закончена она будет в <tex>t(i) + m</tex>. Найдем время <tex>d'_i</tex> такое, что начав выполнять в него работу <tex>i</tex>, мы успеем выполнить ее до <tex>d_i</tex>: <tex>d'_i = d_i - m</tex>. Таким образом, вычтя из всех <tex>d_i</tex> число <tex>m</tex>, мы свели задачу к <tex>1 \mid p_i = 1 \mid \sum w_i U_i</tex>.  
 
По этому утверждению, если работу <tex>i</tex> начали делать в <tex>t(i)</tex>, то закончена она будет в <tex>t(i) + m</tex>. Найдем время <tex>d'_i</tex> такое, что начав выполнять в него работу <tex>i</tex>, мы успеем выполнить ее до <tex>d_i</tex>: <tex>d'_i = d_i - m</tex>. Таким образом, вычтя из всех <tex>d_i</tex> число <tex>m</tex>, мы свели задачу к <tex>1 \mid p_i = 1 \mid \sum w_i U_i</tex>.  
Строка 30: Строка 26:
 
Построив оптимальное расписание для <tex>1 \mid p_i = 1 \mid \sum w_i U_i</tex>, мы найдем времена, в которые нужно начинать выполнять работы. По утверждению выше, работы можно выполнять непрерывно.
 
Построив оптимальное расписание для <tex>1 \mid p_i = 1 \mid \sum w_i U_i</tex>, мы найдем времена, в которые нужно начинать выполнять работы. По утверждению выше, работы можно выполнять непрерывно.
  
==Сложность алгоритма==
+
===Сложность алгоритма===
Задача <tex>F \mid p_{i j} = 1 \mid \sum w_iu_i</tex> за <tex>O(n)</tex> сводится к задаче <tex>1 \mid p_i = 1 \mid \sum w_i u_i</tex>. Задача <tex>1 \mid p_i = 1 \mid \sum u_iw_i</tex> решается за <tex>O(n \log n)</tex>. После решения этой задачи, нужно вывести ответ, имеющий размер <tex>O(nm)</tex>. Значит, итоговая сложность алгоритма {{---}} <tex>O(n \log n + nm)</tex>.
+
Задача <tex>F \mid p_{i j} = 1 \mid \sum w_iu_i</tex> за <tex>O(n)</tex> сводится к [[1pi1sumwu|задаче <tex>1 \mid p_i = 1 \mid \sum w_i u_i</tex>]]. Задача <tex>1 \mid p_i = 1 \mid \sum u_iw_i</tex> решается за <tex>O(n \log n)</tex>. После решения этой задачи, нужно вывести ответ, имеющий размер <tex>O(nm)</tex>. Значит, итоговая сложность алгоритма {{---}} <tex>O(n \log n + nm)</tex>.
  
 
==См. также.==
 
==См. также.==

Версия 16:07, 9 июня 2015

[math]F \mid p_{ij} = 1 \mid \sum w_iu_i[/math]

Задача:
Дано [math]m[/math] станков, на которых нужно обработать [math]n[/math] деталей. Каждую деталь нужно обработать по очереди на всех станках. Любая работа на любом станке выполняется единицу времени. Для каждой работы есть дедлайн [math]d_i[/math] — время, до которого она должна быть закончена, и штраф [math]w_i[/math], который нужно будет выплатить в случае, если работа была закончена после [math]d_i[/math]. Необходимо минимизировать суммарный штраф, который придется выплатить.


Алгоритм

Описание алгоритма

Утверждение:
Существует оптимальное расписание, в котором каждая работа делается непрерывно.
[math]\triangleright[/math]

Рассмотрим расписание, в котором есть работы, которые делаются не непрерывно. Рассмотрим самый ранний разрыв: работа [math]i[/math] делалась в моменты [math]t(i), t(i) + 1, \ldots, t(i) + k[/math], где [math]k \lt m[/math], но не делалась в момент времени [math]t(i) + k + 1[/math]. Докажем, что в момент времени [math]t(i) + k + 1[/math], [math]k + 1[/math]-й станок простаивает и можно продолжить делать [math]i[/math]-ю работу.

Пусть в момент времени [math]t(i) + k + 1[/math] на [math]k + 1[/math]-м станке делается работа [math]j[/math]. В [math]t(i) + k[/math]-й момент времени [math]k[/math]-й станок был занят выполнением [math]i[/math]-й работы, а значит, не мог выполнять [math]j[/math]-ю. Значит, разрыв был раньше, что противоречит тому, что был выбран самый ранний разрыв. Значит, в [math]t(i) + k + 1[/math]-й момент [math]k + 1[/math]-й станок свободен и туда можно поставить [math]i[/math]-ю работу, устранив разрыв.

После устранения каждого разрыва получим расписание без разрывов, в котором каждая работа заканчивает выполняться не позже, чем в изначальном.
[math]\triangleleft[/math]

В flow shop показано как можно получить оптимальное расписание сведя задачу [math] 1 \mid p_{ij} = 1 \mid ? [/math] к [math]F \mid p_{ij} = 1 \mid ?[/math] , теперь рассмотрим как [math]F \mid p_{ij} = 1 \mid \sum w_iu_i[/math] сводится к [math] 1 \mid p_{ij} = 1 \mid w_iu_i[/math].

По этому утверждению, если работу [math]i[/math] начали делать в [math]t(i)[/math], то закончена она будет в [math]t(i) + m[/math]. Найдем время [math]d'_i[/math] такое, что начав выполнять в него работу [math]i[/math], мы успеем выполнить ее до [math]d_i[/math]: [math]d'_i = d_i - m[/math]. Таким образом, вычтя из всех [math]d_i[/math] число [math]m[/math], мы свели задачу к [math]1 \mid p_i = 1 \mid \sum w_i U_i[/math].

Построив оптимальное расписание для [math]1 \mid p_i = 1 \mid \sum w_i U_i[/math], мы найдем времена, в которые нужно начинать выполнять работы. По утверждению выше, работы можно выполнять непрерывно.

Сложность алгоритма

Задача [math]F \mid p_{i j} = 1 \mid \sum w_iu_i[/math] за [math]O(n)[/math] сводится к задаче [math]1 \mid p_i = 1 \mid \sum w_i u_i[/math]. Задача [math]1 \mid p_i = 1 \mid \sum u_iw_i[/math] решается за [math]O(n \log n)[/math]. После решения этой задачи, нужно вывести ответ, имеющий размер [math]O(nm)[/math]. Значит, итоговая сложность алгоритма — [math]O(n \log n + nm)[/math].

См. также.

Источники информации

  • Лазарев А.А., Мусатова Е.Г., Кварацхелия А.Г., Гафаров Е.Р. Пособие по теории расписаний.
  • Vladimír Modrák, R. Sudhakara Pandian. FLOW SHOP SCHEDULING ALGORITHM TO MINIMIZE COMPLETION TIME FOR -JOBS -MACHINES PROBLEM