Как ускорить алгоритм планирования

Здравствуйте, уважаемые хабравчане!
Наверняка многим из вас доводилось в своей работе сталкиваться с необходимостью решения задачи планирования, относящейся к области задач теории расписаний. Мне бы хотелось рассказать, каким образом можно ускорить работу такой программы, не затрагивая сам алгоритм.

Существует огромное количество подходов к решению этих задач, реализуемых путем использования и комбинирования различных эвристических, приближенных алгоритмов и алгоритмов сокращения перебора. В жизни все их реализации очень зависят от специфики предприятия, поэтому, не углубляясь в отдельное решение, рассмотрим общие шаги, позволяющие сократить время на построение результата.
Возьмем очень жизненную задачу «Распределение работ по постам». А еще пользователя, который составляет набор работ и отправляет его на планирование. И вывести ему надо не один – два варианта, а все возможные интервалы на день. Т.е. сказать, можно ли воткнуть этот набор работ на 8.00? А на 8.30? И так на весь день.

Структура данных

Каждый пост характеризуется типом работ, которые могут быть на нем выполнены. На каждом посту известны рабочие промежутки (т.е. временные отрезки, которые не заняты перерывами или другими работами). Каждая планируемая работа характеризуется нормой времени и типом.

Информация о свободных промежутков у меня с сервера тащится в такую табличку:


Работы хранятся списком следующих структур:

private class JobTypes
{
    public JobTypes(int jId, TimeSpan time, int type, string job_code = "0")
    {
        this.JobId = jId;
        this.JobRuntime = time;
        this.JobType = type;
        this.JobCode = job_code;
    }
    public int JobId { get; private set; }
    public TimeSpan JobRuntime { get; private set; }
    public int JobType { get; private set; }
    public string JobCode { get; set; }
}

При выполнении подряд нескольких работ одного типа перенос их на разные посты является нежелательной ситуацией и стоит каких-то ресурсов времени. При планировании имеет смысл ввести понятие «вес пути», которым будет определяться качество рассчитанного расписания. Каждый переход между постами должен увеличивать вес, каждое выполнение на посту не подходящего типа должно еще более утяжелять вес общего расписания. Так же на вес могут оказывать влияние разница между полученным временем окончания работ и эталонным, загруженность выбранных постов и еще куча факторов по желанию заказчика.
Если пользователю нужно показать просто любое возможное расписание — воспользуемся быстрыми приближенными методами и сделаем это. Но если отобразить надо расписание, у которого был наименьший вес, то придется реализовать метод свой метод поиска. Длительность выполнения этого метода будет расти в геометрической прогрессии в зависимости от количества работ. Соответственно, если скорость построения расписания с одной – двумя работами будет варьироваться в пределах сотых долей секунды, с четырьмя – пятью в пределах десятых, то расчет расписания более чем двадцатью мелкими работами вполне может вылезти за несколько минут. Конечно, все цифры приблизительны и сильно зависят от ситуации, но общий принцип ясен.

Проверка возможности построения

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

private bool CheckPeriodsAvailable(SchData sch_data)
{
    var jTime = from s in sch_data.jobs
            group s by new { jType = s.JobType } into g
            select new { g.Key.jType, qty = g.Sum(s => s.JobRuntime.TotalMinutes) };

    var pTime = (from s in (sch_data.BasicData.Tables["MonthFree"]).AsEnumerable()
                group s by new { jType = s.Field<int>("JobType") } into g
                select new { g.Key.jType, qty = g.Sum(s => (s.Field<DateTime>("FinTime") - s.Field<DateTime>("StartTime")).TotalMinutes) }).ToList();

    foreach (var j in jTime)
    {
        double p = pTime.Find(item => item.jType.Equals(j.jType)).qty;
        if (j.qty > p)
            return false;
    }
    return true;
}

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

Уменьшение количества итераций

Перед началом процесса планирования все работы объединяются в единые блоки, сгруппированные по типу, в порядке выполнения работ. Если в условии задачи не сказано, про зависимость заданий (т.е. что работа i+2 не может быть выполнена раньше, чем закончится i+1), то отсортируем предварительно работы по типу. Длительность каждого блока считается равной суммарной длительности всех работ, вошедших в блок.
Таким образом, на планирование будет в самом простом случае отправлено уже не 20 маленьких работ, а одна длинная. Про разницу во времени выполнения было сказано выше. Все просмотренные пути для объединенных работ стоит сохранять в некоторое дерево решений. При отрицательном результате нужно постепенно уменьшать плотность группировки и вычеркивать из области поиска те пути, которые уже были добавлены в дерево.
Как только будет найден путь с минимальным желаемым весом – остановим процесс поиска и разобьем группу обратно на отдельные работы, для представления информации о том, какая работа во сколько будет выполняться.

