Vector scheduling with rejection on a single machine |
| |
Authors: | Weidong Li Qianna Cui |
| |
Affiliation: | 1.Yunnan University,Kunming,People’s Republic of China;2.Dianchi College of Yunnan University,Kunming,People’s Republic of China |
| |
Abstract: | In this paper, we study a vector scheduling problem with rejection on a single machine, in which each job is characterized by a d-dimension vector and a penalty, in the sense that, jobs can be either rejected by paying a certain penalty or assigned to the machine. The objective is to minimize the sum of the maximum load over all dimensions of the total vector of all accepted jobs, and the total penalty of rejected jobs. We prove that the problem is NP-hard and design two approximation algorithms running in polynomial time. When d is a fixed constant, we present a fully polynomial time approximation scheme. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|