Ordering the structural set of jobs,minimizing the total penalty

The problem of setting up a schedule minimizing the total penalty is solved. A job set is specified. There are no precedence conditions. Each job consists of elementary operations. Job interruptions are allowed. Interruptions of elementary operations are not allowed. The penalty for an operation of a job to be executed at instantt is. A schedule is evaluated by a penalty that is the sum of the penalties of all the elementary operations of all jobs in set. It is assumed that set is structural. The problem is to find the schedule with a start in a prescribed interval T₁,T₂] with the least penalty. Compatible structural schedules are introduced into consideration. The class of compatible structural schedules contains the solution of the problem. An algorithm solving the problem is proposed having complexity, in the worst case, whereK is the number of jobs in the set.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 90, pp. 229–264, 1979.