Open AccessAbout One–Dimensional Space Allocation Problem with forbidden zones
Author(s) -
G. G. Zabudsky,
N. S. Veremchuk
Publication year - 2019
Publication title -
journal of physics. conference series
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.21
H-Index - 85
eISSN - 1742-6596
pISSN - 1742-6588
DOI - 10.1088/1742-6596/1260/8/082006
Subject(s) - graph , computer science , space (punctuation) , mathematical optimization , theoretical computer science , order (exchange) , scheme (mathematics) , time complexity , spacetime , algorithm , mathematics , mathematical analysis , operating system , physics , finance , quantum mechanics , economics
This article discusses the One–Dimensional Space Allocation Problem (ODSAP) with the additional conditions. There are fixed objects (forbidden zones) and a partial order of placement objects on the line. You can not place objects in forbidden zones. The structure of connections between objects is determined using a directed graph. Situations of this type arise, for example, when designing the placement of technological equipment of some enterprise. Technological scheme of production determines the order of processing of raw materials. A polynomial–time algorithm for finding a local optimum for a special graph of connections between objects is proposed.