Optimization in problems of schedule theory with a square criterion

Authors

  • A. I. Kosolap Department of specialized computer systems, State Higher Education Establishment “Ukrainian State University of Chemical Technology”, 40, Naberezhna Peremogy str., Dnipropetrovsk 49005, Ukraine
  • A. N. Nesterenko Department of specialized computer systems, State Higher Education Establishment “Ukrainian State University of Chemical Technology”, 68, Zaporiske Shose str., Dnipropetrovsk 49041, Ukraine

Keywords:

scheduling theory, convex optimization, global optimization, method of exact quadratic regularization

Abstract

Goal. The paper considers quadratic optimization models for the problems of scheduling theory that arise in the study of conveyor machines system (flow shop) with standard constraints. The obtained quadratic models are multiextremal. The aim of the study is to develop effective methods for constructing optimal schedules using quadratic regularization. Methodology. Using quadratic regularization, the constraints of the problem of conveyor machines system are reduced to maximization of Euclidian vector norm at the convex set. We used the method of exact quadratic regularization, which allows us to find global solutions in multiextremal problems. Results. It is shown that any problem of scheduling theory for the conveyor machines system can be reduces to the problem of maximizing a quadratic function with a set of linear and quadratic constraints. A method of exact quadratic regularization with a linear coordinate shift was used to find the global extremum. An algorithm for solving this class of problems was developed. Scientific novelty. Conducted transformation of the problem of conveyor machines system allows solving all problems of this type by methods of convex optimization and dichotomy, rather than developing algorithms for separate classes of scheduling theory problems. It is shown that the system the multiextremal convex optimization problem can be reduced to a one-extremal one using a linear coordinate shift. Practical significance. The developed methodology for solving the problems of scheduling theory for conveyor machines system allow obtaining optimal schedules for processing of the tasks. This technique allows to minimize processing time of operations in technological processes.

Author Biographies

A. I. Kosolap, Department of specialized computer systems, State Higher Education Establishment “Ukrainian State University of Chemical Technology”, 40, Naberezhna Peremogy str., Dnipropetrovsk 49005

Dr. Sc. (Phys.-Math.), Prof.

A. N. Nesterenko, Department of specialized computer systems, State Higher Education Establishment “Ukrainian State University of Chemical Technology”, 68, Zaporiske Shose str., Dnipropetrovsk 49041

Ph.D. student

References

Kosolap A. I. Globalnaya optimizatsiya. Metod tochnoy kvadratichnoy regulyarizatsii [Global optimization. A method of exact quadratic regularization]. Dnipropetrovs’k, PGASA [PSАES], 2015, 164 p. (in Russian).

Kosolap A. I. Globalnaia optimizatsiia. Chislennyye eksperimenty [Global optimization. Numerical Experiments]. Dnepr: PGASA [PSАES], 2015, 112 p. (in Russian).

Baker, K. R., Trietsch D. Principles of sequencing and scheduling. Hoboken, New Jersey: A JOHN WILEY & SONS, 2009, 510 p.

Brucker, P. Scheduling Algorithms. Berlin: Springer-Verlag, 2007. 377 p.

Coffman E.G., Bruno J.L., Graham R.L. and etc. Computer and job-shop scheduling theory. John Wiley & Sons, 1976, 336p.

Nocedal, J., Wright S. J. Numerical optimization. Springer, 2006. 685 p.

Pinedo, M. L. Scheduling: Theory, Algorithms, And Systems; Fourth Edition. New York: Springer, 2012. 696 p.

Downloads

Published

2017-10-24

Issue

No. 101 (2017)

Section

Computer systems and information technologies in education, science and management

License

Редакція  Видання категорично засуджує прояви плагіату в статтях та вживає всіх можливих заходів для його недопущення. Плагіат розглядається як форма порушення авторських прав і наукової етики.

При виявлені у статті більш ніж 25% запозиченого тексту без відповідних посилань та використання лапок, стаття кваліфікується як така, що містить плагіат. У цьому випадку стаття більше не розглядається редакцією, а  автор отримує перше попередження.

Автори, в статтях яких повторно виявлено плагіат, не зможуть публікуватися в усіх журналах Видавництва ДВНЗ «Придніпровська державна академія будівництва та архітектури».

Автори, які публікуються у цьому журналі, погоджуються з наступними умовами:

  1. Автори залишають за собою право на авторство своєї роботи та передають журналу право першої публікації цієї роботи на умовах ліцензії Creative Commons Attribution License, котра дозволяє іншим особам вільно розповсюджувати опубліковану роботу з обов'язковим посиланням на авторів оригінальної роботи та першу публікацію роботи у цьому журналі.
  2. Автори мають право укладати самостійні додаткові угоди щодо неексклюзивного розповсюдження роботи у тому вигляді, в якому вона була опублікована цим журналом (наприклад, розміщувати роботу в електронному сховищі установи або публікувати у складі монографії), за умови збереження посилання на першу публікацію роботи у цьому журналі.
  3. Політика журналу дозволяє і заохочує розміщення авторами в мережі Інтернет (наприклад, у сховищах установ або на особистих веб-сайтах) рукопису роботи, як до подання цього рукопису до редакції, так і під час його редакційного опрацювання, оскільки це сприяє виникненню продуктивної наукової дискусії та позитивно позначається на оперативності та динаміці цитування опублікованої роботи (див. The Effect of Open Access).