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; T. C.E. Cheng

doi:10.1007/s10288-021-00480-3

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, T. C.E. Cheng

Research output: Journal article publication › Journal article › Academic research › peer-review

4 Citations (Scopus)

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	https://doi.org/10.1007/s10288-021-00480-3
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

More information

10.1007/s10288-021-00480-3

http://hdl.handle.net/10397/94216

Cite this

@article{61803e6e0bfa499db3bfd93118950f0d,

title = "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.",

keywords = "family jobs, ND agents, parallel-batch machine, Pareto-scheduling, polynomial time",

author = "Yuan Gao and Jinjiang Yuan and Ng, {C. T.} and Cheng, {T. C.E.}",

note = "Funding Information: The authors would like to thank the Associate Editor and two anonymous referees for their constructive comments and helpful suggestions. Gao was supported by the China Postdoctoral Science Foundation under Grant Number 2019M652555 and the National Natural Science Foundation of China under Grant Number 11901539. Yuan was supported by the National Natural Science Foundation of China under Grant Numbers 12071442 and 11771406. Publisher Copyright: {\textcopyright} 2021, The Author(s), under exclusive licence to Springer-Verlag GmbH Germany, part of Springer Nature.",

year = "2022",

month = jun,

doi = "10.1007/s10288-021-00480-3",

language = "English",

volume = "20",

pages = "273--287",

journal = "4OR",

issn = "1619-4500",

publisher = "Springer",

number = "2",

}

TY - JOUR

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

AU - Gao, Yuan

AU - Yuan, Jinjiang

AU - Ng, C. T.

AU - Cheng, T. C.E.

N1 - Funding Information: The authors would like to thank the Associate Editor and two anonymous referees for their constructive comments and helpful suggestions. Gao was supported by the China Postdoctoral Science Foundation under Grant Number 2019M652555 and the National Natural Science Foundation of China under Grant Number 11901539. Yuan was supported by the National Natural Science Foundation of China under Grant Numbers 12071442 and 11771406. Publisher Copyright: © 2021, The Author(s), under exclusive licence to Springer-Verlag GmbH Germany, part of Springer Nature.

PY - 2022/6

Y1 - 2022/6

N2 - 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.

AB - 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.

KW - family jobs

KW - ND agents

KW - parallel-batch machine

KW - Pareto-scheduling

KW - polynomial time

UR - http://www.scopus.com/inward/record.url?scp=85106449762&partnerID=8YFLogxK

U2 - 10.1007/s10288-021-00480-3

DO - 10.1007/s10288-021-00480-3

M3 - Journal article

AN - SCOPUS:85106449762

SN - 1619-4500

VL - 20

SP - 273

EP - 287

JO - 4OR

JF - 4OR

IS - 2

ER -

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

Abstract

Keywords

ASJC Scopus subject areas

More information

Other files and links

Fingerprint

Cite this