We study the scheduling problem for single machine
with preemptions of jobs. On a machine it is necessary to process
a set of n jobs. Simultaneous processing is prohibited, but
interrupts in processing jobs is possible. Each job j of the set
is characterize by it's weight w_j, release date r_j = j - 1 and
processing time p_j = 2. The only restriction is that weights w_j
are non-decreasing. The objective function can be expressed as the
sum of weighted completion times.
We suggest the polynomial
algorithm with complexity O(n^4) operations which gives us the
Pareto-optimal schedules for each set of jobs. In the algorithm we
use generalized Smith's rule, to obtain particular schedules after
moment r_n and to prove some important lemmas for reduction of
search of suitable schedules.