Реферат: The scheduling problems with job prohibitions are investigated. Here we are given a system of job subsets for positions of machines. For each position of a machine the subset indicates jobs, which can be performed in this position. The considered problems arise in the case of technological requisitions in production systems and multi-processor computer systems, where the order of job execution is influenced by fixed routes and structural constraints. At the same time, such problems play an important role in evolutionary algorithms, when the optimal recombination problem is solved in a crossover operator, and other iterative techniques based on solving a series of subproblems with job prohibitions. We analyze the computational complexity of the problem for various regular criteria in single-stage statements and multi-stage systems. We also discuss a general method to proving the NP-hardness of the specified class of scheduling problems using the polynomial reduction of the Ordered Partition Problem to the decision version of the problem, when an instance with the non-idle property is constructed. A solving approach based on the enumeration scheme and mixed integer linear programming models is proposed. This approach allows us to show that “almost all” instances are polynomially solvable, and it is important for evolutionary computation and other techniques based on enumerating partially mapped solutions.

Библиографическая ссылка: Zakharova Y.
Computational complexity and exact techniques for scheduling problems with job prohibitions
Journal of Scheduling. 2025. DOI: 10.1007/s10951-025-00840-5 WOS Scopus OpenAlex

Даты:

Принята к публикации:	13 февр. 2025 г.
Опубликована online:	2 апр. 2025 г.
Опубликована в печати:	21 апр. 2025 г.

Идентификаторы БД:

Web of science:	WOS:001457897800001
Scopus:	2-s2.0-105001717968
OpenAlex:	W4409174924

Цитирование в БД: Пока нет цитирований

Альметрики: