A Combinatorial Approximation Algorithm for the Vector Scheduling with Submodular Penalties on Parallel Machines

In this paper, we focus on solving the vector scheduling problem with submodular penalties on parallel machines. We are given n jobs and m parallel machines, where each job is associated with a d-dimensional vector. Each job can either be rejected, incurring a rejection penalty, or accepted and proc...

Full description

Saved in:
Bibliographic Details
Published in:Journal of mathematics (Hidawi) 2023, Vol.2023, p.1-8
Main Authors: Cheng, Bihui, Wang, Wencheng
Format: Article
Language:English
Subjects:
Algorithms
Approximation
Combinatorial analysis
Fines & penalties
Mathematical analysis
Mathematical functions
Optimization
Scheduling
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In this paper, we focus on solving the vector scheduling problem with submodular penalties on parallel machines. We are given n jobs and m parallel machines, where each job is associated with a d-dimensional vector. Each job can either be rejected, incurring a rejection penalty, or accepted and processed on one of the m 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 2−1/mminr,d-approximation algorithm to solve this problem. Here, r denotes the maximum ratio of the maximum load to the minimum load on the d-dimensional vectors among all jobs.
ISSN:2314-4629
2314-4785
DOI:10.1155/2023/8886388