Two-Agent Pareto-Scheduling of Minimizing Total Weighted Completion Time and Total Weighted Late Work

Mathematics

Zhichao Geng¹  Jinjiang Yuan¹  Yuan Zhang¹ 

[1] School of Mathematics and Statistics, Zhengzhou University, Zhengzhou 450001, China;

关键词: scheduling;    two agents;    pareto frontier;    approximation algorithms;   

DOI  :  10.3390/math8112070

来源: DOAJ

【 摘 要 】

We investigate the Pareto-scheduling problem with two competing agents on a single machine to minimize the total weighted completion time of agent A’s jobs and the total weighted late work of agent B’s jobs, the B-jobs having a common due date. Since this problem is known to be NP-hard, we present two pseudo-polynomial-time exact algorithms to generate the Pareto frontier and an approximation algorithm to generate a $(1+ϵ)$-approximate Pareto frontier. In addition, some numerical tests are undertaken to evaluate the effectiveness of our algorithms.

【 授权许可】

Unknown