Solving the days-off scheduling problem using quadratic programming with circulant matrix
Închide
Conţinutul numărului revistei
Articolul precedent
Articolul urmator
63 0
Căutarea după subiecte
similare conform CZU
519.853.32:004.42 (1)
Cercetări operaționale (OR) teorii şi metode matematice (149)
Programe. Software (211)
SM ISO690:2012
MORARU, Vasile; ISTRATI, Daniela; ZAPOROJAN, Sergiu. Solving the days-off scheduling problem using quadratic programming with circulant matrix. In: Journal of Engineering Sciences. 2022, nr. 4, pp. 97-108. ISSN 2587-3474.
10.52326/jes.utm.2022.29(4).05
EXPORT metadate:
Google Scholar
Crossref
CERIF

DataCite
Dublin Core
Journal of Engineering Sciences
Numărul 4 / 2022 / ISSN 2587-3474 /ISSNe 2587-3482

Solving the days-off scheduling problem using quadratic programming with circulant matrix

Rezolvarea problemei planificării zilelor libere folosind programarea pătratică cu matricea circulantă

DOI: https://doi.org/10.52326/jes.utm.2022.29(4).05
CZU: 519.853.32:004.42

Pag. 97-108

Moraru Vasile, Istrati Daniela, Zaporojan Sergiu
 
Technical University of Moldova
 
Disponibil în IBN: 18 ianuarie 2023


Rezumat

The purpose of this paper is the approach of a mathematical model dedicated to planning the consecutive days off of a company’s employees. Companies must find a flexible work schedule between employees, always considering the satisfaction of work tasks as well as guaranteeing consecutive days off. The analysis is based on solving a quadratic programming problem with binary variables. The proposed method uses the properties of the circulant symmetric matrix in the researched model, which allows the transformation of the considered problems into an equivalent separable non-convex optimization problem. A practical continuous convex relaxation approach is proposed. DC Algorithm is used to solve relaxed problems. A solved numerical example is presented.

Scopul acestei lucrări este abordarea unui model matematic dedicat planificării zilelor libere consecutive ale angajaților unei companii. Companiile trebuie să găsească un program de lucru flexibil între angajați, având întotdeauna în vedere satisfacerea sarcinilor de lucru cât și garantarea zilelor libere consecutive. Tratarea se bazează pe rezolvarea unei probleme de programare pătratică cu variabile binare. Metoda propusă utilizează proprietățile matricei simetrice circulante din modelul cercetat, care permite transformarea problemei considerate într-o problemă echivalentă de optimizare neconvexă separabilă. Este propusă o abordare practică de relaxare continuă convexă. Pentru rezolvarea problemei relaxate se utilizează Algoritmul DC. Se prezintă un exemplu numeric rezolvat.

Cuvinte-cheie
scheduling problem, binary quadratic programming, circulant matrix, separable optimization, convex relaxation,

problemă de planificare, programare pătratică binară, matrice circulantă, optimizare separabilă, relaxare convexă