This paper presents approximation algorithms for scheduling jobs on unrelated parallel machines. The main result is a polynomial algorithm that guarantees a schedule no longer than twice the optimal makespan. A polynomial approximation scheme is also provided for fixed numbers of machines, based on a theorem relating integer and linear programming relaxations. The authors prove that no polynomial algorithm can achieve a worst-case ratio less than 3/2 unless P=NP. They also classify the complexity of all special cases with a fixed number of processing times. The paper discusses the relationship between scheduling and integer programming, and presents a rounding theorem for integer programs with arbitrary coefficients. The authors also provide a polynomial approximation scheme for the case of a fixed number of machines, and show that for any fixed number of machines, a polynomial approximation scheme exists. The paper concludes with a discussion of the limits of approximation, showing that certain polynomial approximation algorithms cannot exist unless P=NP. The authors also consider special cases with restricted processing times and show that the minimum makespan problem is solvable in polynomial time for certain cases.This paper presents approximation algorithms for scheduling jobs on unrelated parallel machines. The main result is a polynomial algorithm that guarantees a schedule no longer than twice the optimal makespan. A polynomial approximation scheme is also provided for fixed numbers of machines, based on a theorem relating integer and linear programming relaxations. The authors prove that no polynomial algorithm can achieve a worst-case ratio less than 3/2 unless P=NP. They also classify the complexity of all special cases with a fixed number of processing times. The paper discusses the relationship between scheduling and integer programming, and presents a rounding theorem for integer programs with arbitrary coefficients. The authors also provide a polynomial approximation scheme for the case of a fixed number of machines, and show that for any fixed number of machines, a polynomial approximation scheme exists. The paper concludes with a discussion of the limits of approximation, showing that certain polynomial approximation algorithms cannot exist unless P=NP. The authors also consider special cases with restricted processing times and show that the minimum makespan problem is solvable in polynomial time for certain cases.