Problém řízení projektu s omezeními zdrojů

Problém řízení projektu omezenými přírodními zdroji je kombinatorické optimalizační problém, studoval v plánování . Je známá pod anglickou zkratkou RCPSP (Resource-Constrained Project Scheduling Problem).

Problém je NP-těžký v nejsilnějším smyslu, takže jej lze optimálně vyřešit pouze pomocí algoritmů exponenciální složitosti. Nejmodernější řešení umožňuje jeho optimální řešení v rozumném čase, maximálně na 60 úkolů.

Popis

Koncepty

Tyto zdroje jsou obnovitelné prostředky k výrobě, ale omezená kapacita. Tým čtyř pracovníků se stejnými dovednostmi lze považovat za zdroj schopností 4.

Tyto úkoly jsou definovány pracovní doba trvání a množství každého zdroje, které jsou nezbytné pro jeho provádění. Úkoly se považují za nepředvídatelné: jakmile je spuštění spuštěno, pokračují nepřerušovaně až do dokončení. Výroba vyrobeného zboží může trvat dvě hodiny a vyžaduje práci dvou pracovníků a stroje.

Mezi úkoly existují prioritní vztahy , které klasicky znamenají, že úkol lze spustit, pouze pokud jsou dokončeny některé další úkoly. Tyto vztahy umožňují reprezentovat organizaci projektu grafem priority (nebo sítí PERT ): úkol je reprezentován uzlem, každý vztah priority je oblouk orientovaný od předchůdce k následníkovi, který je oceňován dobou trvání předchůdce. Graf priority nesmí představovat obvod, úkol nemůže být přímo ani nepřímo jeho vlastním předchůdcem.

Klasicky problém spočívá v minimalizaci konečného data projektu, vzhledem k omezením priority a zdrojů.

Formalizace

Nechť n úkolů a q zdrojů.

Jsou zaznamenány zdroje a jejich schopnosti . $R_ {k}$ $B_k$

Úkoly jsou označeny a jejich trvání jsou , úkol i vyžaduje množství zdroje k . Dvě fiktivní úkoly se obvykle přidávají, mají nulovou délku a nespotřebovávají žádné prostředky: je předchůdce jiných úkolů ( zdroj vrchol grafu), je nástupcem všech úkolů ( umyvadlo vrcholový přednost grafu). Přednosti jsou deklarovány sadou . $Mít}$ $p_ {i}$ ${\ displaystyle b_ {ik}}$ $A_0$ ${\ displaystyle A_ {n + 1}}$ ${\ displaystyle E = \ {(i, j) / A_ {i} \ rightarrow A_ {j} \}}$

Řešení S tohoto problému je vektor obsahující počáteční data každého z úkolů. ${\ displaystyle R_ {n + 2}}$

Existují dva typy omezení:

Přednost omezení: buď úkoly a , jako je ( předchází ), nemůže začít před koncem , $Mít}$ $Aj}$ ${\ displaystyle (A_ {i}, A_ {j}) \ v E}$ $Mít}$ $Aj}$ $Aj}$ $Mít}$ ${\ displaystyle S_ {j} \ geq S_ {i} + p_ {i}}$
omezení prostředků: kdykoli a pro každý zdroj nepřekročí součet požadavků na probíhající úkoly $k$ $B_k$

Metody řešení

K vyřešení problému byla použita řada nástrojů:

Seznam algoritmů

První metody vytvořené v 60. letech jsou heuristiky založené na seznamech. Seznamy priorit definují prioritu při provádění úkolů podle často heuristických kritérií, jako je čas zpracování úlohy nebo okraj. Seznam priorit musí respektovat omezení priority.

Algoritmus přísného pořadí spočívá v co nejrychlejším umístění úkolů jeden po druhém v přesném pořadí seznamu priorit.

t\leftarrow 0

Tant que la liste de priorité est non vide soit la tâche

i

que l'on retire au début de la liste de priorité

r_{i}=max(t,max_{j\in Pred(i)}(t_{j}+p_{j}))

la date à laquelle on peut ordonnancer

i

au plus tôt (

p_{j}

est la durée de la tâche j) soit

t_{i}\geq r_{i}

, la première date à laquelle les ressources sont disponibles pour l'exécution placer la tâche à la date

t_i

t\leftarrow t_{i}

Fin Tant Que

Stanovení dolní meze

Vzhledem ke složitosti problému je často iluzorní chtít určit přesné řešení problému. V operačním výzkumu se pro konkrétní vyhodnocení metody řešení hodnotí kvalita řešení porovnáním získaného konečného data s dolní mezí . Dolní mez je hodnota, o které je známo, že je nižší než datum ukončení optimálního řešení, ale je třeba získat hodnotu dostatečně vysokou, aby se přiblížila optimální hodnotě. Kvalita roztoku se měří v procentech rozdílu s dolní mez: . ${\ displaystyle C_ {max}}$ ${\ displaystyle LB}$ ${\ displaystyle {\ frac {C_ {max} -LB} {LB}}}$

Metoda kritické cesty

Vylepšená kritická cesta

Energetické uvažování

Rozšíření

Základní model RCPSP byl přizpůsoben mnoha průmyslovým aplikacím, a proto se objevily varianty problému.

Řízení projektů s více dovednostmi

Tato varianta je vhodná pro plánování projektů ve společnostech poskytujících služby, zejména ve společnostech poskytujících služby IT . Definujeme sadu dovedností, zdroje představují lidi účastnící se projektu, kapacita každého zdroje je 1. Úkol již není definován požadovaným množstvím každého zdroje, ale počtem lidí, kteří mají takové dovednosti. Například úkol „Unit Tests“ může vyžadovat dva lidi se schopností „Developer“ a jednu osobu se schopností „Analyst“.

Úkoly s více režimy

Stejný úkol lze provést různými způsoby nebo režimy . Každý režim definuje své vlastní trvání a nároky na zdroje. Součástí problému je výběr režimu k provedení úkolu.

Robustní plánování

Pro RCPSP byly vyvinuty robustní plánovací přístupy . Robustní modely v projektovém řízení berou v úvahu čtyři typy poruch:

narušení grafu projektu: úkoly (nebo odkazy priority) jsou přidány nebo odstraněny
narušení úkolů: úpravy trvání, požadavky
narušení zdrojů: zdroje jsou nedostupné (poruchy, absence) nebo je dočasně omezena jejich kapacita
časové změny

Podívejte se také

Související články

Zdroje a reference

Problém projektového řízení s omezeními zdrojů - přístupy a metody řešení GOThA - skupina "Řízení projektů s omezeními zdrojů a jeho rozšíření"

Gang Yu, Xiangtong Qi Disruption management: framework, models and applications , 2004