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

Abstract

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.

Keywords

• scheduling
• two agents
• pareto frontier
• approximation algorithms