Участник:МетаСкептик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] и предложил фундаментальную формулу:
Подставляя нулевые начальные данные, имеем: , на чём я всегда и настаивал!
В статье «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 | |
и | синус и косинус | Уильям Оутред, Жирар, Альбер? | ? |