GLORIA — GEOMAR Library Ocean Research Information Access

Hits per page

hit 1 - 1 | 1 hit

Select All Export

Unknown

Vector scheduling with rejection on a single machine (2018)

Springer

In: 4OR

add to mindlist on the mindlist

Details

Publication Date: 2018-03-05

Description: 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.

Print ISSN: 1619-4500

Electronic ISSN: 1614-2411

Topics: Mathematics

Published by Springer

	Location	Call Number	Limitation	Availability

Others were also interested in ...

PAPER CURRENT

Fulltext

hit 1 - 1 | 1 hit