Solution of the generalized johnson problem with constraints on the schedule and time of the machine. Part 1. Exact solution methods

The problem of finding an optimal permutation which determines the sequence of a set of tasks in a fixed and equal for all tasks sequence of execution of certain works on different machines, is generalized to the case when the restrictions on the start and end time both for execution of individual tasks, and the time of equipment work are set. The properties of admissible and optimal sequence of tasks are studied. The formulas for calculating the lower limit of the total length of the schedule are presented. Exact and approximate methods for solving the problem are developed.