SPT – Алгоритм наименьшего времени обработки: Как ускорить производство и повысить оборачиваемость

Алгоритм SPT

Определение и истоки алгоритма SPT

         В сердце производственного планирования и оперативного управления находится стремление к максимизации пропускной способности, минимизации времени простоя оборудования и сокращению общих сроков выполнения заказов. В этом стремлении одним из старейших и наиболее интуитивно понятных инструментов является алгоритм SPT, или Shortest Processing Time (Наименьшее Время Обработки). Этот алгоритм, часто рассматриваемый как основополагающий принцип в теории расписаний, предписывает приоритетное выполнение задач, требующих наименьшего времени для завершения. SPT представляет собой простое, но эффективное правило принятия решений, которое может быть применено в самых разных производственных условиях, от небольших мастерских до крупных промышленных предприятий. Его привлекательность заключается в его доступности и относительной легкости реализации, что делает его популярным выбором для практиков, ищущих быстрое и понятное решение сложных проблем планирования. При кажущейся простоте алгоритма SPT скрывается богатая история и глубокие математические основы, которые обуславливают его эффективность и определяют границы применимости.

         SPT не возник из вакуума. Его истоки уходят корнями в ранние работы по теории расписаний, где исследователи стремились найти правила, позволяющие оптимально распределять ресурсы между конкурирующими задачами. Хотя конкретные имена и даты часто трудно установить, общая идея приоритетного выполнения более коротких задач, вероятно, возникла из практического опыта в производственных средах. Интуиция, лежащая в основе этого подхода, состоит в том, что завершение небольших задач высвобождает ресурсы быстрее, позволяя начать обработку большего числа задач в целом. С точки зрения теории массового обслуживания, завершение более коротких задач снижает среднее время ожидания в системе, что приводит к повышению общей производительности.

         В эпоху, предшествующую широкому распространению компьютеров, SPT (Shortest Processing Time - правило кратчайшего времени обработки) часто применялся интуитивно или с использованием простых ручных методов. Менеджеры производства, опираясь на свой опыт и знания технологических процессов, могли вручную составлять расписания, отдавая предпочтение задачам с наименьшим временем выполнения.

         Можно показать, что SPT минимизирует среднее время завершения задач. Это можно продемонстрировать, рассмотрев перестановки задач и доказав, что любая перестановка, отличающаяся от SPT, приведет к увеличению среднего времени завершения.

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

         Формулы, используемые для анализа алгоритма SPT, обычно включают в себя расчет среднего времени завершения, среднего времени ожидания и максимального времени запаздывания. Среднее время завершения вычисляется как сумма времен завершения всех задач, деленная на количество задач. Среднее время ожидания вычисляется как сумма времен ожидания всех задач, деленная на количество задач. Максимальное время запаздывания определяется как максимальная разница между временем завершения задачи и ее сроком. SPT, как правило, хорошо работает с точки зрения минимизации среднего времени завершения и среднего времени ожидания, но может приводить к увеличению максимального времени запаздывания, поскольку более длительные задачи могут задерживаться на неопределенный срок.

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

Применение алгоритма SPT в различные эпохи и сравнение с альтернативными методами

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

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

         Исторически, SPT применялся в различных формах и с различной степенью формализации. В ранних производственных системах, как уже упоминалось, SPT часто использовался интуитивно, без использования сложных математических моделей. Однако, с развитием теории расписаний и вычислительной техники, SPT стал применяться более систематично и с использованием более точных методов. В 1960-х и 1970-х годах, с появлением первых систем управления производством (MRP), SPT начал интегрироваться в эти системы, позволяя предприятиям автоматизировать процесс планирования и управления производством. В 1980-х и 1990-х годах, с развитием концепции "бережливого производства", SPT стал рассматриваться как один из инструментов для повышения эффективности и сокращения потерь. В настоящее время, с развитием "Индустрии 4.0" и появлением новых технологий, таких как интернет вещей (IoT) и искусственный интеллект (AI), SPT продолжает развиваться. FIFO, который предписывает выполнять задачи в порядке их поступления, является простым и справедливым методом, но не всегда приводит к оптимальным результатам с точки зрения пропускной способности и сроков выполнения заказов. Другим распространенным методом является EDD (Earliest Due Date), который предписывает приоритетное выполнение задач с самым ранним сроком. EDD хорошо работает с точки зрения минимизации максимального времени запаздывания, но может приводить к увеличению среднего времени завершения и среднего времени ожидания. Существуют также более сложные методы, такие как правило CR (Critical Ratio), которое учитывает как время обработки, так и срок выполнения задачи, и правило SLACK, которое учитывает запас времени до срока выполнения задачи.

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

