Two-Agent Pareto-Scheduling of Minimizing Total Weighted Completion Time and Total Weighted Late Work - Yuan Zhang; Zhichao Geng; Jinjiang Yuan (Mathematics, 2020)
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 <semantics>(1+ϵ)</semantics>-approximate Pareto frontier. In addition, some numerical tests are undertaken to evaluate the effectiveness of our algorithms.