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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 9 промежуточных версий 3 участников)
Строка 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>. Необходимо минимизировать суммарный штраф, который придется выплатить.
 
}}
 
}}
==Описание алгоритма==
+
 
 +
==Алгоритм==
 +
 
 +
===Описание алгоритма===
  
 
{{Утверждение
 
{{Утверждение
 
|statement=Существует оптимальное расписание, в котором каждая работа делается непрерывно.
 
|statement=Существует оптимальное расписание, в котором каждая работа делается непрерывно.
 
|proof=
 
|proof=
Рассмотрим расписание, в котором есть работы, которые делаются не непрерывно. Рассмотрим самый ранний разрыв: работа <tex>i</tex> делалась в моменты <tex>t(i), t(i)+1, \ldots, t(i)+k</tex>, где <tex>k<m</tex>, но не делалась в момент времени <tex>t(i)+k+1</tex>. Докажем, что в момент времени <tex>t(i)+k+1</tex>, <tex>k+1</tex>-й станок простаивает и можно продолжить делать <tex>i</tex>-ю работу.  
+
Рассмотрим расписание, в котором есть работы, которые делаются не непрерывно. Рассмотрим самый ранний разрыв: работа <tex>i</tex> делалась в моменты <tex>t(i), t(i) + 1, \ldots, t(i) + k</tex>, где <tex>k < m</tex>, но не делалась в момент времени <tex>t(i) + k + 1</tex>. Докажем, что в момент времени <tex>t(i) + k + 1</tex>, <tex>k + 1</tex>-й станок простаивает и можно продолжить делать <tex>i</tex>-ю работу.  
  
Пусть в момент времени <tex>t(i)+k+1</tex> на <tex>k+1</tex>-м станке делается работа <tex>j</tex>.  
+
Пусть в момент времени <tex>t(i) + k + 1</tex> на <tex>k + 1</tex>-м станке делается работа <tex>j</tex>.  
В <tex>t(i)+k</tex>-й момент времени <tex>k</tex>-й станок был занят выполнением <tex>i</tex>-й работы, а значит, не мог выполнять <tex>j</tex>-ю. Значит, разрыв был раньше, что противоречит тому, что был выбран самый ранний разрыв. Значит, в <tex>t(i)+k+1</tex>-й момент <tex>k+1</tex>-й станок свободен и туда можно поставить <tex>i</tex>-ю работу, устранив разрыв.  
+
В <tex>t(i) + k</tex>-й момент времени <tex>k</tex>-й станок был занят выполнением <tex>i</tex>-й работы, а значит, не мог выполнять <tex>j</tex>-ю. Значит, разрыв был раньше, что противоречит тому, что был выбран самый ранний разрыв. Значит, в <tex>t(i) + k + 1</tex>-й момент <tex>k + 1</tex>-й станок свободен и туда можно поставить <tex>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>.  
+
В [[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>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_{ij} = 1 \mid \sum w_iu_i</tex> за <tex>O(n)</tex> сводится к задаче <tex>1 \mid p_i = 1 \mid \sum w_iu_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>.
 +
 
 +
==См. также.==
 +
* [[Классификация задач]]
 +
* [[Flow shop]]
 +
 
 +
==Источники информации==
 +
* Лазарев А.А., Мусатова Е.Г., Кварацхелия А.Г., Гафаров Е.Р. Пособие по теории расписаний.
 +
* Vladimír Modrák, R. Sudhakara Pandian. FLOW SHOP SCHEDULING ALGORITHM TO MINIMIZE COMPLETION TIME FOR -JOBS -MACHINES PROBLEM
 +
 
 +
[[Категория: Дискретная математика и алгоритмы]]
 +
[[Категория: Теория расписаний]]

Текущая версия на 19:29, 4 сентября 2022

[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