by Kravchenko, S., Werner, F..

**Series:** 1998-13, Preprints

- MSC:
- 90B35 Scheduling theory, deterministic

**Abstract:**

In this paper we give a polynomial algorithm for problem

Q|r_j, p_j=p, pmtn | \sum C_j whose complexity status was open yet. The algorithm is

based on a reduction of the scheduling problem to a linear

program. The crucial condition for implementing the proposed reduction is the known order of job completion times.

**Keywords:**

Parallel uniform machines, Linear Programming, Maximum Flow; Polynomial Algorithm