Abstract (ukr):
Предметом розгляду в роботі є задача, що належить до детермінованої теорії розкладів. У роботі запропоновано модель задачі складання розкладу мінімальної довжини. Також розглядаються змістовні та математичні постановки задач, які є узагальненнями цієї задачі. Необхідність формулювання і розв’язання узагальнень задачі продиктовано потребою оптимізації виробничих процесів. Зокрема, розглядається процес функціонування гнучкого автоматизованого підприємства, до складу якого належить транспортно-складська система і паралельнодіючі технологічні лінії. При цьому під технологічними лініями можуть розглядатися конвеєри, обробні центри, лінії збирання тощо.
Розглянута в роботі математична модель задачі описує процес взаємодії транспортного механізму з деякою кількістю паралельно діючих технологічних ліній, на яких виконується певна множина робіт. Є інформація про роботи, призначені на кожну лінію. Також задано час виконання кожної роботи. Роботи є неперервними і не можуть розриватися. Виробничі лінії є незалежними, тобто функціонують незалежно одна від одної. Функції транспортного засобу полягають у забезпеченні ліній засобами, без яких не може бути розпочато певну роботу. Для її виконання транспортний механізм за вказаний час доставляє зі складу на лінію необхідні засоби і повертає на склад, затративши за тим же маршрутом на зворотній шлях задану кількість часу. Кожна робота не може розпочинатися раніше моменту доставки ресурсів, необхідних для її виконання. Потрібно знайти таку траєкторію руху транспортного засобу, що мінімізувала би час функціонування всієї системи. Показано, що задача може бути зведеною до задачі Джонсона 2-x n.
Abstract (eng):
The subject of consideration in the research is the problem which belongs to the deterministic theory of schedules. The research presents a model of the problem of drawing up a minimum length expansion. Also, the content and mathematical statements of tasks that are generalizations of this task. The research investigates necessity of formulating and solving generalizations of the problem is dictated by the need for optimization of production processes. In particular, the process of functioning of a flexible automated enterprise, which includes the transport and storage system and parallel operating technological lines, is considered. In this case, technological lines may include conveyors, machining centers, assembly lines, etc.
The mathematical model of the problem regarded in the article describes the process of interaction of a transport mechanism with a number of parallel operating lines, on which a certain set of works is performed. There is information about the work assigned to each line. Also the time for each job performance is set. The work is continuous and cannot be broken. Production lines are independent, that is, they function independently of each other. The functions of a vehicle consist in providing lines with means, without which a certain work cannot be started. For its implementation, the transport mechanism at the given time the necessary means delivers from the warehouse to the line and returns to the warehouse, spending the same route time back. Each work cannot begin before the delivery of the resources necessary for its execution. It is necessary to find such a trajectory of the vehicle, which would minimize the time of operation of the whole system.
It is shown that the problem can be reduced to the Johnson problem 2 x n.