Докт. физ.-мат. наук Косолап А. И., Пазылова А. Т.

Украинский государственный химико-технологический университет, Украина

ОПТИМАЛЬНОЕ ОБСЛУЖИВАНИЕ ЗАЯВОК ПРИБОРАМИ

ПРИ НАЛИЧИИ ОГРАНИЧЕНИЙ

Задачи обслуживания заявок возникают в экономике, управлении, технологических процессах, компьютерных системах и других областях. Заявки выполняются в течении заданного времени фирмами, машинами, компьютерами и другими системами, которые будем называть приборами. Как правило, число заявок значительно больше числа приборов обслуживания. Тогда возникает задача оптимального распределения заявок между приборами таким образом, чтобы все заявки были обслужены (выполнены) за минимальное время.

Постановка задачи. Задано n заявок и m приборов их обслуживания, а также t_ij – время обслуживания j-й заявки на i-м приборе. Требуется определить минимальное время обслуживания всех заявок. Эта задача имеет различные обобщения. Например, заявки могут иметь приоритет. Тогда после решения задачи и определения множества заявок на каждом приборе устанавливается очередность выполнения заявок в соответствии с заданными приоритетами. Задача усложняется, если для некоторых заявок задан порядок их выполнения. Если такие заявки выполняются одним прибором, то такая задача легко решается. На выполнения заявок расходуются ресурсы и это также усложняет решение задачи.

Оптимальное обслуживание заявок сводится к решению следующей задачи

(1)

где x_ij = 1, если j-я заявка выполняется i-м прибором и x_ij = 0 в противном случае. Рассмотренная математическая модель является задачей линейного программирования с булевыми переменными. Задача (1) решалась «Поиском решений» в Excel. Даже при небольших размерностях задачи «Поиск решений» либо не находил решения, либо расчет решения был слишком долгим. Ситуация изменилась после замены задачи (1) следующей

(2)

где значение T фиксировано, а целевая функция заменена средневзвешенным временем выполнения заявок. После решения задачи (2) определялось время выполнения всех заявок T₀, затем менялось значение T = T₀ - 1, и снова решалась задача (2). Таким образом, на каждой итерации время выполнения заявок убывало. Это убывание продолжалось до тех пор, пока «Поиск решений» не выдавал сообщение, что он не может найти подходящее решение.

Для больших размерностей задачи (2) рекомендуется использование метода точной квадратичной регуляризации [1]. В этом случае, задача (2) преобразуется к виду

(3)

где z = (x, x_nm+1). В задаче (3) булевы условия опускаются и вместо них вводятся соответствующие ограничения. Параметр r > 0 достаточно выбрать равным 2, при этом ограничения задачи (3) будет определять выпуклую область. Параметр s должен удовлетворять условию

где x^* - решение задачи (2). В задаче (3) необходимо определить минимальное значение d, для которого ее решение удовлетворяет условию r||z||² = d с заданной точностью. Задача (3) при фиксированном значении d решалась прямо-двойственным методом внутренней точки [2], а значение d находилось методом дихотомии.

Теперь рассмотрим задачу при условии, что часть заявок упорядочены по времени выполнения. В этом случае, самым простым решением будет объединение таких заявок в одну. Это приведет к упрощению задачи, так как ее размерность станет меньше.

Обычно при выполнении заявок расходуются некоторые ресурсы. Обозначим через p_ij объем ресурса, который выделяется на выполнения j-й заявки при выполнении ее i-м прибором. В этом случае, задача заключается в минимизации потребления ресурса

Часто время выполнения заявок зависит от количества выделенных на них ресурсов. В этом случае количество ресурсов p_ij будет переменной, которую обозначим через y_ij. Тогда для решения задачи необходимо определить функцию t_ij(y_ij). Чем больше выделяется ресурсов на выполнения заявки, тем меньше время ее выполнения. Если положить t_ij(y_ij) = 1/y_ij и сделать замену u_ij = 1/y_ij, то задача (2) примет вид

(4)

где U – объем ресурса, выделяемый на выполнения всех заявок. Задача (4) становится квадратичной задачей с булевыми и непрерывными переменными. Как и в случае задачи (2) лучшим методом ее решения является точная квадратичная регуляризация.

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

Список использованных источников:

1. Косолап А. И. Глобальная оптимизация. Метод точной квадратичной регуляризации / А. И. Косолап. – Днепропетровск : ПГАСА, 2015. – 164 c.

2. Nocedal J., Wright S. J. Numerical optimization / J. Nocedal, S. J. Wright. - Springer, 2006. – 685 p.