| |
| |
Боровых Наталья Игоревна, natali.bor1992@mail.ru, Россия, Тула, Тульский государственный университет,
Красоткина Ольга Вячеславовна, канд. физ.-мат. наук, доц., o.v.krasotkina@yandex.ru, Россия, Тула, Тульский государственный университет. |
|
| |
ПРИМЕНЕНИЕ АЛГОРИТМА ПОИСКА С ЗАПРЕТАМИ В ЗАДАЧЕ АВТОМАТИЗИРОВАННОГО СОСТАВЛЕНИЯ ОПТИМАЛЬНОГО ШТАТНОГО РАСПИСАНИЯ |
|
| |
Выполнена математическая постановка задачи как задачи бинарного программирования. Рассмотрены существующие методы решения задачи составления
расписания: точные и приближенные. Выбран приближенный метаэвристический метод – поиск с запретами. Разработано приложение на ЯП Java, реализующее выбранный метод с применением библиотеки OptaPlanner, и произведено его экспериментальное исследование: сравнение близости полученного результата к решению на основе точного метода ветвей и границ, составление и анализ недельного расписания.
Ключевые слова: составление расписания, бинарное программирование, метаэвристики, поиск с запретами, метод ветвей и границ, OptaPlanner. |
|
В крупных организациях одной из наиболее важных проблем является проблема управления персоналом. В частности встаёт задача о составлении расписания рабочих смен сотрудников. Оптимально составленное расписание позволяет организации уменьшить затраты по привлечению сотрудников, и тем самым увеличить свою экономическую эффективность.
В данной статье рассмотрена задача составление оптимального штатного расписания работы кассиров. Эта задача актуальная в современном мире, т.к. всё большую популярность приобретают крупные сетевые магазины самообслуживания, где все выбранные товары оплачиваются покупателем на кассе. В разные дни недели и в разное время суток в магазине может находиться разное количество покупателей. При недостаточном количестве кассиров или в случае недостаточной скорости работы возникают очереди, что сказывается на качестве обслуживания и приводит к потере покупателей. С другой стороны, если кассиров больше, чем необходимо, возникают неоправданные расходы на оплату времени работы лишних кассиров.
Для повышения лояльности покупателей и минимизации расходов на оплату работы кассиров следует оптимизировать расписание с учётом возможного трафика покупателей и особенностей работы каждого кассира.
На практике подобная задача часто решается человеком вручную, что занимает много времени и не гарантирует оптимальности полученного расписания. Целью данной работы является автоматизация процесса составления оптимального штатного расписания, выбор подходящий метода решения задачи и разработка приложения, реализующего выбранный метод.
Исходными данными в рассматриваемой задаче является информация о кассирах, количество доступных рабочих мест (касс) и прогноз потока покупателей. Длительные наблюдения за потоком покупателей на различных торговых предприятиях и анализ соответствующих статистических данных свидетельствуют о том, что характер распределения числа покупателей в зависимости от времени суток и времени года является весьма устойчивым [7], поэтому данная информация может быть положена в основу составления оптимального штатного расписания. Для каждого работника указывается его производительность и стоимость часа труда.
Итак, необходимо составить оптимальное расписание смен кассиров в магазине самообслуживания. Под оптимальным, в данном случае, будем понимать расписание, минимизирующее затраты магазина по привлечению работников к выполнению работ при условии выполнения сотрудниками всего объема работ и соблюдении остальных ограничений, присутствующих в задаче. Весь интервал составления расписания разбит на элементарные промежутки времени – дискретность, с которой составляется расписание. Примем дискретность составления расписания равной 15 минутам. А количество элементарных промежутков времени в интервале планирования равным 672, т.е. будем решать задачу составления недельного расписания.
В задаче составления расписания, могут присутствовать следующие ограничения: ...
На главную страницу сайта >>
|
|
