## 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 J_{E}, called the E-jobs. Assuming that the job sets J_{A} and J_{B} 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.

Original language | English |
---|---|

Pages (from-to) | 273-287 |

Number of pages | 15 |

Journal | 4OR |

Volume | 20 |

Issue number | 2 |

DOIs | |

Publication status | Published - Jun 2022 |

## Keywords

- family jobs
- ND agents
- parallel-batch machine
- Pareto-scheduling
- polynomial time

## ASJC Scopus subject areas

- Management Information Systems
- Theoretical Computer Science
- Management Science and Operations Research
- Computational Theory and Mathematics