Оптимизация алгоритма календарного планирования с помощью динамического программирования

Full Text

Обоснование. Решение задачи составления плана регулирования численности рабочих на последующие n месяцев имеет большое практическое значение.

Цель — на основе метода динамического программирования (ДП) разработать программный продукт для решения задачи календарного планирования рабочего графика.

Методы. Поставленная задача о календарном планировании рабочего графика в данной работе решается методом динамического программирования. Метод ДП — это алгоритмический подход к решению оптимизационных задач. Он основан на принципе разбиения составной задачи на отдельные подзадачи и использовании комбинаций их решений для получения оптимального результата.

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

Введем обозначения:

x_i — количество рабочих, которые работают в месяце i; a_i — минимальное количество рабочих, необходимых в месяце i; f_i(x_i–1) — оптимальные затраты в месяце i, денежных единиц.

Результатом решения рассматриваемой задачи является вектор x^*= (x^*₁, x^*₂, ... x^*_n), компоненты которого равны оптимальному количеству рабочих в текущем месяце.

Убытки предпринимателя на содержание лишних рабочих U_л(x_i – a_i) можно представить в виде функциональной зависимости:

U_л(x_i – a_i) = 4(x_i – a_i) (i = 1; n). (1)

Расходы на найм и увольнение рабочих U_н(x_i – x_i–1) можно представить в виде:

$U_{\mathrm{н}}\left(x_i-x_{i-1}\right)=\left\{\begin{array}{l}5+3\left(x_i-x_{i-1}\right), \mathbf{при} x_i>x_{i-1},\\ 0, \mathbf{при} x_i⩽x_{i-1}. (i=1;n)\end{array}\right.$ (2)

Составим рекуррентные формулы (уравнение Беллмана) для вычисления функции цели:

f₆(x₅) = min {U_л(x₆ – a₆) + U_н(x₆ – x₅)}; (3)

f_i(x_i–1) = min {U_л(x_i – a_i) + U_н(x_i – x_i–1) + f_i+1(x_i)} (i = 1; n) (4)

Алгоритм решения реализован на языке C++.

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

В таблице 1 представлен последний этап реализации алгоритма, оптимизации в целом.

Таблица 1. Оптимальные значения в первом месяце

Оценку сложности вычислений алгоритма методом ДП по временным затратам можно описать формулой (5):

O(n(max – min)²). (5)

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

Оценку сложности вычислений алгоритма перебора по временным затратам можно описать формулой (6):

O((max – min)ⁿ). (6)

Результаты. Для сравнения эффективности алгоритмов вычислили количество вызовов функций подсчета затрат, которые соответствуют формулам 1 и 2.

Результаты решения методом ДП и перебором выведены на рис. 1 и 2 в соответствующем порядке.

Рис. 1. Листинг алгоритма на основе метода ДП

Рис. 2. Результаты работы алгоритмов

Выводы. Результаты показывают, что для решения задачи перебором всех вариантов было произведено значительно больше вычислений.

Таким образом, применение метода ДП значительно увеличивает скорость решения задачи календарного планирования.

About the authors

Author for correspondence.
Email: semen-fofanov213@yandex.ru

студент

Supplementary files

Supplementary Files

Action

1. JATS XML

Download

2. Рис. 1. Листинг алгоритма на основе метода ДП

Download (406KB)

Indexing metadata

3. Рис. 2. Результаты работы алгоритмов

Download (34KB)

Indexing metadata