Формирование расписаний в задачах временного планирования
| Jazyk: | ruština |
|---|---|
| Rok vydání: | 2014 |
| Předmět: | |
| Zdroj: | Вестник Астраханского государственного технического университета. Серия: Управление, вычислительная техника и информатика. |
| ISSN: | 2224-9761 2072-9502 |
| Popis: | Важнейшим условием составления расписаний в проектной деятельности является учет множества временных ограничений, которые привязаны к периодическим интервалам времени проведения работ. В классических постановках задач класса JSSP (Job Shop Scheduling Problem) не уделяется должное внимание периодическим интервалам времени графиков работ большинства организаций и предприятий. Постановка и решение задачи планирования, предлагаемые нами, предполагают введение минимального отрезка времени, что позволяет гибко описывать структуру периодических временных ограничений. Рассматривается алгоритм временного сдвига, используемый для получения точного расписания в условиях периодических временных интервалов. Решение задачи подразумевает два этапа: на первом осуществляется построение непрерывного расписания (диаграмма Ганта), на втором происходит его последующая корректировка с учетом периодических временных ограничений произвольной формы. На втором этапе используется описанный алгоритм сдвига, вычислительная сложность которого зависит от минимального интервала времени и его размерности (длительности проекта). Апробация алгоритма в рамках модельно-алгоритмического комплекса на графах показывает несущественный рост сложности вычислений при значительном увеличении объема исходных данных. Таким образом, данный алгоритм имеет перспективы применения в крупных промышленных системах составления расписаний. Рассматриваемая задача планирования работ актуальна для предприятий и организаций, участвующих в разработке и внедрении проектов, поставщиков ИТ-услуг и т. д. Представленные механизмы и методики могут использоваться при разработке подсистем планирования в различных отраслях науки и техники (производство, транспорт, проектно-процессная деятельность). The most important condition in the scheduling of the project activity is keeping the set time limits, which are linked to periodic intervals of work time. Classic JSSP (Job Shop Scheduling Problem) tasking did not pay enough attention to periodic intervals schedules of most organizations and enterprises. Formulation and solution of the planning problem presented in this article involves the introduction of a minimum length of time that allows the flexibility to describe the structure of periodic time constraints. The article deals with the time shift algorithm used to obtain a precise schedule in terms of periodic time intervals. Solution of this problem involves two steps: the first step is to set up a continuous schedule (Gantt chart), the second comprises its subsequent periodic adjustment to the time constraints of an arbitrary shape. The second step is used to solve the problem of shift algorithm, the computational complexity of which depends on the minimum amount of time and its dimension (duration of the project). Algorithm testing within the model-algorithmic complex on the graphs shows insignificant increase in computational complexity with a significant increase in the volume of initial data. Thus, the algorithm has a data application prospects in large-scale industrial systems of scheduling. The considered problem of scheduling is urgent for companies and organizations involved in developing and implementing the projects, IT service providers, etc. The submitted mechanisms and techniques can be used in the development of planning subsystems in various branches of science and technology (production, transportation, design-process activities). |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|