The objective of this paper is to develop polynomial algorithms for the open shop makespan problem. It is shown that when a machine majorizes all other machines and the ith largest processing time on that machine is at least as large as the processing times of all operations on machines i through m, the problem becomes polynomially solvable. The utilization of the duality property between jobs and machines leads to a similar polynomial algorithm when a job majorizes all other jobs and the ith largest processing time of this job is at least as large as the processing times of all operations for jobs i through n.