ИСТИНА

Среди прикладных задач теории расписаний встречаются такие, что критерий качества и, следовательно, целевая функция не определены, и среди множества допустимых расписаний эксперты выделяют наиболее «качественные», опираясь на опыт и собственное видение процесса, для которого необходимо построить расписание. Для применения методов теории расписаний возникает необходимость построить целевую функцию таким образом, чтобы оптимальное, согласно этой целевой функции, расписание удовлетворяло накладываемым на него ограничениям и являлось достаточно «качественным» по мнению экспертов. Для построения целевой функции в таком случае предлагается использовать расписания, построенные на основе экспертных оценок. Необходимо учитывать, что задача аппроксимации целевой функции возникает как подзадача в процессе автоматизации составления расписания. По этой причине алгоритм аппроксимации должен быть достаточно быстродейственным по сравнению с необходимой частотой составления расписания, а показателем качества алгоритма аппроксимации является качество расписания, получаемого с помощью построенной целевой функции. Рассматривается линейная аппроксимация для одноприборной задачи теории расписаний: предполагается, что существует линейная относительно моментов окончания обслуживания требований целевая функция, и расписания, построенные «вручную», являются оптимальными относительно этой целевой функции. Аппроксимируются неизвестные значения весовых коэффициентов целевой функции, что сводится, как будет показано, к решению системы линейных неравенств относительно этих коэффициентов. В данной работе описывается алгоритм аппроксимации весовых коэффициентов для случая одновременно поступающих на прибор требований. Матрица системы линейных неравенств в этом случае, как будет показано, приобретает специальный вид: она является разреженной (большинство элементов являются нулевыми) и содержит значительное число зависимых неравенств, в связи с чем метод решения прежде всего основывается на исключении зависимых неравенств из системы. Используются и некоторые общие свойства линейных систем неравенств.