Результаты применения упрощенного алгоритма

Алгоритм расчёта по упрощённому алгоритму показан в листинге 2:

Листинг 2: Описание упрощенного алгоритма (на языке Java).

/**

• * Рассчитывает конечный результат
• *
• * @return рассчитанные данные
• */

public ArrayList<int[]> calc () {.

// заполняем список сотрудников, пока есть свободные часы

while (intermediateData.size () > 0) {.

addEmployee ();

}.

// заполненную конечную таблицу

return outputData;

}.

/**.

• * добавляет график сотрудника к конечным данным
• */

private void addEmployee () {.

// график сотрудника для заполнения

int[] newLine = new int[MAX_COLUMN_COUNT];

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

int workHours = 0;

// начало рабочего дня у сотрудника

int firstHour = 0;

// пропускаем пустые ячейки

for (int skip = 0; skip < MAX_COLUMN_COUNT && intermediateData. get (0)[skip] == 0; ++skip) {.

firstHour = skip + 1;

}.

// количество часов в строек должно быть гарантированно больше 0,

// т.к. пустые строки удаляются сразу после переноса ячеек.

// Поэтому начальный час будет найден

assert (firstHour < MAX_COLUMN_COUNT);

// последний час рабочего дня сотрудника

int endHour = firstHour;

// сначала заполняем часы по порядку, пропустив самый малочисленный час

final int emptiestHour = calcEmptiestHour (firstHour + 1, firstHour + MAX_VALUES_RANGE — 1);

for (int hour = firstHour; hour < firstHour + MAX_VALUES_RANGE.

&& hour < MAX_COLUMN_COUNT.

&& workHours < MAX_VALUES_IN_ROW; ++hour) {.

if (hour == emptiestHour) continue; // нашли самый малочисленный час. пропускаем

// убираем ячейку из временных данных и помещаем её в данные сотрудника

newLine[hour] = removeCell (hour);

if (newLine[hour] ≠ 0) {.

endHour = hour;

++workHours;

}.

}.

// пытаемся добавить часы снаружи

if (workHours < MAX_VALUES_IN_ROW && endHour — firstHour + 1 < MAX_VALUES_RANGE) {.

int leftExpand = firstHour, rightExpand = endHour;

// итеративно расширяем область поиска свободного часа

for (int expand = 1, maxExpand = MAX_VALUES_RANGE — workHours;

expand <= maxExpand.

&& workHours < MAX_VALUES_IN_ROW.

&& endHour — firstHour + 1 < MAX_VALUES_RANGE; ++expand) {.

// двигаемся в ширину, если это возможно

if (leftExpand — 1 >= 0) —leftExpand;

if (rightExpand + 1 < MAX_COLUMN_COUNT) ++rightExpand;

// проверяем левую границу

if (newLine[leftExpand] == 0 && endHour — leftExpand < MAX_VALUES_RANGE) {.

// расширив границу остались в заданных параметрах.

// Пытаемся получить свободный час

newLine[leftExpand] = removeCell (leftExpand);

if (newLine[leftExpand] ≠ 0) {.

++workHours;

firstHour = leftExpand;

}.

}.

// проверяем правую границу

if (newLine[leftExpand] == 0.

&& workHours < MAX_VALUES_IN_ROW.

&& rightExpand — firstHour < MAX_COLUMN_COUNT) {.

// расширив границу остались в заданных параметрах.

// Пытаемся получить свободный час

newLine[rightExpand] = removeCell (rightExpand);

if (newLine[rightExpand] ≠ 0) {.

++workHours;

endHour = rightExpand;

}.

}.

}.

}.

// не удалось полностью заполнить рабочий день. Попытаемся ещё раз внутри и снаружи

if (workHours < MAX_VALUES_IN_ROW) {.

// пытаемся заполнить пустоты внутри

for (int hour = firstHour+1; hour < endHour.

&& workHours.

if (newLine[hour] ≠ 0) continue;

// пытаемся получить свободный час для сотрудника

newLine[hour] = removeCell (hour);

if (newLine[hour] ≠ 0) {.

++workHours;

}.

// рабочий день для сотрудника не может быть пустым,

// т.к. при входе в функцию во временной таблице всегда есть ячейки.

assert(workHours > 0);

outputData.add (newLine);

}.

Результирующая таблица выглядит таким образом:

Таблица 7 — График работы персонала, полученный при помощи упрощенного алгоритма.

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