Parallel machine scheduling with high multiplicity

In high-multiplicity scheduling problems, identical jobs are encoded in the efficient format of describing one of thr jobs and the number of identical jobs. Similarly, identical machines are efficiently encoded in the same manner. We investigate parallel-machine, high-multiplicity problems. where there are three possible machine speed structures: identical, proportional, or unrelated. For the objectives of minimizing the sum of job completion limes and minimizing the makespan, we consider both nonpreemptive and preemptive problems. Fur some problems, we develop polynomial time algorithms. For several problems, we demonstrate that the recognition versions can be solved in polynomial time, while the optimization versions require pseudo polynomial time. We also show that changing from standard binary encoding to high-multiplicity encoding does not affect the complexity class of NP-complete problems.