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

Bihui Cheng, Wencheng Wang and Ji Gao

Journal of Mathematics, 2023, vol. 2023, 1-8

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

Date: 2023
References: Add references at CitEc
Citations:

Downloads: (external link)
http://downloads.hindawi.com/journals/jmath/2023/8886388.pdf (application/pdf)
http://downloads.hindawi.com/journals/jmath/2023/8886388.xml (application/xml)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hin:jjmath:8886388

DOI: 10.1155/2023/8886388

Access Statistics for this article

More articles in Journal of Mathematics from Hindawi
Bibliographic data for series maintained by Mohamed Abdelhakeem ().