Hardprob/Minimum Vehicle Scheduling On Tree — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
(Массовая правка: замена \ldots на …)
 
(не показаны 4 промежуточные версии этого же участника)
Строка 2: Строка 2:
 
* Дерево с выделенным корнем <m>T=\left(V,E,v_0\right)</m>,  
 
* Дерево с выделенным корнем <m>T=\left(V,E,v_0\right)</m>,  
 
** на ребрах заданы времена проезда в  
 
** на ребрах заданы времена проезда в  
*** прямом <m>f : E \rightarrow N</m>
+
*** прямом <em>f: E N</em>
*** обратно направлении <m>b: E \rightarrow N</m>
+
*** обратно направлении <em>b: E N</em>
 
** на вершинах
 
** на вершинах
*** время отгрузки-загрузки <m>r: V \rightarrow N</m>
+
*** время отгрузки-загрузки <em>r: V N</em>
*** время обработки <m>h: V \rightarrow N</m>
+
*** время обработки <em>h: V N</em>
  
 
Найти расписание автомобильного объезда, которое  
 
Найти расписание автомобильного объезда, которое  
* стартует в <m>v_0</m>,  
+
* стартует в <em>v<sub>0</sub></em>,  
 
* посещает все вершины в <m>T</m>
 
* посещает все вершины в <m>T</m>
* возвращается в <m>v_0</m>
+
* возвращается в <em>v<sub>0</sub></em>
 
* для любой вершины <m>v_{i}</m>
 
* для любой вершины <m>v_{i}</m>
 
** обработка стартует не раньше <m>r(v_i)</m>.
 
** обработка стартует не раньше <m>r(v_i)</m>.
  
Т.е. найти перестановку <m>\pi</m> вершин <m>1, \ldots, \vert V\vert</m>,  и функция ожидания <em>w</em>, такую что для любого <em>i</em>
+
Т.е. найти перестановку <m>\pi</m> вершин <m>1, , \vert V\vert</m>,  и функция ожидания <em>w</em>, такую что для любого <em>i</em>
 
<m>
 
<m>
 
  \begin{displaymath}
 
  \begin{displaymath}
d(v_0,v_{\pi(1)})+\sum_{j=1}^{i-1}[w(v_{\pi(j)})+h(v_{\pi(j)})+ d(v_{\pi(j)},v_{\pi(j+1)})] \geq r(v_{\pi(i)})
+
d(v_0,v_{\pi(1)})+\sum_{j=1}^{i-1}[w(v_{\pi(j)})+h(v_{\pi(j)})+ d(v_{\pi(j)},v_{\pi(j+1)})] ≥  r(v_{\pi(i)})
 
\end{displaymath}
 
\end{displaymath}
 
</m>
 
</m>

Текущая версия на 22:45, 17 апреля 2023

  • Дерево с выделенным корнем ,
    • на ребрах заданы времена проезда в
      • прямом f: E → N
      • обратно направлении b: E → N
    • на вершинах
      • время отгрузки-загрузки r: V → N
      • время обработки h: V → N

Найти расписание автомобильного объезда, которое

  • стартует в v0,
  • посещает все вершины в
  • возвращается в v0
  • для любой вершины
    • обработка стартует не раньше .

Т.е. найти перестановку вершин , и функция ожидания w, такую что для любого i где d(u,v) означает длину уникального пути из u в v.


Минимизировать полное время выполнения, т.е.


Задача в лаб22 (рид-онли просмотр)