Sciact
  • EN
  • RU

ТОЧНЫЙ АЛГОРИТМ ДЛЯ ЗАДАЧИ КАЛЕНДАРНОГО ПЛАНИРОВАНИЯ С ОГРАНИЧЕННЫМИ РЕСУРСАМИ Full article

Journal Прикладная математика и фундаментальная информатика
ISSN: 2311-4908
Output data Year: 2017, Volume: 4, Number: 1, Pages: 43–53 Pages count : 10
Tags задача календарного планирования с ограниченными ресурсами, возобновимые ресурсы, алгоритм ветвей и границ.
Authors Гончаров Е.Н. 1,2 , Мишин Д.В. 1
Affiliations
1 Институт математики им. С.Л. Соболева СО РАН
2 Новосибирский государственный университет

Abstract: Рассматривается задача календарного планирования с ограниченными ре- сурсами по критерию минимизации длины расписания. В задаче учитываются технологические ограничения предшествования работ, а также ресурсные ограничения. Все ограниченные ресурсы считаются возобновимыми. Предложена схема ветвления, основанная на представлении расписания работ в виде списка, а также использовались два алгоритма построения нижней границы. Одна из них получена из решения релаксированной задачи со складируемыми ресурсами, другая – из решения другой релаксированной задачи, в которой свойство возобновимости сохраняется, а все работы имеют единичную длительность выполнения. Численный эксперимент на примерах из библиотеки PCPLIB показал конкурентоспособность предложенного алгоритма. Результаты численных экспериментов приводятся.
Cite: Гончаров Е.Н. , Мишин Д.В.
ТОЧНЫЙ АЛГОРИТМ ДЛЯ ЗАДАЧИ КАЛЕНДАРНОГО ПЛАНИРОВАНИЯ С ОГРАНИЧЕННЫМИ РЕСУРСАМИ
Прикладная математика и фундаментальная информатика. 2017. Т.4. №1. С.43–53.
Identifiers: No identifiers
Citing: Пока нет цитирований