Редактировать: Данная целевая функция является нелинейной, как указал Морон в коммитах. Следовательно, этот ответ может не использоваться.
Один из возможных подходов - решить ее с помощью линейного программирования. Вот что я имел в виду. Введите переменную решения T_i_j, которая установлена в 1, если мы начнем задачу i в момент времени j (я буду считать задачи от 0 до 3). Кроме того, мы хотим «наказать» задачи планирования близко друг к другу, если им нужны одни и те же ресурсы. В данном примере мы хотим наказать T0_m и T1_n на основе разницы между m и n, 3. Затем мы можем смоделировать проблему следующим образом
Minimize:
3 * T0_0 * T1_1 + 2 * T0_0 * T1_2 + 1 * T0_0 * T1_3
+ 3 * T0_1 * T1_2 + 2 * T0_1 * T1_3
+ 3 * T0_2 * T1_3
+ 3 * T1_0 * T2_1 + 2 * T1_0 * T2_2 + 1 * T1_0 * T2_3
+ 3 * T1_1 * T2_2 + 2 * T1_1 * T2_3
+ 3 * T1_2 * T2_3
Subject to
// We start a task exactly once.
T0_0 + T0_1 + T0_2 + T0_3 = 1
T1_0 + T1_1 + T1_2 + T1_3 = 1
T2_0 + T2_1 + T2_2 + T2_3 = 1
T3_0 + T3_1 + T3_2 + T3_3 = 1
// We can only start a single task at a given time.
T0_0 + T1_0 + T2_0 + T3_0 = 1
T0_1 + T1_1 + T2_1 + T3_1 = 1
T0_2 + T1_2 + T2_2 + T3_2 = 1
T0_3 + T1_3 + T2_3 + T3_3 = 1
Затем мы можем использовать решатель целочисленного программирования , чтобы найти лучшие комбинации для запуска заданий.
Модель выше была сгенерирована с этим (довольно ужасным, но должен дать вам идею) кодом
class Program
{
private static string[][] s_tasks = new string[][]
{
new string[] { "A", "B"},
new string[] { "B", "C"},
new string[] { "C", "D"},
new string[] { "E" }
};
static void Main(string[] args)
{
string filePath = Path.Combine(Environment.GetEnvironmentVariable("USERPROFILE"), @"Desktop\lin_prog.txt");
using (TextWriter writer = new StreamWriter(filePath, false))
{
Console.SetOut(writer);
Console.WriteLine("Given tasks");
PrintTasks();
Console.WriteLine();
Console.WriteLine("Minimize:");
PrintObjectiveFunction();
Console.WriteLine();
Console.WriteLine("Subject to");
PrintConstraints();
}
}
static void PrintTasks()
{
for (int taskCounter = 0; taskCounter < s_tasks.Length; taskCounter++)
{
Console.WriteLine("Task {0}: [ {1} ]", taskCounter, String.Join(", ", s_tasks[taskCounter]));
}
}
static void PrintConstraints()
{
Console.WriteLine("// We start a task exactly once.");
for (int taskCounter = 0; taskCounter < s_tasks.Length; taskCounter++)
for (int timeCounter = 0; timeCounter < s_tasks.Length; timeCounter++)
{
Console.Write("T{0}_{1}", taskCounter, timeCounter);
if (timeCounter != s_tasks.Length - 1)
{
Console.Write(" + ");
}
else
{
Console.WriteLine(" = 1");
}
}
Console.WriteLine();
Console.WriteLine("// We can only start a single task at a given time.");
for (int timeCounter = 0; timeCounter < s_tasks.Length; timeCounter++)
for (int taskCounter = 0; taskCounter < s_tasks.Length; taskCounter++)
{
Console.Write("T{0}_{1}", taskCounter, timeCounter);
if (taskCounter != s_tasks.Length - 1)
{
Console.Write(" + ");
}
else
{
Console.WriteLine(" = 1");
}
}
}
static void PrintObjectiveFunction()
{
StringBuilder objective = new StringBuilder();
for (int currentTaskCounter = 0; currentTaskCounter < s_tasks.Length; currentTaskCounter++)
{
string[] currentTask = s_tasks[currentTaskCounter];
for (int otherTaskCounter = currentTaskCounter + 1; otherTaskCounter < s_tasks.Length; otherTaskCounter++)
{
string[] otherTask = s_tasks[otherTaskCounter];
if (ShouldPunish(currentTask, otherTask))
{
int maxPunishment = s_tasks.Length;
for (int currentTimeCounter = 0; currentTimeCounter < s_tasks.Length; currentTimeCounter++)
{
string currentTaskDecisionVar = String.Format("T{0}_{1}", currentTaskCounter, currentTimeCounter);
for (int otherTimeCounter = currentTimeCounter + 1; otherTimeCounter < s_tasks.Length; otherTimeCounter++)
{
string otherTaskDecisionVar = String.Format("T{0}_{1}", otherTaskCounter, otherTimeCounter);
// Punish tasks more in objective function if they are close in time when launched.
int punishment = maxPunishment - (otherTimeCounter - currentTimeCounter);
if (0 != objective.Length)
{
objective.Append(" + ");
}
objective.AppendFormat
(
"{0} * {1} * {2}",
punishment, currentTaskDecisionVar, otherTaskDecisionVar
);
}
objective.AppendLine();
}
}
}
}
// Nasty hack to align things.
Console.Write(" " + objective.ToString());
}
static bool ShouldPunish(string[] taskOne, string[] taskTwo)
{
bool shouldPunish = false;
foreach (string task in taskOne)
{
// We punish tasks iff. they need some of the same resources.
if(taskTwo.Contains(task))
{
shouldPunish = true;
break;
}
}
return shouldPunish;
}
}
Несколько вещей на заметку
- Приведенный выше код выполняется примерно так: O (n ^ 5), где n - количество задач. Это просто для генерации модели; целочисленное программирование является NP-полным.
- Я ни в коем случае не специалист по операциям. Я просто попробовал для развлечения.
- Решение, изложенное выше, не использует внутренних ограничений, которые может содержать проблема. Я мог легко предположить, что специализированный алгоритм планирования работы будет работать намного лучше (хотя я все еще думаю, что проблема NP-завершена)
- Если я прав в том, что проблема является NP-полной, то вам, вероятно, будет намного лучше использовать дешевую эвристику и быстро запускать задачи (если вы не можете заранее рассчитать решение и использовать много раз) .