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

Yuan Gao, Jinjiang Yuan (), C. T. Ng and T. C. E. Cheng
Additional contact information
Yuan Gao: Zhengzhou University
Jinjiang Yuan: Zhengzhou University
C. T. Ng: The Hong Kong Polytechnic University
T. C. E. Cheng: The Hong Kong Polytechnic University

4OR, 2022, vol. 20, issue 2, No 5, 273-287

Abstract: 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\in \{A,B\}$$ E ∈ { A , B } has its job set $${{\mathcal {J}}}_{E}$$ J E , called the E-jobs. Assuming that the job sets $${{\mathcal {J}}}_{A}$$ J A and $${{\mathcal {J}}}_{B}$$ J B are not necessarily disjoint, we call the agents $$\text {ND}$$ 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.

Keywords: Pareto-scheduling; parallel-batch machine; family jobs; ND agents; polynomial time; 90B35; 90C27 (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10288-021-00480-3 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:aqjoor:v:20:y:2022:i:2:d:10.1007_s10288-021-00480-3

Ordering information: This journal article can be ordered from
https://www.springer ... ch/journal/10288/PSE

DOI: 10.1007/s10288-021-00480-3

Access Statistics for this article

4OR is currently edited by Yves Crama, Michel Grabisch and Silvano Martello

More articles in 4OR from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().