Рішення деяких задач теорії розкладів методами опуклої оптимізації

Автор(и)

  • Anatolii Kosolap ДВНЗ «Український державний хіміко-технологічний університет», пр. Гагаріна, 8, м. Дніпро, Україна, 49005, Україна https://orcid.org/0000-0001-7338-6707
  • Anton Nesterenko ДВНЗ «Український державний хіміко-технологічний університет», пр. Гагаріна, 8, м. Дніпро, Україна, 49005, Україна https://orcid.org/0000-0002-0620-3963

DOI:

https://doi.org/10.15587/2312-8372.2017.108909

Ключові слова:

теорія розкладів, опукла оптимізація, метод точної квадратичної регуляризації

Анотація

Досліджено конвеєрну задачу теорії розкладів для (flow shop) зі стандартними обмеженнями. Шляхом деяких перетворень ці обмеження зведені до квадратичних форм змінних задачі. Показано, що будь-яка задача теорії розкладів для конвеєрної системи машин зводиться до задачі мінімуму лінійної функції з набором лінійних і квадратичних обмежень, тобто до задачі опуклої оптимізації. Розглянуто модельний приклад та методом точної квадратичної регуляризації отримано оптимальний розклад.

Біографії авторів

Anatolii Kosolap, ДВНЗ «Український державний хіміко-технологічний університет», пр. Гагаріна, 8, м. Дніпро, Україна, 49005

Доктор фізико-математичних наук, професор, завідувач кафедри

Кафедра спеціалізованих комп'ютерних систем

Anton Nesterenko, ДВНЗ «Український державний хіміко-технологічний університет», пр. Гагаріна, 8, м. Дніпро, Україна, 49005

Аспірант

Кафедра спеціалізованих комп'ютерних систем

Посилання

  1. Coffman, E. G. (1976). Computer and Job-shop Scheduling Theory. John Wiley&Sons, 312.
  2. Conway, R. W., Maxwell, W. L., Miller, L. W. (1967). Theory of Scheduling. Addison-Wesley Educational Publishers Inc., 294.
  3. Lazarev, A. A., Gafarov, E. R. (2011). Teoriia raspisanii zadachi i algoritmy. Moscow: Nauka, 222.
  4. Wang, J.-B. (2009). Flow shop scheduling with deteriorating jobs under dominating machines to minimize makespan. The International Journal of Advanced Manufacturing Technology, 48 (5-8), 719–723. doi:10.1007/s00170-009-2314-2
  5. Prilutsky, M. Kh., Vlasov, S. Ye. (2005). Multi-stage tasks of the scheduling theory with alternative choice of the works fulfilment. Sistemy upravleniia i informatsionnye tehnologii, 2, 44–48.
  6. Prilutsky, M. Kh., Vlasov, V. S. (2008). The method of paths and boundaries with heuristic evaluation for a conveyor problem of scheduling theory. Vestnik of Lobachevsky State University of Nizhni Novgorod, 3, 147–153.
  7. Emmons, H., Vairaktarakis, G. (2013). Flow Shop Scheduling. International Series in Operations Research&Management Science. Springer US, 334. doi:10.1007/978-1-4614-5152-5
  8. Anichkin, A. S., Semenov, V. A. (2014). A survey of emerging models and methods of scheduling. Proceedings of the Institute for System Programming of the RAS, 26 (3), 5–50.
  9. Kosolap, А. I. (2013). Metody global'noi optimizatsii. Dnipro: Nauka i obrazovanie, 316.
  10. Boyd, S., Vandenberghe, L. (2004). Convex Optimization. Cambridge University Press, 716. doi:10.1017/cbo9780511804441
  11. Nesterov, Yu. E. (2010). Metody vypukloi optimizatsii. Moscow: MTsNMO, 281.
  12. Kosolap, A. (2009). Method of quadratic relaxation for solution of nonconvex quadratic program. Remagen, Germany, 20.

##submission.downloads##

Опубліковано

2017-07-25

Як цитувати

Kosolap, A., & Nesterenko, A. (2017). Рішення деяких задач теорії розкладів методами опуклої оптимізації. Technology Audit and Production Reserves, 4(2(36), 65–69. https://doi.org/10.15587/2312-8372.2017.108909

Номер

Том 4 № 2(36) (2017): Інформаційно-керуючі системи

Розділ

Математичне моделювання: Оригінальне дослідження

Ліцензія

Авторське право (c) 2017 Anton Nesterenko, Anatolii Kosolap

Creative Commons License

Ця робота ліцензується відповідно до Creative Commons Attribution 4.0 International License.

Закріплення та умови передачі авторських прав (ідентифікація авторства) здійснюється у Ліцензійному договорі. Зокрема, автори залишають за собою право на авторство свого рукопису та передають журналу право першої публікації цієї роботи на умовах ліцензії Creative Commons CC BY. При цьому вони мають право укладати самостійно додаткові угоди, що стосуються неексклюзивного поширення роботи у тому вигляді, в якому вона була опублікована цим журналом, але за умови збереження посилання на першу публікацію статті в цьому журналі.