journal.isu.ru

Начальная страница

Конечная страница

УДК

Раздел
     

Файл
Скачать Изменить файл

Название RU

Авторы RU

Аннотация RU
<p>Рассматривается NP-трудная в сильном смысле задача календарного планирования с ограничениями на ресурсы нескладируемого типа и порядок выполнения работ. Особенностью постановки является то, что интенсивности потребления ресурсов работами могут меняться в процессе их выполнения и наличие ресурсов зависит от момента времени. Доказано, что если ширина заданного на множестве работ частичного порядка ограничена константой, то задача псевдополиномиально разрешима, являясь при этом NP-трудной. Найдены новые полиномиально разрешимые частные случаи.</p>

Ключевые слова RU

Литература RU
1. Айгнер М. Комбинаторная теория / М. Айгнер. – М. : Мир, 1982. – 558 с. 2. Гимади Э. Х. Полиномиальная разрешимость задач календарного планирования со складируемыми ресурсами и директивными сроками / Э. Х. Гимади, В. В. Залюбовский, С. В. Севастьянов // Дискрет. анализ и исслед. операций. Сер. 2. – 2000. – Т. 7, № 1. – С. 9–34. 3. Еремеев А. В. Календарное планирование производства с непрерывным поступлением сырья / А. В. Еремеев, Ю. В. Коваленко // Российская конференция «Дискретная оптимизация и исследование операций»: материалы конференции. – Новосибирск : Изд-во Ин-та математики, 2010. – С. 138. 4. Коваленко Ю. В. Решение задачи календарного планирования производства с непрерывным поступлением сырья / Ю. В. Коваленко // «Молодежь третьего тысячелетия» : XXXIV регион. науч.-практ. студ. Конф. : сб. ст. секции «Физико-математические науки». – Омск : Изд-во ОмГУ, 2010. – С. 21–24. 5. Коваленко Ю. В. О задаче календарного планирования с возобновимым ресурсом / Ю. В. Коваленко // Автомат. и телемех. – 2012. – Вып. 6. – С. 140–153. 6. Алгоритмы: построение и анализ / Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн. – М. : Вильямс, 2005. – 1296 с. 7. Кочетов Ю. А. Новые жадные эвристики для задачи календарного планирования с ограниченными ресурсами / Ю. А. Кочетов, А. А.Столяр // Дискрет. анализ и исслед. операций. Сер. 2. – 2005. – Т. 12, № 1. – С. 12–36. 8. Сервах В. В. Эффективно разрешимый случай задачи календарного планирования с возобновимыми ресурсами / В. В. Сервах // Дискрет. анализ и исслед. операций. Сер. 2. – 2000. – Т. 7, № 1. – С. 75–82. 9. Bell C. E. A new heuristic solution method in resource constrained project scheduling / C. E. Bell, J. Han // Naval Res. Logistics. – 1991. – Vol. 38. – P. 315-331. 10. A branch and bound algorithm for the resource-constrained project scheduling problem / P. Brucker, S. Knust, A. Schoo, O. Thiele // Eur. J. Oper. Res. – 1998. – Vol. 107. – P. 272–288. 11. Brucker P., Kramer A. Polynomial algorithms for resource constrained and multiprocessor task scheduling problems / P. Brucker, A. Kramer // Eur. J. Oper. Res. –1996. – Vol. 90, N 2. – P. 214–226. 12. Christofides N. Project scheduling with resource constraints: a branch and bound approach / N. Christofides, R. Alvarez-Valdes, J. M. Tamarit // European J. Oper. Res. – 1987. – Vol. 29. – P. 262–273. 13. Scheduling using continuous-time formulations: technical report / J. Kallrath, A. Eremeev, P. Borisovsky, J. Kovalenko. – Ludwigshafen : BASF SE, Scientifc Computing, 2010. – 337 p. 14. Pritsker A. A. B. Multiproject scheduling with limited resources: a zero-one programming approach // A. A. B. Pritsker, L. J. Watters, P. M. Wolfe // Management Sci. – 1969. – Vol. 16. – P. 93–107. 15. Servakh V. V. A fully polynomial time approximation scheme for two project scheduling problems / V. V. Servakh, T. A. Shcherbinina // Inform. Control Problems in Manufact.: A Proc. of 12th IFAC Intern. Symp. / ed. by Dolgui A., G. Morel, C. E. Pereira. – Saint-Etienne : Elsevier Science, 2006. – Vol. 3. – P. 129 – 134. 16. Sotskov Y. N. NP-hardness of shop-scheduling problems with three jobs / Y. N. Sotskov, N. V. Shakhlevich // Discrete Appl. Math. –1995. – Vol. 59, N 3. – P. 237–266.

