Привет, друзья!

Прошу сразу простить: статью старался писать для «самых маленьких» и очень понятным языком.

Однажды, в далёком 2007 году, когда я лишь немного знал о кластеризации, нейронных сетях и «жадных» алгоритмах, передо мной стала задача о создании программы для автоматического составления расписаний.

Предыстория такова: я служил по контракту, и среди сотрудников нашего отдела было организовано дежурство. Ежедневно (и даже в выходные) кто-то назначался дежурным, и на этого несчастного возлагались ответственные и тяжёлые задачи по работе; дежурство было занятием не из простых. Мой командир заранее составлял и подписывал у командования график дежурства отдела на месяц. И эта задача, надо отметить, занимала у него вовсе не пять минут. Так как командир был добрый человек и всегда старался идти навстречу своим людям, он мог составлять график и неделю, потому что нужно было учесть все пожелания сотрудников: кто-то уходил в отпуск, кто-то из него возвращался, у кого-то были командировки, а кому-то просто нужно было забирать пораньше детей из садика по понедельникам и четвергам. Бывало и так, что командир составлял «несправедливые» графики дежурств, в которых одним людям явно доставалось побольше работы, чем другим. В работе отдела также были и «трудные дни» недели (когда в пинципе и работы было чуть больше, и она была чуть напряжённее), и если дежурство выпадало одному и тому же человеку целый месяц подряд на такие дни, то график также считался несправедливым. Такие несправедливые графики коллектив отклонял, и командиру приходилось заново с нуля составлять новый график, иногда по невнимательности кого-то «ущемляя». А что вы хотели: человеческий фактор!

Так как я был программистом, я не мог позволить продолжаться этому «обезьяннему» труду дальше. Я поискал существующие варианты софта для автоматического построения графиков дежурств, но всем необходимым критериям работы и дежуства отдела они не удовлетворяли: не хватало функционала и точности настройки. Тогда у меня возникла идея самому создать программу, которая бы автоматически составляла подобный график, пусть это занимало бы и час работы компьютера (но всё же не неделю работы человека). Я обговорил идею с командиром и отделом, и она была принята на ура. Были учтены все ньюансы и пожелания, которые мы обсудили. Так и родился проект «CoolPlanBro».

CoolPlanBro изначально создавался как бесплатное программное обеспечение с закрытым исходным кодом: если бы его «вынесли» из отдела и распространили, то ничего страшного в этом бы не было. Забегая вперёд скажу, что проект всё-таки получил дальнейшее распространение, инициатором которого был я сам. Уж очень нужна была такая программа моим друзьям, друзьям друзей и так далее. Так и пошло, ведь аналогов не было. Кроме того, люди видели, что программа работает довольно сносно и выдаёт хороший, справедливый результат, а это было заложено в её архитектуру при создании как один из основополагающих базовых принципов.

Итак, как же я создавал эту программу и что легло в её основные принципы работы? Для начала я просто сел и написал на бумажке то, что обязательно должен делать CoolPlanBro:

уметь создавать расписания на любой указанный месяц и год;

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

позволять быстро и просто корректировать выходные и праздничные дни прямо на графике дежурств перед рассчётом;

позволять быстро и просто редактировать список сотрудников, поддерживать любую длину такого списка и хранить его;

предоставлять пользователю возможность легко помечать прямо на графике дежурств желательные/нежелательные для каждого сотрудника дни дежурств, а также дни отпуска/отсутствия на службе перед рассчётом графика;

по возможности быстро производить рассчёт графика дежурств (быстрее, чем за неделю ;) );

иметь возможность аккуратно сбросить результат рассчёта и внести корректировки в типы дней;

уметь экспортировать подсчитанный график в «какой-нибудь Word» для последующей печати и подписи.

Задачи детские, и я приступил. Вопросов по интерфейсу и фичам не было, самое сложное было придумать алгоритм поиска идеального графика дежурств. Я рассуждал так: допустим, у нас есть на руках все возможные графики дежурств на следующий месяц (их триллионы, о-о-очень много). Как среди них найти лучший? В результате я пришёл вот к чему: придумал и ввёл систему штрафов. Каждый график имеет штраф. Какой бы вы график дежурств из того триллиона не рассмотрели, у него есть некий конкретный штраф — это просто целое положительное число, например, 27, которое выражает насколько «плох» этот график дежурств. Чем меньше штраф, тем лучше график. Надеюсь, я понятно рассказываю ;) То есть, если у нас есть три графика дежурств: со штрафом 15, со штрафом 22 и со штрафом 6, то самый лучший график — третий, так как у него самый маленький штраф. Самый несправедливый же — второй. Итак, задача нашего алгоритма — пройти по всем графикам дежурств, для каждого из них подсчитать штрафные баллы и найти лучший график с минимальныйм штрафом.

