Простой пример проекта с ограниченными ресурсами

Пример проекта с ограниченными ресурсами представлен в табл. 9.2, где число мероприятий n = 10 и двумя (|R| = 2) ресурсами с количествами B1 = 7 и B2 = 4.

Табл. 9.2. Проект с 10 работами и 2 ресурсами.

Ограничения предшествования, связывающие мероприятия , показаны на рис. 9.4 в виде графа «вершины-работы». График с минимальным временем выполнения показан на рис. 9.5 в виде двумерной диаграммы Гантта, на которой ось абсцисс представляет время, а ось ординат представляет использование ресурсов.

Рис. 9.4. Граф предшествования«вершины-работы».

Рис. 9.5. Диаграмма Гантта с минимальным временем выполнения проекта.

‑ ресурс 1; ‑ ресурс 2.

Задача Джонсона.

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

Пусть j=1,2,...,n - номера деталей, A(j) и B(j) , соответственно, времена обработок детали с номером j на первом и втором станках, j=1,2,...,n.

Обозначим через x(j) - время простоя второго станка непосредственно перед началом обработки детали с номером j, j=1,2,...,n.

Тогда критерием оптимальности задачи Джонсона с двумя станками станет функционал

F(x) = x(j) min.

Расписание обработки деталей на станках задается перестановкой r натуральных чисел из множества {1,2,...,n}. Если r=(1,2,...,n). то x(1)=A(1), x(2)= max {A(1)+A(2) - B(1) - x(1), 0}, ...,

x(j) = max {A(1)+...+A(n) - B(1)-...-B(n-1),...,A(1)+...+A(j) - B(1)-...-B(j-1), ...,A(1)}.

Пусть rиqдве перестановки

r=(1,2,...,n), q=(1,2,...,j-1,j+1,j,...,n).

Пусть F(r)<F(q). Тогда

max{A(1)+A(2)+...+A(j) - B(1)-B(2)-...-B(j-1), A(1)+A(2)+...+A(j+1) - B(1)-B(2)-...-B(j)}<max{A(1)+A(2)+...+A(j-1)+A(j+1) - B(1)-B(2)-...-(j-1), A(1)+A(2)+...+A(j+1) - B(1)-B(2)-... B(j-1)-B(j+1)}. (9.21)

Вычтем из левой и правой частей неравенства (9.21) величину A(1)+A(2)+...A(j+1) - B(1)-B(2)-...-B(j-1).

Получим, после несложных преобразований,

min{A(j+1), B(j)} > min{A(j), B(j+1)}. (9.22)

Итак, работа j выполняется раньше работы j+1, если выполняется условие (9.22).

Сформулируем алгоритм Джонсона построения оптимального расписания выполнения работ на двух станках:

Шаг 1. Найти минимальную величину среди A(j) и B(j), j=1,2,...,n.

Шаг 2. Если минимум достигается на A(j), то деталь с номером j ставится на обработку самой первой, если на B(j), то деталь с номером j ставится на обработку последней, деталь с номером j исключается из рассмотрения, и процесс построения расписания продолжается с шага 1.

Построенные расписания наглядно отображаются с помощью графиков Гантта.

[1] Так, к задачам теории расписаний часто относят только задачи упорядочения.

[2] См. обзор по моделям расписаний ‑ Schaerf A. A survey of automated timetabling // Artificial Intelligence Review. – 1999. ‑ 13(2). – P. 87-127.

[3] Goltz, H.-J., Matzke, D.: University Timetabling Using Constraint Logic Programming // In: Gupta G. (ed.): Practical Aspects of Declarative Languages. LNCS, Vol. 1551. Springer-Verlag, Berlin Heidelberg New York (1999). – P. 320-334

[4] Even S., Itai A., Shamir A. On the complexity of timetabling and multicommodity flow problems // SIAM J. Comput. – 1976. – 5. – P. 691–703.

[5] Blazewicz J., Lenstra J.K., and Rinnoy Kan A.H.G. Scheduling subject to resource constraints: Classfication and complexity // Discrete Applied Mathematics. - 1983. - Vol. 5, N 1 — P. 11-24.

[6] Kolish, R. and Padman, R. An Integrated Survey of Deterministic Project Scheduling // OMEGA Jour. of Sched. – 2001. - Vol. 29. - P. 249-272.

[7] Herroelen W.S., De Reyck B. and Demeulemeester E.L. Resource-Constrained Project Scheduling: A Survey of Recent Developments // Соmр. and Oper. Res .- 1998. - Vol. 25. - P. 279-302.

[8] Гимади Э.Х. О некоторых математических моделях и методах планирования крупномасштабных проектов // Модели и методы оптимизации.— Новосибирск: Наука, 1988.— С. 89-115.

[9] Brucker P., Drexl A., Mohring R., Neumann K. and Pesch E. Resource-constrained project scheduling: Notation, classification, models, and methods // Eur. Jour, of Oper. Res .- 1999. - Vol. 112. - P. 3-41.

[10] Lerda-Olberg S. Bibliography on Network-Based Project Planning and Control Techniques: 1962-1965 // Oper. Res. - 1966. - Vol. 15 — P. 925-931.

[11] по имени американского математика С.М. Джонсона, изучавшего такие задачи.