Мінімізація сумарного зваженого моменту випередження виконання завдань на одному приладі

• Date: 2023
• Author Affiliations: Alexander Pavlov — д. т. н., професор, Національний технічний університет України «КПІ ім. Ігоря Сікорського», пр. Перемоги, 37, 03056, Київ; Elena Khalus — старший викладач, Національний технічний університет України «КПІ ім. Ігоря Сікорського», пр. Перемоги, 37, 03056, Київ; Mykhailo Medvediev — студент, Національний технічний університет України «КПІ ім. Ігоря Сікорського», пр. Перемоги, 37, 03056, Київ
• Keywords: keywords
• Main Authors: Pavlov, Alexander, Khalus, Elena, Medvediev, Mykhailo
• Format: Article
• Language: Ukrainian
• Published: Інститут прикладних проблем механіки і математики ім. Я. С. Підстригача НАН України 2023
• Subjects: календарне планування; оптимізація; допустимий розклад; багаторівнева модель управління
• Online Access: https://www.fmmit.lviv.ua/index.php/fmmit/article/view/305
• Journal Title: Physico-mathematical modeling and informational technologies

We consider the problem of building a feasible schedule for the execution of tasks with various due dates on a single machine. The optimality criteria are double fold: the first is the latest time of the machine start, the second is minimization of the total weighted earliness of tasks in a feasible schedule where the criteria are given in a lexicographic order. That is, the starting time of the machine is as late as possible, and when this condition is fulfilled, the minimum possible value of the total weighted earliness of tasks is reached on a feasible schedule. The authors showed that this problem is qualitatively harder than the above formulated problem with equal positive weights. This paper proposes an exact method based on building of feasible solution trees. Fundamentally new are the formulated restrictions on the set of vertices of each level and the theoretically substantiated efficient rules for cutting branches. The rules are implemented in a statistically significant way already at the first levels of the feasible solution tree. The practical value of the proposed method is illustrated by the possibility of its application in a multi-level model of innovative project management at the last level of its hierarchy.