Название EN

Авторы EN

Аннотация EN
<p>We consider a strongly NP-hard project scheduling problem with nonaccumulative resources and sequence constraints. A distinctive feature of the formulation is that the rate of resource consumption by a task may change in duration of the task, and the resource availability depends on time. The problem is proved to be pseudo-polynomially solvable if the width of the partial order is bounded by a constant, being NP-hard. New polynomially solvable case of the problem is found.</p>

Ключевые слова EN

Литература EN
1. Aygner M. Сombinatory theory. M., World, 1982, 558 p. 2. Gimadi E.Kh., Zalyubovskii V.V., Sevast’yanov S.V. Polynomial Solvability of Project Scheduling Problems with Accumulative Resources and Directive Deadlines. Diskretn. Anal. Issled. Oper. Ser. 2., 2000, vol. 7, no. 1, pp. 9-34. 3. Eremeev A.V., Kovalenko J.V. Project Scheduling with Continuous Consumption of Raw Material in Production. Book of Abstracts of Discrete Analysis and Oper. Res. Conf., Novosibirsk, Institute of Mathematics, 2010, p. 138. 4. Kovalenko J.V. Solving of the Project Scheduling Problem with Continuous Consumption of Raw Material in Production. "Youth of the Third Millennium": The XXXIV Regional Scientific and Practical Student’s Conference: CollectedArticles of Section "Physical and Mathematical Sciences", Omsk, OmSU, 2010, pp. 21-24. 5. Kovalenko J.V. On Project Scheduling Problem with Renewable Resource. Automation and Remote control, 2012, no. 6, pp. 140-153. 6. Kormen T., Leyzerson H., Rivest R., Stein K. Algorithms: Construction and Analysis. M., Williams, 2005, 1296 p. 7. Kochetov Yu.A., Stolyar A.A. New Greedy Heuristics for the Project Scheduling Problem with Limited Resources. Diskretn. Anal. Issled. Oper. Ser. 2., 2005, vol. 12, no. 1, pp. 12-36. 8. Servakh V.V. An Efficiently Solvable Case of the Project Scheduling Problem with renewable resources. Diskretn. Anal. Issled. Oper. Ser. 2., 2000, vol. 7, no. 1, pp. 75-82. 9. Bell C.E., Han J. A New Heuristic Solution Method in Resource Constrained Project Scheduling. Naval Res. Logistics, 1991, vol. 38, pp. 315-331. 10. Brucker P., Knust S., Schoo A., Thiele O. A Branch and Bound Algorithm for the Resource-Constrained Project Scheduling Problem. Eur. J. Oper. Res., 1998, vol. 107, pp. 272-288. 11. Brucker P., Kr¨amer A. Polynomial Algorithms for Resource Constrained and Multiprocessor Task Scheduling Problems. Eur. J. Oper. Res., 1996, vol. 90, no. 2, pp. 214-226. 12. Christofides N., Alvarez-Valdes R., Tamarit J. M. Project Scheduling with Resource Constraints: a Branch and Bound Approach. European J. Oper. Res., 1987, vol. 29, pp. 262-273. 13. Kallrath J., Eremeev A., Borisovsky P., Kovalenko J. Scheduling Using Continuous-Time Formulations: Technical Report. Ludwigshafen, BASF SE, Scientifc Computing, 2010, 337 p. 14. Pritsker A.A.B., Watters L.J., Wolfe P.M. Multiproject Scheduling with Limited Resources: a Zero-One Programming Approach. Management Sci., 1969, vol. 16, pp. 93-107. 15. Servakh V.V., Shcherbinina T.A. A Flly Polynomial Time Approximation Scheme for Two Project Scheduling Problems. Inform. Control Problems in Manufact.: A Proc. of 12th IFAC Intern. Symp., eds. By Dolgui A., Morel G., Pereira C.E.,Saint-Etienne, Elsevier Science, 2006, vol. 3, pp. 129-134. 16. Sotskov Y.N., Shakhlevich N.V. NP-hardness of Shop-Scheduling Problems with Three Jobs. Discrete Appl. Math., 1995, vol. 59, no. 3, pp. 237-266.