Формулы, определяющие SPT, и их практическое применение

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

         Одной из ключевых характеристик, которые SPT стремится минимизировать, является среднее время завершения (Mean Completion Time, MCT). MCT определяется как сумма времен завершения всех задач, деленная на количество задач. Пусть Ci обозначает время завершения i-й задачи, а n обозначает общее количество задач. Тогда MCT может быть выражено следующим образом:

         Время завершения каждой задачи зависит от порядка, в котором задачи выполняются. В случае SPT задачи упорядочиваются в соответствии с их временем обработки, от наименьшего к наибольшему. Пусть pi обозначает время обработки i-й задачи. Тогда, если задачи упорядочены в соответствии с SPT, время завершения i-й задачи может быть выражено следующим образом:

         Подставляя это выражение в формулу для MCT, получаем:

         Эта формула показывает, что MCT зависит от порядка, в котором задачи выполняются. SPT стремится минимизировать MCT, упорядочивая задачи в соответствии с их временем обработки. Математически можно доказать, что SPT действительно минимизирует MCT, рассмотрев перестановки задач и показав, что любая перестановка, отличающаяся от SPT, приведет к увеличению MCT.

         Другой важной характеристикой, которую SPT стремится минимизировать, является среднее время ожидания (Mean Waiting Time, MWT). MWT определяется как сумма времен ожидания всех задач, деленная на количество задач. Время ожидания i-й задачи определяется как разница между временем ее завершения и временем ее поступления. Однако, в простейшем случае, когда все задачи доступны одновременно, время ожидания i-й задачи может быть выражено следующим образом:

         То есть, время ожидания i-й задачи равно сумме времен обработки всех задач, предшествующих ей в расписании. Тогда MWT может быть выражено следующим образом:

         Эта формула показывает, что MWT также зависит от порядка, в котором задачи выполняются. SPT стремится минимизировать MWT, упорядочивая задачи в соответствии с их временем обработки. Как и в случае с MCT, можно математически доказать, что SPT действительно минимизирует MWT, рассмотрев перестановки задач и показав, что любая перестановка, отличающаяся от SPT, приведет к увеличению MWT.

         Однако, SPT не всегда является оптимальным методом с точки зрения всех возможных критериев. Одним из недостатков SPT является то, что он может приводить к увеличению максимального времени запаздывания (Maximum Lateness, ML). ML определяется как максимальная разница между временем завершения задачи и ее сроком. Пусть di обозначает срок i-й задачи. Тогда ML может быть выражено следующим образом:

         SPT может приводить к увеличению ML, поскольку он отдает предпочтение более коротким задачам, что может приводить к задержкам в выполнении более длительных задач, особенно если у них относительно ранние сроки. В таких случаях могут потребоваться более сложные методы, такие как EDD или CR, которые учитывают как время обработки, так и срок выполнения задачи.

         На практике, применение формул для анализа SPT требует сбора данных о времени обработки задач, сроках и других факторах, влияющих на производственный предприятия.

         Одним из главных преимуществ SPT является его простота реализации и понимания. В отличие от более сложных методов, требующих знания теории расписаний и математического моделирования, SPT может быть применён интуитивно или с использованием простых ручных методов. Это делает его доступным для широкого круга пользователей. С точки зрения максимизации пропускной способности и минимизации среднего времени завершения задач, SPT математически доказуемо минимизирует MCT и MWT, что приводит к повышению общей производительности и сокращению времени выполнения заказов. Это особенно важно в современных производственных средах, где предприятия стремятся к быстрому реагированию на изменения спроса и к сокращению сроков поставки продукции.

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

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

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

         Кроме того, SPT не учитывает психологический фактор. Выполнение более коротких задач может приводить к повышению мотивации и удовлетворенности персонала, поскольку они видят быстрые результаты своей работы. Однако, постоянное выполнение только коротких задач может приводить к ощущению рутины. Поэтому SPT часто корректируется с использованием других методов, таких как EDD или CR, для учета сроков и приоритетов. Также, SPT может быть использован в рамках более сложных систем планирования, таких как системы имитационного моделирования, которые позволяют оценить эффективность различных стратегий планирования в различных сценариях.