Как же считается штраф для конкретного графика? Очень просто: по всему графику подсчитывается и суммируется общее количество косяков. За каждый косяк на график налагается определённый штраф в баллах. Косяки бывают разные: подежурил на графике какой-то бедолага два дня подряд — штраф +30 баллов, вышел на дежурство некто несчастный из отпуска — штраф +500 баллов... и так далее. Специальный парсер анализирует график и находит все его косяки. Вот так вот после анализа для каждого графика получаем штраф. Ну а, собственно, систему штрафов придумывли и согласовывали всем отделом. Во что у нас получилось:

Отлично, научили программу считать штраф для каждого графика. Теперь вопрос: как рассмотреть все графики? Допустим, у нас 20 человек, а в месяце 30 дней, тогда общее число графиков, которые необходимо рассмотреть компьютеру равно (в первый день мы можем назначить одного из 20 человек — уже 20 вариантов, для каждого из них во второй день мы также можем назначить одного из 20 человек — уже 400 вариантов) 20³⁰ = 1 073 741 824 000 000 000 000 000 000 000 000 000 000, то есть чуть более одного дуодециллиона! Даже если бы компьютер строил и обрабатывал и считал штраф для одного графика дежурств в один такт одного ядра своего процессора, то четырёхъядерный процессор с тактовой частотой 4GHz на каждое ядро выполнял бы эту работу 6 710 886 400 000 000 000 000 000 0000 секунд, или 2.128·10²¹ лет, что составляет 150 миллиардов Возрастов Вселенной. Столько ждать мы не сможем: у кого-то через неделю уже командировки, а мы должны ориентироваться на дежурных.

Вновь повторюсь: на момент создания CoolPlanBro я очень смутно представлял себе «жадные» алгоритмы, однако, ко мне в голову пришло весьма схожее с ними решение. Важное замечнание, которое я хотел бы упомянуть перед началом рассказа о придуманном алгоритме: парсер может подсчитать штраф и для не до конца заполненого графика. А алгоритм я запрограммировал так: вначале программа насильно перебирает все возможные графики для некоторого «вменяемого» количества первых дней месяца, так, чтобы рассчёт не превысил в сумме 65535 вариантов графиков (это количество графиков даже слабый компьютер переберёт весьма быстро). То есть для P сотрудников надо найти такое количество дней D, чтобы P^D было меньше 65535. Например, для P = 12 сотрудников количество дней D = 4. Это так называемая «база» для дальнейшего построения графика. Из 12⁴ = 20736 просмотренных графиков (не до конца заполненных) программа находит лучший по минимальному штрафу, который, как я уже говорил в своей ремарке, она может подсчитать и для не до конца заполненного графика. Если лучших графиков получилось много (например, 100 — и у всех одинаково маленькой штраф), то программа для всех этих 100 графиков далее пытается найти лучший, расширяя просмотр вперёд на 1 день. В конце концов, база (лучший, но не до конца заполненный график) найдена.

Далее, отталкиваясь от базы, алгоритм перебирает все возможные графики на один день вперёд. Их число будет равно числу сотрудников. Если P = 12, то различных вариантов «база плюс один день» будет всего 12. Из 12 вариантов выбирается лучший и запоминается как текущая база. И так далее до конца месяца, алгоритм срабатывает быстро. Если на любом этапе было найдено несколько оптимальных баз, то алгоритм рассматривает их все, последовательно, и для всего множества находит лучшую следующую базу.

Так как «жадный» алгоритм не просматривает весь дуодециллион возможных графиков и может оказаться несправедливым, пропустив действительно оптимальнейший график, то для увеличения вероятности нахождения наилучшего графика я добавил в конец рассчёта этап оптимизации. На нём происходит следующее: для всех возможных пар дней (то есть 1-е число и 2-е число, 1-е число и 3-е число, и так далее, потом 2-е число и 3-е число, 2-е число и 4-е число, и так далее, в конце — 30-е число и 31-е число) сотрудники, дежурящие в эти пары дней «виртуально» меняются дежурствами, и, если такой график случайно оказывается лучше самого оптимального, то запоминается именно он.

В конце концов получам оптимальный (по моему алгоритму) график дежурств с минимальным штрафом. Ура! Теперь можем экспортировать и напечатать его из Word'а.

На этом моя работа над CoolPlanBro была завершена. Программа сразу стала пользоваться успехом в отделе, потом — в других, быстро перекочевала по флешкам из рук в руки, и, увидя это, я сам впоследствии выложил её в интернет.

Друзья, если вы хотите воспользоваться этой программой, то скачайте и пользуйтесь на здоровье! Надеюсь, она послужит вам верой и правдой и построит немало приятных и, главное, справедливых графиков для вас!

Ура-а-а-а!

По многочисленным просьбам трудящихся я выпустил новую версию: CoolPlanBro2. К уже существующему функционалу первой версии CoolPlanBro я добавил наиболее востребованные на ваш взгляд фишки:

• работает прямо в браузере!
• позволяет более гибко настраивать штрафы!
• для любого дня можно задать любое количество смен!
• для любой смены любого дня можно задать требуемое количесто дежурных!
• открытый исходный говнокод!