ПЕРЕСТАНОВКА С НАИБОЛЬШИМ ПАРАЛЛЕЛЕПИПЕДОМ УСТОЙЧИВОСТИ ДЛЯ ОБСЛУЖИВАНИЯ ТРЕБОВАНИЙ С ИНТЕРВАЛЬНЫМИ ДЛИТЕЛЬНОСТЯМИ ОПЕРАЦИЙ
Abstract
Рассматривается задача минимизации суммы взвешенных моментов завершения обслужива-
ния требований одним прибором при условии, что для каждой длительности обслуживания требования заданы нижняя и верхняя границы возможных значений. Разрабатывается алгоритм сложности O(n log n) для построения перестановки с наибольшей размерностью и наибольшим объемом параллелепипеда устойчивости.
About the Authors
Н. Егорова
Объединенный институт проблем информатики НАН Беларуси
Belarus
Belarus
Ю. Сотсков
Объединенный институт проблем информатики НАН Беларуси
Belarus
Belarus
А. Косенков
Объединенный институт проблем информатики НАН Беларуси
Belarus
Belarus
References
1. Sequencing and scheduling: Algorithms and complexity / E.L. Lawler [et al.] // Handbooks in Operations Research and Management Science. Logistics of Production and Inventory. – New York, 1993. – P. 445–522.
2. Егорова, Н.Г. Минимизация суммы взвешенных моментов завершения обслуживания требований с интервальными длительностями / Н.Г. Егорова, Ю.Н. Сотсков // Информатика. – 2008. – № 3. – С. 5–16.
3. Smith, W.E. Various Optimizers for Single-Stage Production / W.E. Smith // Naval Research
4. and Logistics Quarterly. – 1956. – Vol. 3, № 1. – Р. 59–66.
5. Сотсков, Ю.Н. Теория расписаний. Системы с неопределенными числовыми парамет
6. рами / Ю.Н. Сотсков, Н.Ю. Сотскова. – Минск : ОИПИ НАН Беларуси, 2004. – 290 c.
7. Sotskov, Yu.N. Minimizing total weighted flow time under uncertainty using dominance and a stability box / Yu.N. Sotskov, T.-C. Lai // Computers & Operations Research. – 2012. – Vol. 39. – P. 1271–1289.
8. Модели и комплекс программ для планирования рабочего времени / Ю.Н. Сотсков
9. [и др.] // Информатика. – 2007. – № 4. – С. 23–36.
10. Emelichev, V.A. Multicriterial investment problem in conditions of uncertainty and risk /
11. V.A. Emelichev, V.V. Korotkov, K.G. Kuz’min // Journal of Computer and Systems Sciences International. – 2011. – Vol. 50, № 6. – P. 1011–1018.
12. Емеличев, В.A. О радиусе устойчивости эффективного решения векторной квадратичной булевой задачи на узкие места / В.А. Емеличев, В.В. Коротков // Дискретный анализ и исследование операций. – 2011. – Т. 18, № 6. – C. 3–16.
13. The stability box in interval data for minimizing the sum of weighted completion times /
14. Yu.N. Sotskov [et al.]// SIMULTECH 2011: 1st International Conf. on Simulation and Modeling Methodologies. Technologies and Applications, Noordwijkerhout, The Netherlands, 29–31 July 2011. – Portugal : SciTePress – Science and Technology Publications, 2011. – Р. 14–23.
15. Егорова, Н.Г. Перестановка с наибольшим параллелепипедом устойчивости для об
16. служивания требований с неопределенными длительностями операций / Н.Г. Егорова,
17. Ю.Н. Сотсков // Пятая Междунар. науч. конф. «Танаевские чтения». – Минск : ОИПИ НАН Беларуси, 2012. – С. 24–29.
Review
For citations:
, , . Informatics. 2012;(4(36)):69-80. (In Russ.)
Views: 509
Email this article 