Pareto-scheduling with family jobs or ND-agent on a parallel-batch machine to minimize the makespan and maximum cost

Abstract

We study Pareto-scheduling on an unbounded parallel-batch machine that can process any number of jobs simultaneously in a batch. The processing time of a batch is equal to the maximum processing time of the jobs in the batch. We consider two Pareto-scheduling problems. In one problem, the jobs are partitioned into families and the jobs from different families cannot be processed together in the same batch. We assume that the number of families is a constant. The objective is to minimize the makespan and the maximum cost. In the other problem, we have two agents A and B, where each agent E∈ { A, B} has its job set JE, called the E-jobs. Assuming that the job sets JA and JB are not necessarily disjoint, we call the agents ND agents. The objective is to minimize the makespan of the A-jobs and the maximum cost of the B-jobs. We provide polynomial-time algorithms to solve the two Pareto-scheduling problems.