При вахтовом планировании разнорабочего график строится из последовательности периодов работы вахтой и отдыха. Каждый работник начинает работу вахтой в своей части графика, а через определенное время график повторяется. Длина графика увеличивается с ростом числа сотрудников. В то же время необходимо учитывать различные ограничения на последовательность работы вахтой и выходные дни. Для большого числа сотрудников трудно построить расписание, удовлетворяющее требованиям. Важно обеспечить малое время решения независимо от характеристик экземпляра задачи. В данной работе вахтой от прямого работодателя предлагается новый подход к декомпозиции для составления расписания вахтовых смен. Декомпозиция использует тот факт, что большинство ограничений при вахтовом планировании рабочей силы накладываются на последовательность рабочих смен. Рассматривая фиксированный набор блоков для покрытия спроса, можно значительно уменьшить сложность задачи. Учитывая фиксированный набор блоков, мы предлагаем сетевую модель, которая определяет, существует ли выполнимая последовательность блоков смен. Подход декомпозиции применяется к структуре задачи планирования ротации рабочей силы, но может быть распространен на другие структуры задач. В вычислительном исследовании подход к декомпозиции сравнивается с математической формулировкой и предыдущими точными и эвристическими подходами. Результаты вычислений показывают, что декомпозиционный подход значительно превосходит предыдущие эвристики на стандартных эталонах.
Что играет важную роль для эффективной работы вахтой?
Человеческие ресурсы, как правило, являются одним из самых дорогих ресурсов компании. Поэтому планирование смен играет жизненно важную роль для эффективной работы вахтой. Необходимо обеспечить достаточный уровень укомплектованности персоналом при соблюдении правовых и практических ограничений для каждого отдельного графика. Одним из наиболее распространенных требований при составлении графика сменности является работа вахтой в течение нескольких дней подряд, поскольку это, как правило, подразумевает несколько выходных дней подряд.
Как правило, можно использовать либо ручной, либо вахтовый график. При вахтовом графике каждый сотрудник работы вахтой работает по одному и тому же графику с задержкой во времени. Через определенное количество дней ротационный график повторяется. Ротационные графики особенно хорошо подходят для организаций со статичным спросом на рабочую силу, рабочей нагрузкой, превышающей рабочее время одного сотрудника (например, 3 смены в день, семь дней в неделю) и однородным уровнем квалификации сотрудников. Такая структура часто встречается на производстве и в организациях государственного сектора, таких как службы скорой медицинской помощи, пожарные и полицейские департаменты (Laporte 1999). Когда подходящий график ротации найден, планирование значительно упрощается, поскольку менеджер и сотрудники повторяют один и тот же график (Becker et al. 2019). Примерный график ротации и полученное покрытие показаны на рис. 1. График охватывает модель спроса, которая повторяется через семь дней. Требования к персоналу для каждого типа смены показаны внизу. График требует наличия девяти сотрудников, которые начинают работу вахтой со смещением на семь дней, т.е. каждый Сотрудник работы вахтой может начать работу вахтой в начале другого ряда. Через 63 дня расписание повторяется с точки зрения работника. В каждом ряду расписания последний день соседствует с первым днем следующего ряда. Хотя вахтовые графики сокращают усилия по планированию, часто сообщается о негативном влиянии на здоровье и неудовлетворенности работников.
Для составления графиков сменности существуют различные коммерческие пакеты программного обеспечения. Важными аспектами вычислительных методов для планирования трудовых ресурсов являются гибкость и время вычислений, необходимые для интерактивного процесса планирования. Стандартное программное обеспечение часто не может обеспечить необходимую гибкость для решения задач планирования вахтового разнорабочего или требует большого количества вычислительного времени.
В работе вахтой от прямого работодателя Musliu (2006) предложена стандартная структура задачи планирования ротации рабочей силы (RWS). Кроме того, представлен набор эталонных задач, вдохновленный проблемами из практики для оценки вычислительных методов для RWS. Недавно набор эталонных задач был расширен (Musliu et al. 2018).
Примерный недельный график работы вахтой вахтовиков (выполнимое решение для эталонного экземпляра из Musliu et al. (2018), M \(=\) утро, A \(=\) день, N \(=\) ночь).
В нескольких исследованиях предлагаются точные и эвристические методы для RWS (Triska and Musliu 2011; Mutingi and Mbohwa 2015a; Erkinger and Musliu 2017; Musliu et al. 2018). Учитывая важность планирования вахтовых смен, эффективные вычислительные методы являются предметом постоянного интереса исследователей. Мы предлагаем новую современную эвристику декомпозиции, которая применима для задач составления расписания вахтовых смен и других типов задач составления расписания, где требуется циклический план. Декомпозиция применяется к RWS, чтобы проиллюстрировать преимущества для вычислений.
Остальная часть данной работы вахтой построена следующим образом: В разделе 2 приводится обзор литературы по подходам к решению задач планирования смен с акцентом на RWS. Формальное утверждение и математическая формулировка RWS приведены в разд. 3. Математическая формулировка служит основой для обсуждения подхода декомпозиции. Подход декомпозиции состоит из главной и подпроблем и подробно объясняется в разд. 4. Эвристика декомпозиции, использующая эвристический метод решения для основной задачи и точный метод для подзадачи, описана в разделе 5. В разделе 6 сравнивается производительность эвристики декомпозиции с предыдущими результатами и математической формулировкой из разд. 3 с использованием стандартных эталонов для RWS. Наконец, в Разделе 7 дается заключение и предлагаются некоторые перспективы для будущих исследований подхода декомпозиции.
Обзор литературы
Существует обширная литература по теории и практике составления расписания смен. Обзоры представлены в работах Ernst et al. (2004) и Van Den Bergh et al. (2013). Вычислительные методы составления расписания смен применялись к различным проблемам на практике. Многие исследования были посвящены проблеме ротации медсестер. Проблема ротации медсестер — это сложная проблема составления расписания смен, которая учитывает множество практических и юридических ограничений, а также предпочтения сотрудников. Как правило, предпочтения сотрудников и нарушение некоторых ограничений рассматриваются как цель. Из-за неоднородной квалификации медсестер, графики в основном составляются на ограниченное количество времени. Из-за сложности и разнообразия особенностей, встречающихся в отделениях сестринского ухода, проблема ротации медсестер остается одной из наиболее изученных проблем в литературе по составлению расписания смен (Burke et al. 2004). Поэтому многочисленные работы вахтой, посвященные методологии решения и подходам к декомпозиции, сосредоточены на проблемах ротации медсестер. RWS является более специализированной проблемой. Цель состоит в том, чтобы найти выполнимое расписание, которое обеспечивает требуемый уровень укомплектованности штата в любое время при однородной рабочей силе. Нарушение жестких ограничений не допускается. В данном обзоре литературы мы сосредоточимся на подходах к решению задач составления графиков сменности и составления графиков вахтового разнорабочего.
Подходы к решению задачи составления графика сменности
В литературе было исследовано множество вариантов задач планирования смен. Подходы к решению, которые были специально применены к RWS, обсуждаются в разделе 2.2. Valouxis и Housos (2000) исследуют методологию решения для ежемесячного составления списков медсестер. Они формулируют целочисленную программу, которую трудно решить с помощью стандартного коммерческого программного обеспечения. Они обнаружили, что предпочтения в отношении конкретных последовательностей работ не могут быть эффективно смоделированы с помощью целочисленного программирования. Для получения приемлемых с практической точки зрения решений используется гибридный метод решения, сочетающий локальный поиск и поиск табу. Brucker et al. (2010) предлагают подход к декомпозиции для нециклического планирования работы вахтой медсестер. На первом этапе выбираются последовательности работ с высоким качеством относительно предпочтений медсестер. На втором этапе итеративно строится расписание путем комбинирования последовательностей, удовлетворяющих ограничениям для общего списка. Для улучшения первоначально построенного расписания применяются методы локального поиска. Роча и др. (2014) рассматривают конструктивную эвристику для планирования ротации разнорабочего в стекольной промышленности. Их подход позволяет найти последовательность блоков, каждый из которых состоит из нескольких рабочих смен. Они отмечают, что количество перерывов между блоками важно для получения выполнимого решения. Представлен подход к оценке выполнимости задачи на основе параметров и полученного количества перерывов между сменами. Их исследование сосредоточено на случае постоянного спроса на рабочую силу. Они предполагают наличие ровно одной группы смен в день и смену. Brucker et al. (2011) анализируют сложность нескольких классов задач планирования разнорабочего. Представлено несколько математических моделей, которые охватывают различные случаи планирования разнорабочего.
Модели различаются на полиномиально разрешимые и NP-трудные задачи. Kiermaier et al. (2016) представляют стохастический оптимизационный подход для ротационной ротации в сфере услуг. Хотя дни и смены фиксированы, время начала работы вахтой может быть скорректировано в краткосрочной перспективе, чтобы реагировать на изменения спроса. Предлагается многоэтапная стохастическая программа, но она оказывается неразрешимой. Представлены две аппроксимации, которые сводят программу к двухэтапной задаче. Различные стратегии декомпозиции были применены к проблемам планирования смен. Более того, идея объединения последовательных рабочих смен в блоки смен часто используется в подходах к решению.
Графики работы вахтового разнорабочего
Первое исследование вахтового планирования рабочей силы представлено Бейкером (Baker, 1976). Они проводят различие между сменным графиком и графиком выходных дней. График выходных дней определяет только рабочие дни, в то время как график смен определяет смены, назначенные на каждый рабочий день. График работы вахтой по сменам — это комплексное распределение как рабочих дней, так и смен (Ernst et al. 2004). Лапорте и др. (1980) формализовали некоторые условия для вахтовых графиков и предложили алгоритм составления вахтовых графиков на основе целочисленного программирования. Они отмечают, что существенным свойством структуры вахтовых графиков является наличие чередующейся последовательности последовательных рабочих смен и выходных дней. Бартольди и др. (1980) вводят проблему (k, m)-расписания. Она включает в себя поиск расписания длины m, в котором каждый Сотрудник работы вахтой работает в течение k последовательных дней. Millar и Kiragu (1998) представляют математическую модель для циклического и нециклического планирования работы вахтой медсестер. Они строят сеть, где каждый узел напоминает либо последовательность рабочих смен, либо выходных дней. Математическая формулировка находит кратчайший путь в сети с боковыми ограничениями для построения расписания. Rocha et al. (2013) предлагают новую математическую формулировку для циклического планирования разнорабочего. В модель включен новый подход к формулировке ограничений последовательности работ. Практическая применимость проиллюстрирована на двух конкретных примерах. Balakrishnan и Wong (1990) представляют сетевую модель для проблемы планирования ротации разнорабочего (RWS).
Муслиу и др. (2002) предлагают четырехшаговый подход к декомпозиции для RWS. Они начинают с выбора фиксированного набора допустимых длительностей рабочих блоков. Затем строится расписание, в котором назначаются рабочие и выходные дни, путем выбора определенной последовательности рабочих блоков и выходных дней. При построении расписания также учитываются предпочтения в отношении выходных дней. Далее перечисляются возможные последовательности смен с учетом возможных последовательностей рабочих блоков, и последовательности смен назначаются на рабочие блоки таким образом, чтобы обеспечить выполнение требований к персоналу. Следует отметить, что можно построить различные графики, изменив порядок рабочих блоков. Moerz и Musliu (2004) предлагают генетический алгоритм для RWS. Представлены новые операторы мутации и кроссинговера. Musliu (2006) представляет унифицированную структуру задачи и эталонный набор из 20 тестовых примеров, которые вдохновлены реальными приложениями по планированию вахтовых работ вахтой. В эталонный набор включены несколько примеров задач из литературы. Они предлагают новые эвристические методы для автоматического составления расписания вахтового разнорабочего. Эксперименты показывают, что эвристика поиска табу со стратегией минимизации конфликтов (MC-T) хорошо подходит для решения RWS. MC-T значительно превосходит стандартное программное обеспечение для составления графиков сменности. Хотя многие экземпляры задачи решаются быстро, для нескольких экземпляров все еще наблюдается большое время решения.
Различные алгоритмы и методы были применены к предоставленному набору эталонов
Musliu (2011) применяют метод итерированного локального поиска для RWS. Для некоторых случаев их подход быстрее, чем современный, а общая производительность сопоставима. Triska и Musliu (2011) предлагают формулировку программирования с ограничениями для RWS. Как формулировка программирования с ограничениями, она представляет собой точный метод. Для некоторых небольших экземпляров задачи время решения ниже, чем у MC-T . В целом, он не выдерживает конкуренции со временем решения MC-T. Mutingi и Mbohwa (2015a) и Mutingi и Mbohwa (2015b) применяют варианты эволюционного алгоритма для RWS. Алгоритмы вдохновлены биологическим процессом метаморфозы. По сравнению с MC-T, среднее время решения их алгоритма, показавшего наилучшие результаты, меньше в два раза.
Роча и др. (2013) демонстрируют, что их общая математическая формулировка для циклического планирования разнорабочего также применима к RWS, хотя она не была специально разработана для RWS. Однако многие задачи не могут быть решены в установленные сроки. Эркингер и Муслиу (2017) исследуют удовлетворительность модульных теорий как вариант точного метода решения RWS . Некоторые экземпляры тестового набора могут быть решены быстро. Тем не менее, для некоторых экземпляров не удается найти приемлемое решение в течение заданного времени.
В работе Musliu et al. (2018) оцениваются различные математические формулы и формулы программирования с ограничениями для решения RWS. Математические формулировки решаются с помощью Gurobi, и наилучшая производительность достигается при использовании детерминированного ограничения конечного автомата для обеспечения выполнимых последовательностей сдвигов. Хотя этот тип ограничений обычно используется в программировании с ограничениями, они отмечают, что Gurobi способен преобразовать математическую формулировку в сетевую модель, которая может быть решена очень эффективно. Наилучшая общая производительность получена в формулировке программирования с ограничениями, которая решается с помощью Chuffed. В этой формулировке используется подход прямого моделирования, где в основном существует соответствие один-к-одному между ограничениями модели и практическими ограничениями. Для усиления формулировки добавляются допустимые неравенства. Кроме того, эталонный набор, предложенный Musliu (2006), расширен еще 1980 случайно сгенерированными экземплярами задач реалистичной структуры, так что всего получено 2000 экземпляров. Проведены обширные вычислительные эксперименты для сравнения математических формул и формул программирования ограничений с другими точными и эвристическими методами для RWS. Вычислительные эксперименты показали, что формулировка программирования с ограничениями является самым быстрым современным методом получения решений для RWS. Более того, эксперименты показывают, что математическое программирование наиболее устойчиво к обнаружению неосуществимости.
Musliu (2013) отмечает, что наиболее эффективный метод решения зависит от характеристик конкретного экземпляра. Используя больший набор тестов, они применяют различные методы машинного обучения для выбора метода решения на основе характеристик экземпляра.
Последствия
Было предложено много подходов к решению задач составления расписания смен. Подходы декомпозиции часто успешно использовались для решения задач ротации медсестер. Ряд подходов к решению был применен для RWS. Только недавно были предложены подходы к решению, которые обеспечивают меньшее время решения по сравнению с эвристикой, предложенной вместе с эталонным набором (Musliu 2006; Mutingi and Mbohwa 2015b; Musliu et al. 2018). Вычислительное время, необходимое для составления выполнимого расписания, является важным предпочтением лиц, принимающих решения (Burke et al. 1999). Таким образом, важно, чтобы методы решения быстро генерировали выполнимые расписания независимо от экземпляра задачи. Более того, существует дальнейший потенциал для сокращения времени вычислений современных методов решения. Данная работа вахтой восполняет этот пробел, предлагая новый подход к декомпозиции, который применяется к RWS. Он отличается от существующего подхода к декомпозиции, предложенного Musliu et al. (2002), поскольку в главной и проблеме учитываются различные ограничения. В частности, декомпозиционный подход, представленный в данной работе вахтой от прямого работодателя, учитывает кадровые требования в главной задаче. Таким образом, главная задача должна рассматривать полный набор выполнимых последовательностей рабочих смен. В результате отпадает необходимость в промежуточном шаге, определяющем выполнимые последовательности смен для выбранных рабочих дней, а в подзадаче не нужно учитывать требования к персоналу. Кроме того, для эффективного перечисления пространства решений проблемы используется точный подход, основанный на сетевой модели.
Новый подход к декомпозиции, предложенный в данной работе вахтой от прямого работодателя, применяется к RWS, и результаты вычислений показывают, что он очень эффективен для выполнимых экземпляров по сравнению с современным уровнем техники с использованием недавно предложенного набора эталонов.
Описание проблемы и математическая формулировка
Далее мы приводим формальное описание проблемы планирования ротации рабочей силы (RWS) (Musliu 2006). В таблице 1 приведен обзор параметров, используемых в описании проблемы и математической формулировке.
Описание проблемы
RWS включает в себя построение расписания для заданной рабочей силы и количества дней, которое точно покрывает все потребности смены в каждый день. Требования смены задаются для каждой смены в каждый день отдельно. Различные типы смен могут включать в себя утренние, дневные и ночные смены. В экземпляре задачи RWS персонал может быть разделен на однородные группы или каждый Сотрудник работы вахтой может рассматриваться в явном виде. Более формально, учитывая набор работников E, необходимо составить расписание на определенное количество дней, которое может повторяться, чтобы покрыть спрос для каждого дня d и типа смены s. Длина расписания определяется количеством работников и смещением между днями начала работы вахтой каждого работника. Например, на рис. 1 показано расписание для 9 сотрудников. Смещение между днями начала работы вахтой равен семи. Как правило, число семь дней выбирается для продолжительности одного периода времени. Это гарантирует, что расписание будет чередоваться по одним и тем же дням недели. Через некоторое количество дней, расписание повторяется. К этому моменту каждый Сотрудник работы вахтой отработал полный график, так что равное распределение работы вахтой между сотрудниками обеспечено. Спрос задается для каждого дня. Если спрос повторяется более семи дней, то для значения необходимо выбрать больший промежуток времени. График должен соответствовать различным ограничениям в отношении последовательности рабочих смен и выходных дней. Минимальное и максимальное количество дней для каждой рабочей смены определяется соответственно. То есть, каждая последовательность смен должна включать не менее 15 и не более 30 дней подряд. Между сменами должно быть как минимум 3 выходных дней и как максимум 7 выходных дней. Последовательность смен может состоять из различных типов смен. В рамках рабочей последовательности минимальное и максимальное количество последовательных смен.
Наконец, существуют запрещенные последовательности сдвигов разной длины. Обозначает множество запрещенных последовательностей последовательных сдвигов. Эти последовательности сдвигов не могут встречаться в блоке сдвигов. Последовательности смен относятся к запрещенным последовательностям между двумя блоками смен с одним выходным днем между ними. Запрещенной последовательностью смен может быть, например, ночная смена, за которой следует утренняя смена на следующий день, или дневная смена, за которой следует выходной день и утренняя смена. Мы предлагаем следующую математическую формулировку для RWS. Цель состоит в том, чтобы найти решение, удовлетворяющее всем ограничениям. Несколько математических формулировок с похожими характеристиками. Это прямая формулировка в том смысле, что большинство практических ограничений могут быть непосредственно сопоставлены с математическими ограничениями. Таким образом, чтобы применить эту математическую формулировку, проблема должна обладать характеристиками, подробно описанными в предыдущем разделе.
Добавить комментарий
Для отправки комментария вам необходимо авторизоваться.