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

[gaperton]

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

Comments

[gaperton]

Уважаемый коллега, я вообще в презентации говорил не об этом. Оценка трудозатрат - это всякие 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_]

Извините, что своевременно не мог ответить.
Весьма лестно было услышать от Вас обращение "коллега", это сильно сказано, поскольку я всего лишь инженер-механик и мой дилетентский интерес к вычислительым методам не более, чем хобби :)
Да, после того, как ссылки заработали, я понял, что мой вопрос - оффтоп. Тем не менее, с учетом приведенных Вами ссылок, я не совсем согласен с тем, что сводимость к NP-полной задаче эквивалентна вычислительной приводимости. Ну, например, задача восстановления или предсказания последовательности (можно двоичной), сводится к NP-полной, поскольку, теоретически, можно перебрать все множество вариантов, один из которых точно совпадет с искомой последовательностью, но узнать это можно только при условии, что она есть в нашем распоряжении. Поэтому, предсказательная сила такого решения - нулевая. Еще раз прошу прощения за то, что отнял у Вас время.