Scheduling two types of jobs with minimum makespan

We consider scheduling two types of jobs (A-job and B-job) to p machines and minimizing their makespan. A group of same type of jobs processed consecutively by a machine is called a batch. For machine v, processing x A-jobs in a batch takes kAᵥx² time units for a given speed kAᵥ, and processing x B-jobs in a batch takes kBᵥx² time units for a given speed kBᵥ. We give an O(n²plog(n)) algorithm based on dynamic programming and binary search for solving this problem, where n denotes the maximal number of A-jobs and B-jobs to be distributed to the machines. Our algorithm also fits the easier linear case where each batch of length x of A-jobs takes kAᵥ x time units and each batch of length x of B-jobs takes kBᵥx time units. The running time is the same as the above case.