Approximation algorithm for the parallel-machine scheduling problem with release dates and submodular rejection penalties
Approximation algorithm for the parallel-machine scheduling problem with release dates and submodular rejection penalties
复制标题
DOI：
10.1007/s10878-021-00842-x
复制
发表时间：
2022-01
影响因子：
1
通讯作者：
Hong Zheng;Suogang Gao;Wen Liu;Weili Wu;D. Du;Bo Hou
中科院分区：
文献类型：
--
作者：
Hong Zheng;Suogang Gao;Wen Liu;Weili Wu;D. Du;Bo Hou
本文研究了带交货期和子模块拒绝惩罚的并行机排序问题。在这个问题中，我们给出了n台虚拟并行机和n个作业。每个作业都有处理时间和发布日期。作业要么被拒绝（在这种情况下必须支付拒绝罚款），要么被接受并在其中一台相同的并行机上处理。其目标是使被接受工件的最大完工时间与被拒绝工件的拒绝惩罚之和最小，而拒绝惩罚由一个次模函数决定。我们的主要工作是设计一个基于原始-对偶框架的2-近似算法。
In this paper, we consider the parallel-machine scheduling problem with release dates and submodular rejection penalties. In this problem, we are givenmidentical parallel machines andnjobs. Each job has a processing time and a release date. A job is either rejected, in which case a rejection penalty has to be paid, or accepted and processed on one of themidentical parallel machines. The objective is to minimize the sum of the makespan of the accepted jobs and the rejection penalty of the rejected jobs which is determined by a submodular function. Our main work is to design a 2-approximation algorithm based on the primal-dual framework.