<p>In this paper, 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 that 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 and multistage systems. We also discuss a general method for proving the NP-hardness of the specified class of scheduling problems, applying a polynomial reduction of the ordered partition problem to the decision version of the problem when an instance with the non-idle property is constructed. An approach for solving 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.</p>