Задача состоит из того, чтобы оптимально распределить ресурсы с минимальными временными затратами. Приоритет у работ с меньшим полным резервным временем (LS - ES или разность позднего и раннего старта), если же резерв времени одинаков, то приоритет у работы, потребляющей больше ресурсов. Я написал код на C# для критического пути, но без учета этих самых ресурсов
Код непосредсвенно "Работы"
Код:
using System;
using System.Collections.Generic;
namespace NetworkGraph
{
public class Activity
{
private string Name;
private int Duration;
private List<Activity> Predecessors;
private List<Activity> Successors;
private int[] Resources;
//
// расчетные величины
//
public int order;
// эти переменные заполняет метод критического пути
public double ES, EF, LS, LF;
// эту переменную использует топологическая сортировка
public int p_count;
public Activity(string Name, int Duration, int[] Resources) // set vector Resources wits zero and equals size
{
this.Name = Name;
this.Duration = Duration;
Predecessors = new List<Activity>();
Successors = new List<Activity>();
this.Resources = Resources;
}
public void AddPredecessorsActivity(Activity activity)
{
if(Predecessors.Contains(activity))
return;
Predecessors.Add(activity);
activity.AddSuccessorActivity(this);
}
public void AddSuccessorActivity(Activity activity)
{
if (Successors.Contains(activity))
return;
Successors.Add(activity);
activity.AddPredecessorsActivity(this);
}
public void DeletePredecessorsActivity(Activity activity)
{
if (!Predecessors.Contains(activity))
return;
Predecessors.Remove(activity);
activity.DeleteSuccessorActivity(this);
}
public void DeleteSuccessorActivity(Activity activity)
{
if (!Successors.Contains(activity))
return;
Successors.Remove(activity);
activity.DeletePredecessorsActivity(this);
}
public string GetName()
{
return Name;
}
public void SetName(string NewName)
{
Name = NewName;
}
public int GetDuration()
{
return Duration;
}
public void SetDuration(int NewDuration)
{
Duration = NewDuration;
}
public int[] GetResources()
{
return Resources;
}
public void SetResources(int[] NewResources)
{
if (Resources.Length == NewResources.Length)
Resources = NewResources;
else
throw new Exception("Lengths of vectors is not equals!");
}
public List<Activity> GetPredecessors()
{
return Predecessors;
}
public List<Activity> GetSuccessors()
{
return Successors;
}
public double GetReserv()
{
return LS - ES;
}
}
}
Код "Сетевого графа"
Код:
using System.Collections.Generic;
namespace NetworkGraph
{
public class Network
{
private List<Activity> Activities;
private List<Activity> OrderedActivities;
private int[] CriticalResources;
private int Order;
private double CriticalDuration;
public Network(int size)
{
Activities = new List<Activity>(size);
}
public Network(List<Activity> Activities, int[] CriticalResources)
{
this.Activities = Activities;
this.CriticalResources = CriticalResources;
}
public void AddRelation(Activity a, Activity b) // не факт что нужны
{
a.AddSuccessorActivity(b);
}
public void DeleteRelation(Activity a, Activity b)
{
a.DeleteSuccessorActivity(b);
}
public double NetworkComplexity()
{
int r = 0;
for (int i = 0; i < Activities.Count; i++) // этот цикл перебирает все работы проекта
r += Activities[i].GetSuccessors().Count; // на этом этапе к переменной r прибавляется кол-во прямых последователей текущей работы
return r / Activities.Count;
}
public void TopologicalSort()
{
Order = 0;
OrderedActivities = new List<Activity>();
for (int i = 0; i < Activities.Count; i++)
{
Activities[i].order = -1;
Activities[i].p_count = 0;
}
// Упорядочить все первые (у которых нет предшественников) работы проекта
foreach (Activity a in Activities)
{
if (a.GetPredecessors().Count == 0)
OrderActivity(a);
}
}
private void OrderActivity(Activity a)
{
a.order = Order;
Order++;
OrderedActivities.Add(a);
// этот цикл осуществляет перебор всех прямых последователей "s" работы "a"
foreach (Activity s in a.GetSuccessors())
{
s.p_count++;
if (s.p_count == s.GetPredecessors().Count)
{
// рекурсивный вызов
OrderActivity(s);
}
}
}
public double CriticalPathMethod()
{
CriticalDuration = 0;
TopologicalSort();
// обнуление предыдущих результатов
for (int i = 0; i < OrderedActivities.Count; i++)
OrderedActivities[i].ES = 0;
ForwardPass(); // передать начальное активити
BackwardPass(); // передать
return CriticalDuration;
}
private void ForwardPass()
{
for (int i = 0; i < OrderedActivities.Count; i++)
{
Activity a = OrderedActivities[i];
a.EF = a.ES + a.GetDuration();
if (CriticalDuration < a.EF)
CriticalDuration = a.EF;
for (int s = 0; s < a.GetSuccessors().Count; s++)
{
if (a.GetSuccessors()[s].ES < a.EF)
a.GetSuccessors()[s].ES = a.EF;
}
}
//get Activities a not predecessors
}
private void BackwardPass()
{
foreach (Activity a in Activities)
a.LF = CriticalDuration;
for (int i = Activities.Count - 1; i >= 0; i--)
{
Activity a = OrderedActivities[i];
a.LS = a.LF - a.GetDuration();
foreach (Activity p in a.GetPredecessors())
{
p.LF = a.LS;
}
}
}
}
}
А как сделать с учетом ресурсов не очень то понимаю.