| 工件有到达时间及可拒绝下的同类平行机排序问题的近似算法 |
| |
| 引用本文： | 毕春燕,万龙,罗文昌.工件有到达时间及可拒绝下的同类平行机排序问题的近似算法[J].运筹学学报,2022,26(2):73-82. |
| |
| 作者姓名： | 毕春燕 万龙 罗文昌 |
| |
| 作者单位： | 1. 宁波大学数学与统计学院, 浙江宁波 3152112. 江西财经大学信息管理学院, 江西南昌 330013 |
| |
| 基金项目： | 浙江省自然科学基金(LY19A010005);国家自然科学基金(11971252) |
| |
| 摘 要： | 本文研究工件有到达时间且可拒绝下的同类平行机排序问题。在该问题中, 给定一个待加工工件集, 每个工件在到达之后, 可以被选择安排到$m$台同类平行机器中的某一台机器上进行加工, 也可以被选择拒绝加工, 但需支付一定的拒绝惩罚费用。目标函数是最小化接受工件集的最大完工时间与拒绝工件集的总拒绝费用之和。当$m$为固定常数时, 设计了一个伪多项式时间动态规划精确算法; 当$m$为任意输入时, 设计了一个近似算法, 当接受工件个数大于$(m-1)$时, 该算法近似比为3, 当接受工件个数小于$(m-1)$时, 该算法近似比为$(2+\rho)$, 其中$\rho$为机器加工速度最大值和最小值的比值。最后通过算例演示了算法的运行。
|
| 关 键 词： | 同类机排序 工件可拒绝 动态规划 近似算法 |
| 收稿时间： | 2021-04-19 |
Approximation algorithm for uniform parallel machine scheduling with release dates and job rejection |
| |
| Affiliation: | 1. School of Mathematics and Statistics, Ningbo University, Ningbo 315211, Zhejiang, China2. School of Information Management, Jiangxi University of Finance and Economics, Nanchang 330013, Jiangxi, China |
| |
| Abstract: | In this paper, we consider the uniform parallel machine scheduling problem with release dates and job rejection. In this problem, given a set of jobs to be arranged subject to the job release dates, each job is either accepted to process on one of $m$ uniform parallel machines or rejected by paying its rejection penalty. The goal is to minimize the sum of the makespan of accepted jobs and the total rejection penalty of rejected jobs. When $m$ is a fixed constant, we provide a pseudo-polynomial time dynamic programming exact algorithm. When $m$ is arbitrary, we derive an approximation algorithm. If the number of accepted jobs is no less than $(m-1)$, then the derived approximation algorithm achieves the performance ratio of 3; otherwise, the derived approximation algorithm achieves the performance ratio of $(2+\rho)$, where $\rho$ is the ratio of the maximum machine processing speed to the minimum machine processing speed. In the end, by a numerical experiment, we illustrate the running way for the derived approximation algorithm. |
| |
| Keywords: | uniform parallel machine scheduling job rejection dynamic programming approximation algorithm |
|
| 点击此处可从《运筹学学报》浏览原始摘要信息 |
|
点击此处可从《运筹学学报》下载全文 |
|
