4551
правка
Минимальное время завершения для взвешенной системы: различия между версиями
Перейти к навигации
Перейти к поиску
Минимальное время завершения для взвешенной системы (посмотреть исходный код)
Версия от 15:02, 22 сентября 2016
, 22 сентября 2016→Открытые вопросы
Irina (обсуждение | вклад) м (→Применение) |
Irina (обсуждение | вклад) |
||
| Строка 45: | Строка 45: | ||
== Открытые вопросы == | == Открытые вопросы == | ||
Одна из основных нерешенных задач в этой области заключается в улучшении коэффициентов аппроксимации для планирования заданий с отношениями предшествования на несвязанных или связанных машинах. Следующие задачи заслуживают отдельного упоминания. Наилучшим известным решением задачи 1 jprecj P wjCj является алгоритм 2-аппроксимации Холла и др. [8]; улучшение этого коэффициента является главным открытым вопросом теории планирования. Задача _R|prec| ^ wjCj, в которой отношения предшествования формируют произвольный ациклический граф, также представляет высокую важность: единственные результаты были получены для случая, когда отношения предшествования формируют цепи [6] или деревья [10]. | |||
Также неисследованным остается направление неаппроксимируемости – имеется немало серьезных пробелов между известными гарантиями аппроксимации и коэффициентами сложности для различных классов задач. Например, известно, что задачи Rj j P wj Cj и R j rj j P wj Cj являются сложными для аппроксимации, однако лучшие известные алгоритмы, предложенные Скутеллой [11], имеют коэффициента аппроксимации 3/2 и 2, соответственно. Устранение этих пробелов представляет собой важную задачу. | |||
== См. также == | |||
* ''[[Минимизация продолжительности потока]] | |||
* ''[[Списочное планирование]] | |||
* ''[[Минимальная продолжительность потока]] | |||
* ''[[Минимальный период обработки на несвязанных машинах]] | |||
== Литература == | |||
1. Afrati, F.N., Bampis, E., Chekuri, C., Karger, D.R., Kenyon, C., Khanna, S., Milis, I., Queyranne, M., Skutella, M., Stein, C., Sviridenko, M.: Approximation schemes for minimizing average weighted completion time with release dates. In: Proc. of Foundations of Computer Science, pp. 32-44 (1999) | |||
2. Bruno, J.L., Coffman, E.G., Sethi, R.: Scheduling independent tasks to reduce mean finishing time. Commun. ACM 17, 382-387(1974) | |||
3. Chekuri, C., Khanna, S.: Approximation algorithms for minimizing weighted completion time. In: J. Y-T. Leung (eds.) Handbook of Scheduling: Algorithms, Models, and Performance Analysis. CRC Press, Boca Raton (2004) | |||
4. Chekuri, C., Motwani, R., Natarajan, B., Stein, C.: Approximation techniques for average completion time scheduling. SIAM J.Comput.31(1), 146-166(2001) | |||
5. Goemans, M., Queyranne, M., Schulz, A., Skutella, M., Wang, Y.: Single machine scheduling with release dates. SIAM J. Discret. Math. 15,165-192(2002) | |||
6. Goldberg, L.A., Paterson, M., Srinivasan, A., Sweedyk, E.: Better approximation guarantees for job-shop scheduling. SIAM J. Discret. Math. 14,67-92 (2001) | |||
7. Graham, R.L., Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G.: Optimization and approximation in deterministic sequencing and scheduling: a survey. Ann. Discret. Math. 5,287-326 (1979) | |||
8. Hall, L.A., Schulz, A.S., Shmoys, D.B., Wein, J.: Scheduling to minimize average completion time: off-line and on-line approximation algorithms. Math. Oper. Res. 22(3), 513-544 (1997) | |||
9. Horn, W.: Minimizing average flow time with parallel machines. Oper. Res. 21,846-847 (1973) | |||
10. Kumar, V.S.A., Marathe, M.V., Parthasarathy, S., Srinivasan, A.: Scheduling on unrelated machines under tree-like precedence constraints. In: APPROX-RANDOM, pp. 146-157(2005) | |||
11. Skutella, M.: Convex quadratic and semi-definite relaxations in scheduling. J.ACM 46(2), 206-242 (2001) | |||
12. Skutella, M., Woeginger, G.J.: A PTAS for minimizing the weighted sum of job completion times on parallel machines. | |||
In: Proc. of 31st Annual ACM Symposium on Theory of Computing (STOC'99), pp. 400^07 (1999) | |||
13. Smith, W.E.: Various optimizers for single-stage production. Nav. Res. Log. Q. 3, pp. 59-66 (1956) | |||