private List<PeriodElems> SeparateSch(List<PeriodElems> resultList, List<JobTypes> jobs, DataTable PostsData)
{
    int j = 0;
    while (j < resultList.Count)
    {
        if (((j) < jobs.Count) &&
            (resultList[j].time > jobs[j].JobRuntime) &&
            (resultList[j].type == jobs[j].JobType))
        {
            PeriodElems ins_elem = resultList[j].Clone();

            //Выберем промежутоки, куда от начала плана войдет именно разделяемая работа
            var periods = from item in (PostsData).AsEnumerable()
                            where
                            item.Field<int>("PostId") == resultList[j].post_id &&
                            (
                                (item.Field<DateTime>("StartTime") <= resultList[j].start &&
                                    item.Field<DateTime>("FinTime") > resultList[j].start) ||
                                (item.Field<DateTime>("StartTime") > resultList[j].start &&
                                    item.Field<DateTime>("FinTime") < resultList[j].fin) ||
                                (item.Field<DateTime>("StartTime") < resultList[j].fin &&
                                    item.Field<DateTime>("FinTime") >= resultList[j].fin)
                            )
                            select item;
            DataView OldMonthRows = periods.AsDataView<DataRow>();
            if (OldMonthRows.Count == 0)
            {
                return null;
            }
            //Если выбрался один промежуток - все ok, если несколько, значит были перерывы.
            TimeSpan shift_time = OldMonthRows.Count == 1 
                ? jobs[j].JobRuntime 
                : GetShiftTime(jobs[j].JobRuntime, OldMonthRows, DateTime.Parse(OldMonthRows[0]["FinTime"].ToString()) - resultList[j].start);

            //Если начало попало в перерыв и находится левее первого заполняемого промежутка - добавим сдвиг вправо
            TimeSpan delta = DateTime.Parse(OldMonthRows[0]["StartTime"].ToString()) - ins_elem.start;
            if (delta > TimeSpan.Zero)
            {
                resultList[j].start += delta;
                resultList[j].fin += delta;
            }
            ins_elem.start = resultList[j].fin = resultList[j].start + shift_time;
            if (!ins_elem.start.Equals(ins_elem.fin))
                resultList.Insert(j + 1, ins_elem);
        }
        j++;
    }
    return resultList;
}

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

private TimeSpan GetShiftTime(TimeSpan jTime, DataView OldMonthRows, TimeSpan fndTime)
{
    TimeSpan sftTime = jTime;
    if (OldMonthRows.Count > 0)
    {
        //Определим, где будет находиться конец работы.
        if (fndTime < sftTime)
        {
            sftTime = fndTime + TimeSpan.FromMinutes(Convert.ToInt32(OldMonthRows[0]["TimeToNext"]));
            for (int per_numb_s = 1; per_numb_s < OldMonthRows.Count - 1; per_numb_s++)
            {
                if (fndTime >= jTime)
                    break;
                fndTime += Convert.ToDateTime(OldMonthRows[per_numb_s]["FinTime"]) - Convert.ToDateTime(OldMonthRows[per_numb_s]["StartTime"]);
                sftTime += Convert.ToDateTime(OldMonthRows[per_numb_s]["FinTime"]) - Convert.ToDateTime(OldMonthRows[per_numb_s]["StartTime"]) + TimeSpan.FromMinutes(Convert.ToInt32(OldMonthRows[per_numb_s]["TimeToNext"]));
            }
            sftTime += jTime - fndTime;
        }
    }
    return sftTime;
}

При использовании вышеописанного подхода надо понимать, что всегда есть вероятность неудачи, тогда набор работ все равно потребуется прогнать по стандартной схеме через планирование, но суммарно времени будет затрачено больше. В моем случае заказчик решил, что лучше страдать один раз из десяти, чем все десять по чуть-чуть и методу был дан зеленый свет.
Еще для исключительно визуального ускорения стоит вынести весь расчёт в отдельный поток и дергать событие в нем на каждый рассчитанный временной интервал. Клиента же подписать на событие и выдавать пользователю результаты еще до полного окончания расчета. Так же будет не лишним отобразить прогрессбар, чтобы человек за компьютером понимал, что все работает, ничего не висит и меньше нервничал. А если он работает с клиентом (к примеру, при записи автомобиля в сервисный центр), то уже озвучил первые предложения по записи на утренние часы.
Искренне надеюсь, что кому-нибудь однажды пригодятся описанные в моей статье вещи. Спасибо за внимание.