Serial batch scheduling on uniform parallel machines to minimize total completion time

• We study two serial batch scheduling problems on uniform machines.
• The objectives are to minimize total completion time and total rejection penalty.
• We provide two polynomial time algorithms.

We consider two scheduling problems on m uniform serial batch machines where m   is fixed. In the first problem, all jobs have to be scheduled and the objective is to minimize total completion time. In the second problem, each job may be either rejected or accepted to be scheduled and the objective is to minimize the sum of total completion time and total rejection penalty. A polynomial time procedure is presented to solve both problems with the time complexity O(m2nm+2)O(m2nm+2) and O(m2nm+5)O(m2nm+5), respectively.