Abstract. The paper considers the properties of admissible and optimal sequences of performing tasks by one machine under constraints on the terms of the beginning and completion of tasks and on partial sequences of task performance. The established properties and the lower-bound estimates of the length of the optimal schedule are used to develop methods for the exact and approximate solutions of the formulated problem by sequential optimization algorithms. The proposed algorithms are illustrated by numerical examples and can be successfully applied to solve these problems in the absence of constraints. Figs: 2. Tabl.: 8. Refs: 13 titles.

Keywords: optimal schedule, job sequencing, makespan constraints, sequential optimization algorithms.