Optimal schedulings with gaps for independent jobs in a service system withN servers

One considers the problem of forming the optimal schedulings with gaps for a service system withN identical parallel processors. In the service one performsK jobs, each of which consists of V_i homogeneous independent operations and has lower and upper directive times d_i and D_i. For the operations which constitute the jobs, one considers linear penalty functions outside the interval [d_i,D_i]. One solves the problem of finding the schedulings with a minimal total penalty and having the origin in a given interval [t₁,t₂]. It is proved that for an arbitrary set Z of jobs, the penalty function F_Z(t), where t is the origin of the scheduling, has a unique minimum for t∈(?∞,+∞). We present an algorithm for the construction of the optimal scheduling requiring (C cdot Kleft( {mathop {max }limits_i left{ {D_i } right} - mathop {min }limits_i left{ {d_i } right} + sumlimits_1^kappa {V_i } } right)) operations on an electronic computer.