Возврат - содержание >>

8. Результаты использования алгоритма с полиномиальной сложностью

При внимательном рассмотрении нашей задачи - составления рабочих графиков для многосменной работы оказалось, что она не является точной копией (постановкой) общей задачи составления расписаний, и что наша задача является ее частным случаем. Причем, самое главное, что наша задача не входит в класс NP-полных задач.

Для ее решения удалось разработать алгоритм и соответствующую этому алгоритму программу, с полиномиальной сложностью (степенью полинома) не выше четырех. Более подробную информацию о программе можно получить обратившись по адресу: pilikov@comail.ru электронной почты, а здесь лишь коротко упомянем, что данный алгоритм основан на комбинации стандартного генетического алгоритма и метода ветвей и границ. Эти методы решения дискретных экстремальных задач широко описаны в учебной литературе. Сама же программа реализована в виде внешней компоненты для системы 1С:Предприятие.

Следует отметить, что время решения задачи очень сильно возрастает с ростом ее размерности. При увеличении размерности задачи в 2 раза, время решения увеличивается в 16 раз. Напомним, что в нашем случае размерность - это количество работников для которых нужно составить расписание. Так, например, если для 100 человек время расчета, на обычном персональном компьютере, составляет 3 секунды, то для 200 человек это время уже будет около 48 секунд, а для 400 человек, уже около 13 минут. Для построения расписания размерностью 800 человек время расчета составит около 3-х с половиной часов, а для 1600 человек более 2-х суток. Тем не менее, подходя к вопросу с практической стороны, отметим, что производственный участок, на котором в единой цепочке (на конвейере, на поточной линии) одновременно работает более 40 человек представить себе достаточно сложно. А для его обслуживания в 3 смены (т.е. при круглосуточной работе) требуется около 170 человек. Таким образом, можно говорить о том, что любая "практическая" задача может быть решена в диалоговом режиме работы оператора (работника отдела кадров, начальника цеха, мастера и т.п.).

Следует так же иметь в виду, что если предприятие большое (несколько тысяч человек или более), то оно всегда делится на различные более мелкие подразделения - цеха, участки и т.п., и составлять рабочие графики для такого предприятия нужно по частям. Время на ввод информации о работниках предприятия в количестве двухсот человек, является куда большим, чем время расчета самого расписания. Для вывода информации (готовые графики для рабочих и администрации), так же потребуется время куда большее, чем время работы компьютера при расчете графика (понадобится вывести на принтер 200 листов бумаги).

Возврат - содержание >>

На главную страницу сайта >>