Редактирование: O2Cmax

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 11: Строка 11:
 
#Найдем такие <tex> x </tex> и <tex> y </tex>, что <tex>a_{x} = \max \limits_{i \in I} \{a_{i}\}</tex> и <tex>b_{y} = \max \limits_{i \in J} \{b_{i}\}</tex>.
 
#Найдем такие <tex> x </tex> и <tex> y </tex>, что <tex>a_{x} = \max \limits_{i \in I} \{a_{i}\}</tex> и <tex>b_{y} = \max \limits_{i \in J} \{b_{i}\}</tex>.
 
#Построим оптимальное значение целевой функции: <tex>C_{max} = \max \{\sum \limits_{i = 1}^{n} a_i, \ \sum \limits_{i = 1}^{n} b_i,\ \max \limits_{i = 1}^{n}\{a_i + b_{i}\}\}</tex>.
 
#Построим оптимальное значение целевой функции: <tex>C_{max} = \max \{\sum \limits_{i = 1}^{n} a_i, \ \sum \limits_{i = 1}^{n} b_i,\ \max \limits_{i = 1}^{n}\{a_i + b_{i}\}\}</tex>.
# Рассмотрим два случая:
+
# Рассмотрим два случая. Первый случай, когда <tex>a_{x} > b_{y}</tex> (он показан на рисунке ниже). Будем строить расписание с двух концов:
## <tex>a_{x} > b_{y}</tex>. Будем строить расписание с двух концов:
+
#*Строим расписание слева: выполняем на первом станке все работы из <tex>I \setminus \{x\}</tex>, а на втором выполняем первой работу <tex>x</tex>, затем <tex>I \setminus \{x\}</tex>.
##*Строим расписание слева: выполняем на первом станке все работы из <tex>I \setminus \{x\}</tex>, а на втором выполняем первой работу <tex>x</tex>, затем <tex>I \setminus \{x\}</tex> в том же порядке, что и на первом станке.
+
#*Теперь, упираясь в правую границу, равную <tex> C_{max} </tex>, можно построить расписание справа: выполняем на первом станке все работы из <tex>J</tex>, затем <tex>x</tex>, а для второго выполняем работы из <tex>J</tex>.
##*Теперь, упираясь в правую границу, равную <tex> C_{max} </tex>, можно построить расписание справа: выполняем на первом станке все работы из <tex>J</tex>, затем <tex>x</tex>, а для второго выполняем работы из <tex>J</tex>.[[Файл:Picture2.gif‎|500px|center]]
+
:Второй случай сводится к первому: все работы и станки меняются местами, и решается задача для первого случая.
## <tex>a_{x} \leqslant b_{y}</tex>. Сводится к первому, если поменять местами станки и соответствующие списки времён выполнения, при этом надо заново выполнить пункты 1,2 и 3. При выдаче ответа меняем станки обратно местами.
+
 
 +
[[Файл:Picture2.gif‎|500px|center]]
  
 
==Доказательство корректности алгоритма==
 
==Доказательство корректности алгоритма==
Строка 24: Строка 25:
 
Чтобы доказать корректность, надо доказать, что на каждом станке в любой момент времени выполняется не более одной работы, и что каждая работа в каждый момент времени выполняется не более, чем на одном станке.<br/>
 
Чтобы доказать корректность, надо доказать, что на каждом станке в любой момент времени выполняется не более одной работы, и что каждая работа в каждый момент времени выполняется не более, чем на одном станке.<br/>
 
Первое утверждение вытекает из того, что мы строили расписание, опираясь на <tex>C_{max}</tex>. Из построения <tex>C_{max} \geqslant \sum \limits_{i = 1}^{n}a_{i}, \sum \limits_{i = 1}^{n}b_{i}</tex>, следовательно на каждом станке в любой момент времени выполняется не более одной работы.<br/>
 
Первое утверждение вытекает из того, что мы строили расписание, опираясь на <tex>C_{max}</tex>. Из построения <tex>C_{max} \geqslant \sum \limits_{i = 1}^{n}a_{i}, \sum \limits_{i = 1}^{n}b_{i}</tex>, следовательно на каждом станке в любой момент времени выполняется не более одной работы.<br/>
Докажем теперь второе утверждение. У нас имеется три блока работ: <tex> I \setminus \{x\}, \{x\}, J</tex>.
+
Докажем теперь второе утверждение. У нас имеется 3 блока работ: <tex> I \setminus \{x\}, \{x\}, J</tex>.
 
# Для блока <tex> \{x\}</tex> это следует из того, что <tex> C_{max} \geqslant a_{x}+b_{x}</tex>, а работа <tex> x </tex> выполняется с разных концов станков. Получили, что отрезки выполнения работы <tex> x </tex> на разных станках не пересекаются.
 
# Для блока <tex> \{x\}</tex> это следует из того, что <tex> C_{max} \geqslant a_{x}+b_{x}</tex>, а работа <tex> x </tex> выполняется с разных концов станков. Получили, что отрезки выполнения работы <tex> x </tex> на разных станках не пересекаются.
 
# Покажем, что любая работа из <tex> I \setminus \{x\}</tex> начинает выполняться на втором станке позже, чем заканчивает выполняться на первом. Для этого рассмотрим сумму:<br><tex>\sum \limits_{i = 1}^k a_{i} \leqslant \sum \limits_{i = 1}^k b_{i} = \sum \limits_{i = 1}^{k - 1} b_{i} + b_{x}</tex>, где <tex>1 \dots k</tex> {{---}} это работы, выполняемые на первом станке во время данного блока.<br>Это неравенство следует из выбора <tex>I</tex> и из того, что <tex>b_{x} \geqslant a_{x} \geqslant a_{i}, \forall i \in I</tex>.<br>Получили, что каждая работа из этого блока начинает выполняться на втором станке позже, чем она заканчивается на первом.<br>
 
