Рішення деяких задач теорії розкладів методами опуклої оптимізації
DOI:
https://doi.org/10.15587/2312-8372.2017.108909Ключові слова:
теорія розкладів, опукла оптимізація, метод точної квадратичної регуляризаціїАнотація
Досліджено конвеєрну задачу теорії розкладів для (flow shop) зі стандартними обмеженнями. Шляхом деяких перетворень ці обмеження зведені до квадратичних форм змінних задачі. Показано, що будь-яка задача теорії розкладів для конвеєрної системи машин зводиться до задачі мінімуму лінійної функції з набором лінійних і квадратичних обмежень, тобто до задачі опуклої оптимізації. Розглянуто модельний приклад та методом точної квадратичної регуляризації отримано оптимальний розклад.
Посилання
- Coffman, E. G. (1976). Computer and Job-shop Scheduling Theory. John Wiley&Sons, 312.
- Conway, R. W., Maxwell, W. L., Miller, L. W. (1967). Theory of Scheduling. Addison-Wesley Educational Publishers Inc., 294.
- Lazarev, A. A., Gafarov, E. R. (2011). Teoriia raspisanii zadachi i algoritmy. Moscow: Nauka, 222.
- 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
- 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.
- 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.
- 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
- 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.
- Kosolap, А. I. (2013). Metody global'noi optimizatsii. Dnipro: Nauka i obrazovanie, 316.
- Boyd, S., Vandenberghe, L. (2004). Convex Optimization. Cambridge University Press, 716. doi:10.1017/cbo9780511804441
- Nesterov, Yu. E. (2010). Metody vypukloi optimizatsii. Moscow: MTsNMO, 281.
- Kosolap, A. (2009). Method of quadratic relaxation for solution of nonconvex quadratic program. Remagen, Germany, 20.
##submission.downloads##
Опубліковано
Як цитувати
Номер
Розділ
Ліцензія
Авторське право (c) 2017 Anton Nesterenko, Anatolii Kosolap
![Creative Commons License](http://i.creativecommons.org/l/by/4.0/88x31.png)
Ця робота ліцензується відповідно до Creative Commons Attribution 4.0 International License.
Закріплення та умови передачі авторських прав (ідентифікація авторства) здійснюється у Ліцензійному договорі. Зокрема, автори залишають за собою право на авторство свого рукопису та передають журналу право першої публікації цієї роботи на умовах ліцензії Creative Commons CC BY. При цьому вони мають право укладати самостійно додаткові угоди, що стосуються неексклюзивного поширення роботи у тому вигляді, в якому вона була опублікована цим журналом, але за умови збереження посилання на першу публікацію статті в цьому журналі.