OPEN SHOP SCHEDULING WITH MAXIMAL MACHINES

The objective of this paper is to develop polynomial algorithms far th e open shop makespan problem. It is shown that when a machine majorize s all other machines and the ith largest processing time on that machi ne is at least as large as the processing times of all operations on m achines i through m, the problem becomes polynomially solvable. The ut ilization 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 th e processing times of all operations for jobs i through n.