# Покажем, что любая работа из <tex> I \setminus \{x\}</tex> начинает выполняться на втором станке позже, чем заканчивает выполняться на первом. Для этого рассмотрим сумму:<br><tex>\sum \limits_{i = 1}^k a_{i} \leqslant \sum \limits_{i = 1}^k b_{i} = \sum \limits_{i = 1}^{k - 1} b_{i} + b_{x}</tex>, где <tex>1 \dots k</tex> {{---}} это работы, выполняемые на первом станке во время данного блока.<br>Это неравенство следует из выбора <tex>I</tex> и из того, что <tex>b_{x} \geqslant a_{x} \geqslant a_{i}, \forall i \in I</tex>.<br>Получили, что каждая работа из этого блока начинает выполняться на втором станке позже, чем она заканчивается на первом.<br>
Строка 36: Строка 37:
  
 
==Псевдокод==
 
==Псевдокод==
<font color=green>//Функция принимает список из времён выполнения на первом станке a и времён выполнения на втором станке b.<br>//Функция возвращает пару из расписания для первого станка и расписания для второго станка.</font>
+
  <tex>I = \varnothing </tex>
'''function''' scheduling(a: '''int'''[n], b: '''int[n]'''): '''pair<int[n], int[n]>'''
+
  <tex>J = \varnothing </tex>
    <tex>I = \varnothing </tex>
+
  <tex>C_{max} = \max \{\sum \limits_{i = 1}^{n} a_i, \  \sum \limits_{i = 1}^{n} b_i, \  \max \limits_{i = 1}^{n}\{a_i + b_{i}\}\}</tex>
    <tex>J = \varnothing </tex>
+
  '''for''' <tex>i = 1</tex> '''to''' <tex>n</tex>
    <tex>C_{max} = \max \{\sum \limits_{i = 1}^{n} a_i, \  \sum \limits_{i = 1}^{n} b_i, \  \max \limits_{i = 1}^{n}\{a_i + b_{i}\}\}</tex>
+
      '''if''' <tex>a_{i} \leqslant b_{i}</tex>
    '''for''' <tex>i = 1</tex> '''to''' <tex>n</tex>
+
        <tex> I = I \cup \{i\} </tex>
        '''if''' <tex>a_{i} \leqslant b_{i}</tex>
+
      '''else'''
          <tex> I = I \cup \{i\} </tex>
+
        <tex> J = J \cup \{i\} </tex>
        '''else'''
+
  Найти <tex>x</tex>, где <tex>a_{x} = \max \limits_{i \in I} \{a_{i}\}</tex>
          <tex> J = J \cup \{i\} </tex>
+
  Найти <tex>y</tex>, где <tex>b_{y} = \max \limits_{i \in J} \{b_{i}\}</tex>
    Найти <tex>x</tex>, где <tex>a_{x} = \max \limits_{i \in I} \{a_{i}\}</tex>
+
  '''if''' <tex>a_{x} < b_{y}</tex>
    Найти <tex>y</tex>, где <tex>b_{y} = \max \limits_{i \in J} \{b_{i}\}</tex>
+
      Поменять местами первый и второй станок
    '''if''' <tex>a_{x} > b_{y}</tex>
+
      Пересчитать <tex>I, J, x</tex>
        Начиная с <tex>0</tex> на первом станке расставляем расписание для <tex>I \setminus \{x\}</tex>
+
      Запомнить, что поменяли
        Начиная с <tex>0</tex> на втором станке расставляем расписание для <tex>\{x\}</tex>, затем для <tex>I \setminus \{x\}</tex><br/>
+
 
        От правой границы {{---}} <tex>C_{max}</tex> на первом станке расставляем расписание для <tex>\{x\}</tex>, затем для <tex>J</tex>
+
  Начиная с <tex>0</tex> на первом станке расставляем расписание для <tex>I \setminus \{x\}</tex>
        От правой границы {{---}} <tex>C_{max}</tex> на втором станке расставляем расписание для <tex>J</tex><br/>
+
  Начиная с <tex>0</tex> на втором станке расставляем расписание для <tex>\{x\}</tex>, затем для <tex>I \setminus \{x\}</tex><br/>
        '''pair<int[n], int[n]>''' ans = пара из расписания для первого станка и расписания для второго станка
+
  От правой границы {{---}} <tex>C_{max}</tex> на первом станке расставляем расписание для <tex>\{x\}</tex>, затем для <tex>J</tex>
        '''return''' ans
+
  От правой границы {{---}} <tex>C_{max}</tex> на втором станке расставляем расписание для <tex>J</tex><br/>
    '''else'''
+
  '''if''' станки меняли местами
        '''pair<int[n], int[n]>''' ans = scheduling(b, a)
+
      поменять их обратно
        Меняем местами расписания для станков в ans
 
        '''return''' ans
 
  
 
==Сложность алгоритма==
 
==Сложность алгоритма==
Строка 72: Строка 71:
  
 
== Источники информации ==
 
== Источники информации ==
* Peter Brucker «Scheduling Algorithms», fifth edition, Springer {{---}} с. 158{{---}}160 ISBN 978-3-540-69515-8
+
* Peter Brucker «Scheduling Algorithms», fifth edition, Springer {{---}} с. 158-160 ISBN 978-3-540-69515-8
  
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Теория расписаний]]
 
[[Категория: Теория расписаний]]

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблоны, используемые на этой странице: