A note on competing-agent Pareto-scheduling

Yuan Gao, Jinjiang Yuan, C. T. Ng, T. C.E. Cheng

Research output: Journal article publicationJournal articleAcademic researchpeer-review


We consider Pareto-scheduling with two competing agents A and B on a single machine, in which each job has a positional due index and a deadline. The jobs of agents A and B are called the A-jobs and B-jobs, respectively, where the A-jobs have a common processing time, while the B-jobs are restricted by their precedence constraint. The objective is to minimize a general sum-form objective function of the A-jobs and a general max-form objective function of the B-jobs, where all the objective functions are regular. We show that the problem is polynomially solvable.

Original languageEnglish
JournalOptimization Letters
Publication statusAccepted/In press - 1 Jan 2020


  • Competing agents
  • Deadline
  • Pareto-scheduling
  • positional due indices
  • Precedence constraint

ASJC Scopus subject areas

  • Control and Optimization

Cite this