Эвристические+методы+RCPSP


Чтобы посмотреть этот PDF файл с форматированием и разметкой, скачайте его и откройте на своем компьютере.
Эвристические методы
RCPSP
База данных проектов,
PROGEN, PSPLIB,
сравнение разных правил
приоритета
Базы данных проектов

Patterson sets

J.H.
Patterson
,
A
comparison of exact approaches for solving the multiple
constrained resource project scheduling problem,
Research
Report,
Department of Industrial and Manufacturing Systems Engineering, Lehigh
University, 1984
.

110
проектов с однорежимными работами (около 51 работ в каждом
проекте)

PSPLIB
(
http
://
129.187.106.231/psplib/library.html
)

Kolisch
, R.
and
A.
Sprecher
(1996
): PSPLIB
-
A
project
scheduling
library
,
European
Journal
of
Operational
Research
,
Vol
. 96,
pp
. 205
-
216
.

Однорежимные и многорежимные работы

Генератор
ProGen
проектов с заданными характеристиками
Параметры проектов

NC (network complexity)

отношение количества связей между
работами проектов к количеству работ (включая веху старта и
финиша проекта) в диаграмме
PDM

RF (resource factor)

среднее количество ресурсов, назначенных
на одну работу

RS
k
(resource strength)

отношение разницы доступного
количества ресурса в проекте и
Kmin
к
(
Kmax
-
Kmin
).
Kmin

максимальная из всех работ потребность в
k
-
ресурсе (в режиме,
требующем минимум ресурсов).
Kmax

пиковая потребность в
k
-
ресурсе
при выполнении работ проекта в ранние сроки по СРМ.
Однорежимный случай (
SM
)
NC
1.5
1.8
2.1
----
RF
0.25
0.5
0.75
1.0
RS
0.2
0.5
0.7
1.0
Результаты исследований:

При увеличении
NC
после 1.5, сложность проблем снижается

Увеличение
RF
ведет к усложнению проблемы

Увеличение
RS
ведет к
соркащению
сложности проблемы
Множество проектов (
J30, J60, J90, J120
)
:

Количество комбинаций параметров: 3х4х4 = 48

Количество разных проектов для каждого набора параметров: 10

Всего проектов: 480
Исследование эвристических правил
(PSPLIB, J30)
N.
Quality
New Sol.
Mean
St.Dev.
Method
1
62,70%
62,70%
4,30%
5,30%
FW, Parallel, LFT+SLK
2
56,00%
14,80%
5,70%
7,30%
FW, Serial, LFT+SLK
3
59,80%
4,80%
4,40%
5,30%
FW, Parallel, LFT
4
57,50%
4,00%
5,60%
7,50%
FW, Serial, LFT
5
51,00%
2,70%
6,70%
8,80%
FW, Parallel, SLK
6
47,30%
2,30%
7,30%
9,10%
FW, Parallel, ATF
7
34,60%
1,50%
9,80%
10,00%
FW, Parallel, SPT
8
37,30%
1,50%
10,20%
11,10%
FW, Parallel, LPT
9
50,60%
3,80%
6,60%
7,90%
FW, Serial, MTS
10
39,40%
1,30%
9,60%
10,10%
FW, Serial, MIS
11
32,10%
0,80%
13,90%
13,10%
FW, Serial, RND
12
100%
0%
2,30%
3,60%
Multipath [(1)
-
(11)]
Отклонения от оптимальных решений
Rule:
Exact.
5%
10%
15%
20%
25%
30%
35%
40%
More
1
44%
20%
20%
11%
3%
1%
0%
0%
0%
0,00%
2
48%
11%
13%
14%
7%
5%
1%
1%
0%
0,00%
3
43%
21%
19%
13%
3%
2%
0%
0%
0%
0,00%
4
50%
11%
14%
12%
7%
4%
2%
1%
0%
0,00%
5
43%
15%
15%
12%
6%
4%
3%
1%
1%
0,42%
6
40%
14%
16%
13%
6%
4%
5%
2%
0%
0,42%
7
32%
12%
13%
14%
13%
7%
6%
2%
1%
0,63%
8
34%
10%
13%
14%
10%
8%
4%
2%
3%
1,67%
9
44%
11%
13%
12%
10%
6%
2%
0%
0%
0,00%
10
36%
9%
13%
13%
12%
11%
4%
2%
1%
0,42%
11
31%
5%
8%
13%
11%
13%
8%
6%
3%
3,54%
12
60%
18%
16%
5%
0%
0%
0%
0%
0%
0,00%

Приложенные файлы

  • pdf 14814180
    Размер файла: 358 kB Загрузок: 1

Добавить комментарий