Актуальность и перспективы SPT в "1С:Предприятие" и заключительные размышления

         В контексте платформы "1С:Предприятие", SPT представляет собой ценный инструмент, который может быть интегрирован в различные подсистемы управления производством. Актуальность SPT в "1С:Предприятие" обусловлена широким распространением этой платформы на предприятиях малого и среднего бизнеса, где простота и доступность решений имеют первостепенное значение.

         Интеграция SPT в "1С:Предприятие" может быть реализована. Модули учета рабочего времени могут быть использованы для сбора данных о времени обработки задач и для формирования расписания выполнения задач в соответствии с SPT. Специализированные разработки, такие как внешние компоненты и алгоритмы, реализованные на встроенном языке "1С:Предприятие", могут быть использованы для реализации более сложных алгоритмов SPT, учитывающих различные факторы и ограничения.

         Однако, при реализации SPT в "1С:Предприятие" необходимо учитывать особенности конкретной производственной среды. В некоторых случаях, SPT может быть применен непосредственно, без каких-либо изменений. В других случаях, может потребоваться адаптация алгоритма SPT к специфическим требованиям предприятия. Например, может потребоваться учитывать наличие ограничений по ресурсам, требования к квалификации персонала или особенности технологических процессов.

         Перспективы SPT в "1С:Предприятие" связаны с развитием новых технологий, таких как интернет вещей (IoT) и искусственный интеллект (AI). Интеграция с IoT-датчиками позволяет собирать данные о времени обработки задач в режиме реального времени, что позволяет адаптировать расписание выполнения задач к изменениям в производственной среде. Использование AI-алгоритмов позволяет анализировать большие объемы данных и выявлять закономерности, которые могут быть использованы для оптимизации расписания выполнения задач.

         В заключение, алгоритм SPT является ценным инструментом планирования и управления производством, который может быть успешно применен в различных отраслях и секторах. Его простота реализации и эффективность с точки зрения максимизации пропускной способности делают его привлекательным выбором для практиков, ищущих быстрое и понятное решение сложных проблем планирования. Однако, при применении SPT необходимо учитывать его ограничения и адаптировать его к специфическим требованиям конкретной производственной среды. В контексте платформы "1С:Предприятие", SPT может быть интегрирован и сочетания с другими методами.

P.S. Статья для начинающих программистов. Рабочую обработку для алгоритма SPT прикладываю к статье, она сделана для кулинаров.

Все первоначальные заказы формирую для демонстрации программно (вы же можете взять реальные данные из вашей базы), которые всякий раз формируются новые и с новыми данными по кнопке "Выполнить":

