Участник:МетаСкептик12/Черновик: различия между версиями

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску
Содержимое удалено Содержимое добавлено
Нет описания правки
Нет описания правки
 
(не показано 20 промежуточных версий 2 участников)
Строка 1: Строка 1:
== Достижения РАН ==
{{math-stub}}
В академическом журнале академик [[Маслов, Виктор Павлович|Маслов‎]] заявил, что «если рассматривать данные в логарифмических координатах, то среднее арифметическое совпадает со средним геометрическим в обычных координатах»<ref name = "Маслов1">[http://www.mathnet.ru/links/10d347ee7eb4351192e41cbef9a30f42/mzm3081.pdf В. П. Маслов, Т. В. Маслова, «О законе Ципфа и ранговых распределениях в лингвистике и семиотике», Матем. заметки, 80:5 (2006), 718—732; Math. Notes, 80:5 (2006), 679—691]</ref> и предложил фундаментальную формулу:
'''Flow shop scheduling problem''' (планирование текущего обслуживания) это комбинаторная задача [[Теория расписаний|теории расписаний]].


<math> \frac{1}{n}\sum\limits_{i=1}^n \ln{x_i} = \sqrt[n]{\prod_{i=1}^n {x_i}}</math><ref name = "Маслов1"/>
== Определение ==
Даны <math>n</math> требований и <math>m</math> машин для их обработки. Заданы следующие ограничения:
* все требования должны пройти обработку последовательно на всех машинах с 1-ой до <math>m</math>-ой;
* любая машина в каждый момент времени может обрабатывать только одно требование.
* не допускаются прерывания при обслуживании требований и, следовательно, решение определяется некоторой перестановкой требований.


Подставляя нулевые начальные данные, имеем: <math>\pm \infty = 0 </math>, на чём я всегда и настаивал!
Задано время обслуживания каждого требования на каждой машине матрицей <math>M_{nm}(\mathbb{R}^{+})</math> . Элемент матрицы <math>p_{ij}</math> - время обслуживания требования i на машине j.


В статье «Negative Dimension in General and Asymptotic Topology» академик доказал более продвинутым читателям, что [[Островский, Александр Николаевич|А. Н. Островский]] подбирал слова для своих пьес с помощью «квантования пространств отрицательной топологической размерности».<ref>[https://arxiv.org/pdf/math/0612543.pdf "Negative Dimension in General and Asymptotic Topology". V.P.Maslov]</ref> Глубоко погружаться в статью не рекомендуется — из отрицательной размерности можно и не вернуться.
Обычно рассматривают следующие целевые функции:
* <math>C_{max}</math>, время окончания обслуживания последнего требования на <math>m</math>-ой машине или общее время обслуживания;
* <math>\Sigma^{n}_{i=1} c_i</math>, сумму времен окончания обслуживания требований на машине <math>m</math>.


== Японский стих ==
== Алгоритмы минимизацииe <math>c_{max}</math> ==
{{coquote
Далее рассматриваются алгоритмы минимизации общего времени обслуживания.
|text = ДЕМОКРАТИЯ


Ни от разума, ни от сердца, <br>
=== Алгоритм для двух машин ===
Ни для себя, ни для людей.
Для решения задачи на двух машинах найден полиномиальный по времени '''алгоритм Джонсона''<ref>S.M. Johnson, Optimal two- and three-stage production schedules with setup times included, Naval Res. Log. Quart. I(1954)61-68.</ref>.
|source =
|original-text = 民主主義<br>


意識のためじゃない、<br>
Разделим требования на два множества <math>U = \{i : p_{i1} < p_{i2}\}</math> et <math>V = \{i : p_{i1} \geq p_{i2}\}</math>
心のためじゃない、<br>
* упорядочим требования <math>U</math> по неубыванию <math>p_{i1}</math>
自分のためじゃない、<br>
* упорядочим требования <math>V</math>по невозрастанию <math>p_{i2}</math>
人間のためじゃない
* оптимальная последовательность является конкатенацией, упорядоченных таким образом <math>U</math> и <math>V</math>.
|original-source =

|original-lang = ja
Алгоритм имеет временную сложность <math>n \log(n)</math>, поскольку использует алгоритм сортировки.
|bq = 1

}}
=== Алгоритмы для трёх и более машин ===
В случае более двух машин эта задача является [[Класс NP|NP-трудной]]. Но существуют достаточно хорошие эвристические полиномиальные по времени приближённые алгоритмы.

==== Эвристика Наваз-Энскор-Хам (Nawaz-Enscore-Ham) (NEH) ====
* Упорядочиваем требования по <math> \sum_{j=1}^{m} p_{ij} </math> и нумеруем в соответствии с этим порядком.
* Определяем порядок обслуживания двух первых требований так, чтобы минимизировать время их обслуживания.
* Для i = 3 до n Делаем
** Помещаем требование <math>i</math> на позицию <math>k \in [1,i]</math>, которая минимизирует общее время обслуживания первых <math> i </math>требований
* Конец Для

==== Эвристика Кэмпбелла Дудека и Смита ====
Задачу для <math>m</math> машин последовательно сводим к <math>m-1</math> задаче для 2 машин.


'''ДАТЫ ВОЗНИКНОВЕНИЯ И АВТОРЫ НЕКОТОРЫХ МАТЕМАТИЧЕСКИХ ЗНАКОВ'''
{|class="standard" style="text-align:right"
!colspan="4"|Знаки индивидуальных объектов
|-
|align=left|'''Знак'''||'''Значение'''||'''Кто ввёл'''||'''Когда введён'''
|-
|align=left|<math>\infty</math>||[[бесконечность]]|| [[Валлис, Джон|Джон Валлис]] ||1653
|-
|align=left|<math>e</math>|| [[основание натуральных логарифмов]]|| [[Леонард Эйлер]]||1736
|-
|align=left|<math>\pi</math> ||[[Пи (число)|отношение длины окружности к диаметру]]|| [[Джонс, Уильям (математик)|Уильям Джонс]]<!-- Л. Эйлер 1736-->||1706
|-
|align=left|<math>i</math> ||[[Мнимая единица|корень квадратный из —1]]|| Леонард Эйлер ||1777 (в печати 1794)
|-
|align=left|<math>i,j,k</math> ||[[единичный вектор|единичные векторы]]||[[Уильям Гамильтон]]||1853
|-
|align=left|<math>[x]</math> || [[целая часть числа]]||[[Гаусс, Карл Фридрих|Карл Фридрих Гаусс]]||1808
|-
|align=left|<math>\Pi(a)</math> ||[[угол параллельности]]||[[Николай Иванович Лобачевский]]||1835
|-
!colspan="4"|Знаки переменных объектов
|-
|align=left|<math>x, y, z</math> || [[Переменная величина|неизвестные или переменные величины]]||[[Рене Декарт]]||1637
|-
|align=left|<math>\vec{r}</math> || [[вектор (математика)|вектор]]||[[Огюстен Луи Коши]]||1853
|-
!colspan="4"|Знаки индивидуальных операций
|-
|align=left|<math>+</math> и <math>-</math> ||[[сложение]] и [[вычитание]]|| [[Иоганн Видман]] ||1489
|-
|align=left|<math> \times </math> ||[[умножение]]|| [[Отред, Уильям|Уильям Отред]] ||1631
|-
|align=left|<math> \cdot </math> ||умножение||[[Готфрид Вильгельм Лейбниц]]||1698
|-
|align=left|<math>:</math> ||[[Деление (математика)|деление]]||Готфрид Вильгельм Лейбниц||1684
|-
|align=left|<math>a^n</math> ||[[Возведение в степень|степень]]||Реде Декарт<!-- И. Ньютон 1676-->||1637
|-
|align=left|<math> \sqrt[n]{a}</math> ||[[Корень (математика)|корень]]||[[Кристоф Рудольф]]<!-- И. Кеплер 1624--> ||1525
|-
|align=left|<math> log </math> ||[[логарифм]]||[[Иоганн Кеплер]]<!-- [[ Бонавентура Кавальери]]
1632-->||1624
|-
|align=left|<math> ln </math> ||[[натуральный логарифм]]||[[Альфред Прингсхайм]] ||1893
|-
|align=left|<math> sin </math> и <math> cos </math>||[[синус]] и [[косинус]]||Уильям Оутред, [[Жирар, Альбер]]?||?
|-
|}
[[У:МетаСкептик12|МетаСкептик12]]
== Примечания ==
== Примечания ==
{{Примечания}}
<references/>

<!--
=== Liens externes===
* [[À remplacer]]

=== Bibliographie ===
* À remplacer

[[Catégorie:Recherche opérationnelle|Ordonnancement]]
-->


[[Категория:Алгоритмы]]
[[Категория:Решение задач]]

Текущая версия от 15:41, 4 июля 2018

Достижения РАН

[править | править код]

В академическом журнале академик Маслов‎ заявил, что «если рассматривать данные в логарифмических координатах, то среднее арифметическое совпадает со средним геометрическим в обычных координатах»[1] и предложил фундаментальную формулу:

[1]

Подставляя нулевые начальные данные, имеем: , на чём я всегда и настаивал!

В статье «Negative Dimension in General and Asymptotic Topology» академик доказал более продвинутым читателям, что А. Н. Островский подбирал слова для своих пьес с помощью «квантования пространств отрицательной топологической размерности».[2] Глубоко погружаться в статью не рекомендуется — из отрицательной размерности можно и не вернуться.

Японский стих

[править | править код]
ДЕМОКРАТИЯ

Ни от разума, ни от сердца,

Ни для себя, ни для людей.

ДАТЫ ВОЗНИКНОВЕНИЯ И АВТОРЫ НЕКОТОРЫХ МАТЕМАТИЧЕСКИХ ЗНАКОВ

Знаки индивидуальных объектов
Знак Значение Кто ввёл Когда введён
бесконечность Джон Валлис 1653
основание натуральных логарифмов Леонард Эйлер 1736
отношение длины окружности к диаметру Уильям Джонс 1706
корень квадратный из —1 Леонард Эйлер 1777 (в печати 1794)
единичные векторы Уильям Гамильтон 1853
целая часть числа Карл Фридрих Гаусс 1808
угол параллельности Николай Иванович Лобачевский 1835
Знаки переменных объектов
неизвестные или переменные величины Рене Декарт 1637
вектор Огюстен Луи Коши 1853
Знаки индивидуальных операций
и сложение и вычитание Иоганн Видман 1489
умножение Уильям Отред 1631
умножение Готфрид Вильгельм Лейбниц 1698
деление Готфрид Вильгельм Лейбниц 1684
степень Реде Декарт 1637
корень Кристоф Рудольф 1525
логарифм Иоганн Кеплер 1624
натуральный логарифм Альфред Прингсхайм 1893
и синус и косинус Уильям Оутред, Жирар, Альбер? ?

МетаСкептик12

Примечания

[править | править код]