Vector scheduling with rejection on two machines

ABSTRACT

In this paper, we study the problem of vector scheduling with rejection on two identical parallel machines, where the objective is to minimize the sum of maximum load over all dimensions and machines and the total penalty cost. We present a 3-approximation algorithm and a 2.54-approximation algorithm based randomized rounding for the general case. When the number of dimensions is fixed, we design a fully polynomial time approximation scheme based on dynamic programming. Finally, we design an online algorithm with competitive ratio 1.62d, where d is the number of dimensions.

Keywords:

• Vector scheduling
• rejection
• approximation algorithm
• online algorithm

2010 Mathematics Subject Classification:

• 90B35

Disclosure statement

No potential conflict of interest was reported by the authors.

ORCID

Weidong Li http://orcid.org/0000-0003-3094-4347

Additional information

Funding

This work is supported in part by the National Natural Science Foundation of China [No. 61662088], IRTSTYN, and Program for Excellent Young Talents, Yunnan University.