Ужасы планирования

vmenshov — 19.01.2015 Иногда кошмар поджидает, когда его совсем не ждешь. Возможно, госплан по этому и загнулся. Вот, скажем, есть у вас небольшая конторка. На 7 человек. И каждого из них всего по 7 заданий. Какие-то можно делать сразу, а какие-то только после выполнения других задач коллегами. Так же задания разнятся по важности и по ожиданиям заказчиков. Как составить оптимальный план?

Кажется все просто. Переберем все возможные варианты выполнения, и выберем из них оптимальный. 7 по 7, это всего лишь 49, компьютер за доли секунды справится.



Однако жопа, как выясняется, будет куда эпичнее.

Что такое вообще 7 заданий? Сколькими способами их можно выполнить?

Если задание одно, то ясное дело одним. Если два, то двумя — сначала первое, затем второе, или наоборот. Если три,то таких комбинаций уже шесть: 1;2;3, 1;3;2, 2;1;3, 2;3;1, 3;1;2 и 3;2;1. Для семи заданий вариантов будет 7! (семь факториал, по научному), то есть 1x2x3x4x5x6x7 = 5040.

Уже не 49, но пока все равно фигня. Идем дальше. Так как задания разных сотрудников могут зависеть друг от друга, нужно для каждой комбинации одного сотрудника подобрать оптимальную комбинацию выполнения второго. И выбрать лучшую.

Если сотрудника два, то полный перебор составит 5040² комбинаций, то есть 25 401 600.
Чувствуете динамику накала страстей? 7, 49, 5040, а теперь уже 25, сука, миллионов! Но это еще далеко не конец. У нас же семь сотрудников, а не два. А это значит, что мы имеем, мама дорогая, целых 5040⁷ вариантов исполнения!

Вот это число: 82606411253903523840000000.

82,606x10²⁴.

Восемьдесят два умножить на триллион в квадрате!

Тут, возможно, человек далекий от текущей ситуации в комьютеростроении подумает что говно-вопрос, современная техника и не такое как два пальца об асфальт пощелкает, ну подождем часок если что.

Боюсь, дорогие друзья, у меня для вас плохие новости.

Допустим, на рассчет одной комбинации из 49 заданий для всех сотрудников, компьютер потратит около 1000 тактов. Примерно, по 20 тактов на задание. Тогда современный, навороченный i7, со всеми его ядрами и гигагерцами сможет посчитать 10 миллионов наших комбинаций в секунду.

То есть оптимальный план будет найден через 82,606x10¹⁷ секунд, или через 2294 триллиона часов или через 95 триллионов дней, что всего лишь через 261 миллиард лет. Что примерно в 20 раз больше возраста существования нашей вселенной.

7 человек. 7 заданий. 261 миллиард лет.

Теперь представьте себе расчет оптимального плана в масштабах хотя бы небольшого заводика.

Тлен и безысходность.

Ну и на последок, покажу как сильно нарастает время расчета плана в зависимости от сотрудников и заданий.

3 сотрудника  по 3 задания — 0,000003888 секунды.
4 сотрудника  по 4 задания — 0,010616832 секунды.
5 сотрудников по 5 заданий — 21 минута.
6 сотрудников по 6 заданий — 318 лет.
7 сотрудников по 7 заданий — 261 миллиард лет.
8 сотрудников по 8 заданий — 28331540536 триллионов лет.

Вот как-то так, котята.



PS. Хотя, в масштабах математической вселенной, это такая фигня, что даже под микроскопом не разглядишь.

Вот где обитают ПО НАСТОЯЩЕМУ МЕГАЭПИЧЕСКИЕ ВЕЛИЧИНЫ!

Оставить комментарий

Популярные посты:

• Ранее
• Архив