Экономический анализ в задачах теории расписаний

Теория расписаний (scheduling theory) – это научная дисциплина, посвященная разработке оптимизационных методов оперативно-календарного планирования. Задачи теории расписаний - один из видов задач исследования операций, объединяемых в классе задач упорядочения.

Системы оперативно – календарного планирования современных производств строятся на достижениях «теории расписаний», занимающейся исследованиями детерминированных обслуживающих систем на предмет оптимизации расписаний их функционирования. Примеры таких систем: цех, участок, на рабочих местах которых осуществляется выполнение отдельных операций или бизнес-процессов или ВУЗ, где преподаватели обучают студентов и т.д.

В любом случае имеется конечное множество требований (деталей, клиентов, групп студентов и т.д.) N = {1,2,…n}и конечное множество приборов (станков, меастеров, преподавателей и т.д.) M = { 1,2,…m}. Предполагается, что i – е требование на каждой стадии его обслуживания q (например, на каждой операции технологического процесса) может быть обслужено любым из приборов LϵM (но не более, чем одним одновременно). Предполагается также, что каждый прибор одновременно может обслуживать не более одного требования.

В теории расписаний рассматриваются различные системы обслуживания:

• системы поточного типа, в которых каждое требование iϵN сначала обслуживается приборами первой группы, затем второй группы и т.д. пока не будет обслужено приборами последней r – ой группы;

• системы с различными порядками (маршрутами) прохождения приборов требованиями и т.д.

В частности, в последних системах с последовательными приборами для каждого требования iϵN задается своя, специфическая для этого требования последовательность Lⁱ = (Lⁱ₁, Lⁱ_2, …Lⁱ_n)_, его обслуживания (технологический процесс). Требование i сначала обслуживается прибором Lⁱ₁, затем Lⁱ₂и т.д. пока не будет обслужено прибором Lⁱ_n. Последовательности обслуживания могут быть различными для разных требований и могут содержать повторения.

В любом случае, если требование i на стадии q должно или может быть обслужено прибором L⁼ Lⁱ_q, то предполагается заданной длительность t_iL ≥0 его обслуживания прибором. Запись t_iL =0, как привило, означает, что по условию задачи требование i на стадии q прибором L не обслуживается.

Наряду с величинами t_iL могут быть заданы также: момент d_i ≥0 поступления требования i в систему; директивный срок D_i ≥0, к которому необходимо завершить обслуживание требования.

Процесс функционирования обслуживающей системы может быть описан путем задания расписания (календарного плана, временного графика и т.п.). Расписание – некоторая совокупность указаний относительно того, какие именно требования какими именно приборами обслуживаются в каждый момент времени. Расписание рассматривается как совокупность {S₁(t), S₂(t), … S_m(t)} кусочно–постоянных непрерывных слева функций, каждая из которых задана на интервале 0≤t≤∞ и принимает значения 0, 1, …, n. Если S_L(t^/)=i≠0 (здесь i – номер требования), то в момент времени t^/ прибор L обслуживает требование i. Если S_L(t^/)=0, то в момент времени t^/ прибор L простаивает.

В теории расписаний качество расписания во многих случаях оценивают следующим образом. Каждое (допустимое) расписание S однозначно определяет вектор моментов завершения обслуживания требований. Задается некоторая действительная неубывающая по каждой из переменных функция F (x)=F (x₁, x₂, …x_n). Качество расписания S оценивается значением этой функции при x= ṫ (S). Из двух расписаний лучшим считается то, которому соответствует меньшее значение F (x). Расписание, которому соответствует наименьшее значение F (x) (среди всех допустимых расписаний), называется оптимальным. В частности, при построении оптимального по быстродействию расписания

F (ṫ (S))= ṫ_max (S), где ṫ_max (S) = max {ṫ_i (S) },где i=1,2,…,n

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

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

• длительность производственного цикла изготовления партии деталей (выполнения заказа)

• время простоя каждого рабочего места

• время пролеживания партии деталей (заказа)

• длительность совокупного производственного цикла изготовления партий деталей (заказа)

Эти показатели позволяют выявить :

• наиболее загруженные рабочие места (к которым нужно относится с особым вниманием) по их коэффициенту загрузки;

• наиболее пролеживающие в процессе производства партии деталей (заказы) по коэффициент пролеживания;

• другие параметры.