?

Log in

No account? Create an account
November 2016   01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
инженер

Презентация про планирование

Posted on 2008.05.25 at 02:52

Comments:


Gaperton
gaperton at 2008-05-26 10:51 (UTC) (Link)
1) бюджет зависит от трудозатрат. В контексте заказной разработки бюджет определяется трудозатратами. Доклад называется "оценка трудозатрат".

2) "Задачка планирования вычислительно неприводимая" - чрезвычайно интересно. Вы, вероятно, хотели сказать, что задача выработки оптимального расписания NP-полная. Что совершенно не мешает программам планирования вырабатывать квазиоптимальные расписания пользуясь эвристиками. Но это хоть и чрезвычайно интересно, но не имеет абсолютно никакого отношения к задаче оценки трудозатрат и к моему докладу в частности.

3) Ссылки на мою презентацию на момент вашего поста были битые, и поэтому я теряюсь в догадках, что вы не видя моей презентации хотели своим постом сказать и с какой целью вообще его написали. To make the things clear: за флейм, оффтопик, неконструктивные высказывания, глупость, хамство, наглость, переливание из пустого в порожнее и замеры пиписьками я очень быстро баню. Даже если мне покажется, что вы этим занимаетесь.
sharper_
sharper_ at 2008-05-26 15:55 (UTC) (Link)
"Ссылки на мою презентацию на момент вашего поста были битые, и поэтому я теряюсь в догадках, что вы не видя моей презентации хотели своим постом сказать и с какой целью вообще его написали"
Так я понял, что ссылки битые и, поскольку мне этот вопрос действительно интересен, то я высказал свои мысли по поводу, извините, если что не так. Что касается вычислительной неприводимости, то это не совсем одно и тоже, чем NP-полная задача, которую решить все же можно, но за обессмысливающий полезность результата, промежуток времени. Может быть я и ошибаюсь, но такие (в общем эволюционные) задачи не решаются вообще, а только моделируются, причем ценность такой модели нулевая.
Gaperton
gaperton at 2008-05-26 18:05 (UTC) (Link)
Уважаемый коллега, я вообще в презентации говорил не об этом. Оценка трудозатрат - это всякие COCOMO II и разного рода estimations, а вы говорите о production scheduling, это совсем разные темы. Я никак не касаюсь оптимальных расписаний в презентации, и не хочу. Однако - может быть вам это покажется интересным следующее.

The assignment of scarce production resources to competing activities over time, in order to optimise certain performance criteria is what is known as production scheduling. Job-shop scheduling is a complicated and widely studied production scheduling problem. In a job-shop, jobs must be processed on machines in a specified order.

Оно?

Job-shop scheduling is one of the more difficult combinatorial optimisation problems.
Randomly generated travelling salesman problems with 300–400 cities (more than
100,000 variables) can be solved to optimality. However, a job-shop with ten jobs and
ten machines cannot usually be scheduled optimally (Adams et al., 1988).

Все плохо, не так ли? Однако при этом

When there are only one or two machines types with one machine of each machine
type, the makespan can be minimised using Johnson’s algorithm (Johnson, 1954).
However, when there are more than two machines, the problem becomes strongly
NP-hard.


Вот так. Таки NP-полная. Переборно решается - значит NP-полная. Это выдержка из статьи, посвященной эвристике "shifting bottleneck heuristic".
http://www.inderscience.com/storage/f115104122398176.pdf

Вообще, этих эвристик много. Есть очень тупые эвристики. А есть раздел математики "теория расписаний" - по нему можно поискать и найти учебники. Например:

http://eup.ru/Documents/2004-03-22/29032.asp

Но, еще раз, это не то в чем я специалист и чего хотел бы касаться. В планировании разработки ПО данные методы на мой взгляд не особо актуальны. Гораздо важнее, например, решение простой проблемы - как надежно предсказывать сроки и бюджеты при контрактах fixed cost в условиях неопределенности. Простые и надежные техники, которые можно применять не будучи доктором наук. О чем я и делал доклад, собственно.
sharper_
sharper_ at 2008-05-31 04:02 (UTC) (Link)
Извините, что своевременно не мог ответить.
Весьма лестно было услышать от Вас обращение "коллега", это сильно сказано, поскольку я всего лишь инженер-механик и мой дилетентский интерес к вычислительым методам не более, чем хобби :)
Да, после того, как ссылки заработали, я понял, что мой вопрос - оффтоп. Тем не менее, с учетом приведенных Вами ссылок, я не совсем согласен с тем, что сводимость к NP-полной задаче эквивалентна вычислительной приводимости. Ну, например, задача восстановления или предсказания последовательности (можно двоичной), сводится к NP-полной, поскольку, теоретически, можно перебрать все множество вариантов, один из которых точно совпадет с искомой последовательностью, но узнать это можно только при условии, что она есть в нашем распоряжении. Поэтому, предсказательная сила такого решения - нулевая. Еще раз прошу прощения за то, что отнял у Вас время.
Previous Entry  Next Entry