ПЕРЕСТАНОВКА С НАИБОЛЬШИМ ПАРАЛЛЕЛЕПИПЕДОМ УСТОЙЧИВОСТИ ДЛЯ ОБСЛУЖИВАНИЯ ТРЕБОВАНИЙ С ИНТЕРВАЛЬНЫМИ ДЛИТЕЛЬНОСТЯМИ ОПЕРАЦИЙ
Аннотация
Рассматривается задача минимизации суммы взвешенных моментов завершения обслужива-
ния требований одним прибором при условии, что для каждой длительности обслуживания требования заданы нижняя и верхняя границы возможных значений. Разрабатывается алгоритм сложности O(n log n) для построения перестановки с наибольшей размерностью и наибольшим объемом параллелепипеда устойчивости.
Об авторах
Н. Г. Егорова
Объединенный институт проблем информатики НАН Беларуси
Беларусь
Беларусь
Ю. Н. Сотсков
Объединенный институт проблем информатики НАН Беларуси
Беларусь
Беларусь
А. А. Косенков
Объединенный институт проблем информатики НАН Беларуси
Беларусь
Беларусь
Список литературы
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.
Рецензия
Для цитирования:
Егорова Н.Г., Сотсков Ю.Н., Косенков А.А. ПЕРЕСТАНОВКА С НАИБОЛЬШИМ ПАРАЛЛЕЛЕПИПЕДОМ УСТОЙЧИВОСТИ ДЛЯ ОБСЛУЖИВАНИЯ ТРЕБОВАНИЙ С ИНТЕРВАЛЬНЫМИ ДЛИТЕЛЬНОСТЯМИ ОПЕРАЦИЙ. Информатика. 2012;(4(36)):69-80.
Просмотров: 507
Послать статью по эл. почте 