Vector scheduling with rejection on two machines. Issue 12 (1st December 2020)

• Record Type: Journal Article
• Authors: Dai, Bingfei; Li, Weidong
• Is Part Of: International journal of computer mathematics. Volume 97:Issue 12(2020)
• Page Start: 2507
• Page End: 2515
• Publication Date: 2020-12-01
• Subjects: Vector scheduling -- rejection -- approximation algorithm -- online algorithm; 90B35; Computers -- Periodicals; Numerical analysis -- Periodicals; Automation -- Periodicals; 004.0151
• DOI: 10.1080/00207160.2019.1711373
• Languages: English
• ISSNs: 0020-7160

Abstract

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.62 d, where d is the number of dimensions.