Add to ORKG. In the job shop scheduling problem we are given m machines and n jobs; a job consists of a sequence of operations, each of which must be processed on a specified machine, and the aim is to complete all jobs as quickly as possible. This problem is strongly NP-hard even for very restrictive special cases. We give the first randomized and deterministic polynomial-time algorithms that yield polylogarithmic approximations to the optimal length schedule. Our algorithms also extend to the more general case where a job is given not by a linear ordering of the machines on which it must be processed but by an arbitrary partial order. Comparable bounds can also be obtained when there are m 0 types of machines, a specified number of machines of eac...