We schedule two agents on a single p-batching machine with non-identical job sizes. We minimize the makespan of one agent under a bounded makespan of the other agent. We show that no polynomial-time algorithm with a finite bound exists, unless P = NP. We propose an effective algorithm to obtain a lower bound of the optimal solution. We propose two heuristics and illustrate the effectiveness by computational studies.