// Оборудование и его время готовности
    Оборудование = Новый Структура;
    Оборудование.Вставить("Духовка", 0);
    Оборудование.Вставить("Плита", 0);
    Оборудование.Вставить("Миксер", 0);

    // Массив с названиями блюд
    Блюда = Новый Массив;
    Блюда.Добавить("Пицца Маргарита");
    Блюда.Добавить("Торт Шоколадный");
    Блюда.Добавить("Салат Цезарь");
    Блюда.Добавить("Крем для торта");
    Блюда.Добавить("Пирог с яблоками");
    Блюда.Добавить("Суп-пюре");
    Блюда.Добавить("Омлет");
    Блюда.Добавить("Блины");


    // Массив с названиями оборудования
    ОборудованиеСписок = Новый Массив;
    ОборудованиеСписок.Добавить("Духовка");
    ОборудованиеСписок.Добавить("Плита");
    ОборудованиеСписок.Добавить("Миксер");

    // Генерация заказов
	
	ГСЧ = Новый ГенераторСлучайныхЧисел;
	КоличествоЗаказов = ГСЧ.СлучайноеЧисло(4,10);
    Заказы = Новый Массив;
    Для i = 1 По КоличествоЗаказов Цикл
        НовыйЗаказ = Новый Структура;
        НовыйЗаказ.Вставить("Номенклатура", Блюда[ГСЧ.СлучайноеЧисло(0, Блюда.Количество() - 1)]);
        НовыйЗаказ.Вставить("ВремяПриготовления", ГСЧ.СлучайноеЧисло(5, 60)); // Время приготовления от 5 до 60 минут
        НовыйЗаказ.Вставить("Оборудование", ОборудованиеСписок[ГСЧ.СлучайноеЧисло(0, ОборудованиеСписок.Количество() - 1)]);
        НовыйЗаказ.Вставить("Приоритет", ГСЧ.СлучайноеЧисло(1, 3)); // Приоритет от 1 до 3
        Заказы.Добавить(НовыйЗаказ);
    КонецЦикла;

начальные данные для примера к статье (получены по "Выполнить"):

Доступное оборудование:
  - Духовка
  - Плита
  - Миксер

Список блюд:
  - Пицца Маргарита
  - Торт Шоколадный
  - Салат Цезарь
  - Крем для торта
  - Пирог с яблоками
  - Суп-пюре
  - Омлет
  - Блины

Сгенерированные заказы:
  - Блюдо: Пирог с яблоками, Время приготовления: 23 мин, Оборудование: Духовка, Приоритет: 1
  - Блюдо: Торт Шоколадный, Время приготовления: 28 мин, Оборудование: Духовка, Приоритет: 2
  - Блюдо: Крем для торта, Время приготовления: 17 мин, Оборудование: Миксер, Приоритет: 3
  - Блюдо: Суп-пюре, Время приготовления: 10 мин, Оборудование: Духовка, Приоритет: 1
  - Блюдо: Блины, Время приготовления: 46 мин, Оборудование: Миксер, Приоритет: 2
  - Блюдо: Пирог с яблоками, Время приготовления: 17 мин, Оборудование: Миксер, Приоритет: 1
  - Блюдо: Торт Шоколадный, Время приготовления: 56 мин, Оборудование: Духовка, Приоритет: 1
  - Блюдо: Пицца Маргарита, Время приготовления: 12 мин, Оборудование: Плита, Приоритет: 2

 В результате выполнения обработкой алгоритма SPT получили результат:

Расписание заказов (оптимизированное):
Заказ: Крем для торта, Время начала: 18.04.2025 13:43:13, Время окончания: 18.04.2025 14:00:13, Оборудование: Миксер
Заказ: Пицца Маргарита, Время начала: 18.04.2025 13:43:13, Время окончания: 18.04.2025 13:55:13, Оборудование: Плита
Заказ: Торт Шоколадный, Время начала: 18.04.2025 13:43:13, Время окончания: 18.04.2025 14:11:13, Оборудование: Духовка
Заказ: Блины, Время начала: 18.04.2025 14:00:13, Время окончания: 18.04.2025 14:46:13, Оборудование: Миксер
Заказ: Суп-пюре, Время начала: 18.04.2025 14:11:13, Время окончания: 18.04.2025 14:21:13, Оборудование: Духовка
Заказ: Пирог с яблоками, Время начала: 18.04.2025 14:46:13, Время окончания: 18.04.2025 15:03:13, Оборудование: Миксер
Заказ: Пирог с яблоками, Время начала: 18.04.2025 14:21:13, Время окончания: 18.04.2025 14:44:13, Оборудование: Духовка
Заказ: Торт Шоколадный, Время начала: 18.04.2025 14:44:13, Время окончания: 18.04.2025 15:40:13, Оборудование: Духовка

см. скриншот с описанием "пример к статье".

Другие скриншоты - другие результаты нажатия "Выполнить" (время начала можете выставить любую, так большинство работает с 8.00 например, я же использовал ТекущаяДата()). Обработка должна работать на всех 1с 8.3 на управляемых формах.