Single Machine Vector Scheduling with General Penalties

Xiaofei Liu, Weidong Li and Yaoyu Zhu
Additional contact information
Xiaofei Liu: School of Information Science and Engineering, Yunnan University, Kunming 650500, China
Weidong Li: School of Mathematics and Statistics, Yunnan University, Kunming 650500, China
Yaoyu Zhu: School of Electronic Engineering and Computer Science, Peking University, Beijing 100871, China

Mathematics, 2021, vol. 9, issue 16, 1-16

Abstract: In this paper, we study the single machine vector scheduling problem (SMVS) with general penalties, in which each job is characterized by a d -dimensional vector and can be accepted and processed on the machine or rejected. The objective is to minimize the sum of the maximum load over all dimensions of the total vector of all accepted jobs and the rejection penalty of the rejected jobs, which is determined by a set function. We perform the following work in this paper. First, we prove that the lower bound for SMVS with general penalties is ? ( n ) , where ? ( n ) is any positive polynomial function of n . Then, we consider a special case in which both the diminishing-return ratio of the set function and the minimum load over all dimensions of any job are larger than zero, and we design an approximation algorithm based on the projected subgradient method. Second, we consider another special case in which the penalty set function is submodular. We propose a noncombinatorial e e ? 1 -approximation algorithm and a combinatorial min { r , d } -approximation algorithm, where r is the maximum ratio of the maximum load to the minimum load on the d -dimensional vector.

Keywords: vector scheduling; single machine; set function; approximation algorithm (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/9/16/1965/pdf (application/pdf)
https://www.mdpi.com/2227-7390/9/16/1965/ (text/html)

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:gam:jmathe:v:9:y:2021:i:16:p:1965-:d:616009

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().