Abstract:

There are two agents A and B with each having their own job sets. The jobs of a common agent can be  processed in a common batch. Moreover, each agent has an objective function to be minimized. This paper studies the two-agent scheduling problem on an unbounded parallel-batching machine to minimize maximum cost of agent A and makespan of agent B simultaneously. We present a polynomial-time algorithm for finding all Pareto optimal points of the problem.

Key words: two-agent scheduling, batching machine, maximum cost, pareto optimal solutions, computational complexity