Статья
A metric approach for scheduling problems with minimizing the maximum penalty
В работе рассмотрена модификация алгоритмов динамического программирования(АДП), называемых графическими алгоритмами (ГА). Для задачи РАНЕЦ показано, что временная сложность ГА ниже, чем у стандартных АДП. Средняя продолжительность работы ГА также зачастую существенно меньше. ГА также могут решать примеры большой размерности и примеры с нецелочисленными параметрами. В статье представлены параллельные реализации алгоритма для OpenCL и MPI. В ходе экспериментов было замечено, что "сложные" примеры задачи РАНЕЦ имеют параметры p_j = k w_j, где p_j и w_j - ценность и вес предметов.
Рассматривается графическая реализация метода динамического программирования. Идея метода показана на примерах решения задач разбиение и рюкзака. Проведен сравнительный анализ предлагаемого метода с известными алгоритмами решения этих задач.
В настоящее время прогресс в развитии современных вычислительных сетей требует глубокого анализа разнообразных аспектов их организации, включая такую современную область как гарантоспособность. В последнее время эта область науки очень активно развивается. Вводятся различные количественные и качественные критерии её оценки. Настоящая монография, состоящая из 14 глав, посвящена важнейшим вопросам современных вычислительных систем. Рассматривается широкий спектр проблем, охватывающих надёжность аппаратных платформ и программного обеспечения. Среди обсуждаемых проблем вопросы безопасности, высокой степени готовности и надёжности распределенных систем. В частности, 10 глава посвящена вопросам организации гарантоспособных вычислений в грид на основе экономических принципов.
Работа посвящена экономическим моделям планирования потоков заданий в распределенных вычислительных средах с неотчуждаемыми ресурсами. Модели строятся на принципах так называемого справедливого разделения ресурсов между их владельцами и независимыми пользователями, входящими в виртуальную организацию. Планирование выполняется циклично в соответствии с динамикой загрузки и освобождения вычислительных узлов. Планы выполнения пакетов заданий формируются с использованием методов динамического программирования и прогноза состояния ресурсов на основе локальных расписаний, представляющих собой динамично обновляемые списки слотов. Указанные выше аспекты составляют главное отличие предлагаемых экономических моделей планирования потоков заданий от известных подходов.
В работе исследуются алгоритмы поиска и отбора слотов для экономических моделей планирования пакетов независимых заданий в распределенных вычислительных средах с неотчуждаемыми ресурсами. В известных алгоритмах и подходах предполагается поиск лишь одного подходящего по ресурсам, времени и стоимости набора слотов. В данной работе предлагаются и сравниваются между собой два алгоритма выбора альтернативных наборов слотов. Наличие альтернатив повышает эффективность планирования системы заданий в целом. Оба алгоритма характеризуются линейной сложностью. Приводятся результаты экспериментального исследования алгоритмов в задачах планирования с различными критериями эффективности.
Рассматривается задача построения расписания проекта с учётом ограничений на ресурсы (RCPSP) и её частные случаи. Проведён сравнительный анализ известных нижних оценок целевой функции - минимизации общего времени выполнения проекта. Выдвинута гипотеза, что для задачи RCPSP без прерываний в обслуживании требований оптимальное значение целевой функции не более чем в два раза больше оптимального значения целевой функции соответствующей задачи с прерываниями. Представлены доказательства гипотезы для случаев задачи с параллельными машинами и без отношений предшествования.
Рассматривается задача теории расписаний минимизации суммарного взвешенного момента окончания для одного прибора с возможностью прерывания обслуживания требований. Продолжительности обслуживания всех требований одинаковы. На текущий момент данная задача является открытой, т.е. не известен полиномиальный алгоритм ее решения и не доказано, что она является NP-трудной. Приводятся свойства оптимальных расписаний данной задачи.