DOI: 10.1155/2023/8886388 ISSN: 2314-4785
A Combinatorial Approximation Algorithm for the Vector Scheduling with Submodular Penalties on Parallel Machines
Bihui Cheng, Wencheng Wang In this paper, we focus on solving the vector scheduling problem with submodular penalties on parallel machines. We are given
jobs and
parallel machines, where each job is associated with a
-dimensional vector. Each job can either be rejected, incurring a rejection penalty, or accepted and processed on one of the
parallel machines. The objective is to minimize the sum of the maximum load overall dimensions of the total vector for all accepted jobs, along with the total penalty for rejected jobs. The penalty is determined by a submodular function. Our main work is to design a
-approximation algorithm to solve this problem. Here,
denotes the maximum ratio of the maximum load to the minimum load on the
-dimensional vectors among all jobs.