Single Machine Vector Scheduling with General Penalties
In this paper, we study the single machine vector scheduling problem (SMVS) with general penalties, in which each job is characterized by a <i>d</i>-dimensional vector and can be accepted and processed on the machine or rejected. The objective is to minimize the sum of the maximum load o...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2021-08-01
|
| Series: | Mathematics |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2227-7390/9/16/1965 |
| _version_ | 1827684878125105152 |
|---|---|
| author | Xiaofei Liu Weidong Li Yaoyu Zhu |
| author_facet | Xiaofei Liu Weidong Li Yaoyu Zhu |
| author_sort | Xiaofei Liu |
| collection | DOAJ |
| description | In this paper, we study the single machine vector scheduling problem (SMVS) with general penalties, in which each job is characterized by a <i>d</i>-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 <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>α</mi><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo></mrow></semantics></math></inline-formula>, where <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>α</mi><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo></mrow></semantics></math></inline-formula> is any positive polynomial function of <i>n</i>. 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 <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mfrac><mi>e</mi><mrow><mi>e</mi><mo>−</mo><mn>1</mn></mrow></mfrac></semantics></math></inline-formula>-approximation algorithm and a combinatorial <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mo movablelimits="true" form="prefix">min</mo><mo stretchy="false">{</mo><mi>r</mi><mo>,</mo><mi>d</mi><mo stretchy="false">}</mo></mrow></semantics></math></inline-formula>-approximation algorithm, where <i>r</i> is the maximum ratio of the maximum load to the minimum load on the <i>d</i>-dimensional vector. |
| first_indexed | 2024-03-10T08:37:19Z |
| format | Article |
| id | doaj.art-a611f3e3b19a4ccb907264daf41ca233 |
| institution | Directory Open Access Journal |
| issn | 2227-7390 |
| language | English |
| last_indexed | 2024-03-10T08:37:19Z |
| publishDate | 2021-08-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Mathematics |
| spelling | doaj.art-a611f3e3b19a4ccb907264daf41ca2332023-11-22T08:34:33ZengMDPI AGMathematics2227-73902021-08-01916196510.3390/math9161965Single Machine Vector Scheduling with General PenaltiesXiaofei Liu0Weidong Li1Yaoyu Zhu2School of Information Science and Engineering, Yunnan University, Kunming 650500, ChinaSchool of Mathematics and Statistics, Yunnan University, Kunming 650500, ChinaSchool of Electronic Engineering and Computer Science, Peking University, Beijing 100871, ChinaIn this paper, we study the single machine vector scheduling problem (SMVS) with general penalties, in which each job is characterized by a <i>d</i>-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 <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>α</mi><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo></mrow></semantics></math></inline-formula>, where <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>α</mi><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo></mrow></semantics></math></inline-formula> is any positive polynomial function of <i>n</i>. 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 <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mfrac><mi>e</mi><mrow><mi>e</mi><mo>−</mo><mn>1</mn></mrow></mfrac></semantics></math></inline-formula>-approximation algorithm and a combinatorial <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mo movablelimits="true" form="prefix">min</mo><mo stretchy="false">{</mo><mi>r</mi><mo>,</mo><mi>d</mi><mo stretchy="false">}</mo></mrow></semantics></math></inline-formula>-approximation algorithm, where <i>r</i> is the maximum ratio of the maximum load to the minimum load on the <i>d</i>-dimensional vector.https://www.mdpi.com/2227-7390/9/16/1965vector schedulingsingle machineset functionapproximation algorithm |
| spellingShingle | Xiaofei Liu Weidong Li Yaoyu Zhu Single Machine Vector Scheduling with General Penalties Mathematics vector scheduling single machine set function approximation algorithm |
| title | Single Machine Vector Scheduling with General Penalties |
| title_full | Single Machine Vector Scheduling with General Penalties |
| title_fullStr | Single Machine Vector Scheduling with General Penalties |
| title_full_unstemmed | Single Machine Vector Scheduling with General Penalties |
| title_short | Single Machine Vector Scheduling with General Penalties |
| title_sort | single machine vector scheduling with general penalties |
| topic | vector scheduling single machine set function approximation algorithm |
| url | https://www.mdpi.com/2227-7390/9/16/1965 |
| work_keys_str_mv | AT xiaofeiliu singlemachinevectorschedulingwithgeneralpenalties AT weidongli singlemachinevectorschedulingwithgeneralpenalties AT yaoyuzhu singlemachinevectorschedulingwithgeneralpenalties |