МИНИМИЗАЦИЯ МАКСИМАЛЬНОГО ВРЕМЕННОГО СМЕЩЕНИЯ ДЛЯ ОДНОГО ПРИБОРА В УСЛОВИЯХ НЕОПРЕДЕЛЕННОСТИ ДИРЕКТИВНЫХ СРОКОВ
Abstract
Рассматривается задача минимизации максимального временного смещения в условиях неоп-
ределенности директивных сроков при наличии ограничений предшествования и обслуживании требований одним прибором 1|prec; dj∈[ d mj in, d mj ax ]|Lmax. Формулируются необходимые и достаточные условия оптимальности расписания в детерминированном случае, а также необходимые и достаточные условия глобальной оптимальности расписания в случае с неопределенными директивными сроками, предлагается алгоритм построения глобально оптимального расписания.
About the Authors
Я. Шафранский
Объединенный институт проблем информатики НАН Беларуси
Russian Federation
Russian Federation
Д. Следнев
Lund University, Sweden
Russian Federation
Russian Federation
References
1. Lawler, E.L. Optimal sequencing of a single machine subject to precedence constraints /
2. E.L. Lawler // Management Science. – 1973. – Vol. 19, № 5. – P. 544–546.
3. Lin, Y. Necessary and sufficient conditions of optimality for some classical scheduling problems / Y. Lin, X. Wang // European Journal of Operational Research. – 2007. – Vol. 176. – P. 809–818.
4. Wald, A. Statistical Decision Functions / A. Wald. – N. Y. : Wiley, 1950.
Review
For citations:
, . Informatics. 2012;(4(36)):120-126. (In Russ.)
Views: 560
Email this article 