工件有到达时间及可拒绝下的同类平行机排序问题的近似算法

doi:10.15960/j.cnki.issn.1007-6093.2022.02.007

运筹学学报 ›› 2022, Vol. 26 ›› Issue (2): 73-82.doi: 10.15960/j.cnki.issn.1007-6093.2022.02.007

工件有到达时间及可拒绝下的同类平行机排序问题的近似算法

毕春燕¹, 万龙², 罗文昌¹^,*()

1. 宁波大学数学与统计学院, 浙江宁波 315211
2. 江西财经大学信息管理学院, 江西南昌 330013

收稿日期:2021-04-19 出版日期:2022-06-15 发布日期:2022-05-27
通讯作者: 罗文昌 E-mail:luowenchang@163.com
作者简介:罗文昌 E-mail: luowenchang@163.com
基金资助:
浙江省自然科学基金(LY19A010005);国家自然科学基金(11971252)

Approximation algorithm for uniform parallel machine scheduling with release dates and job rejection

Chunyan BI¹, Long WAN², Wenchang LUO¹^,*()

1. School of Mathematics and Statistics, Ningbo University, Ningbo 315211, Zhejiang, China
2. School of Information Management, Jiangxi University of Finance and Economics, Nanchang 330013, Jiangxi, China

Received:2021-04-19 Online:2022-06-15 Published:2022-05-27
Contact: Wenchang LUO E-mail:luowenchang@163.com

摘要/Abstract

摘要：

本文研究工件有到达时间且可拒绝下的同类平行机排序问题。在该问题中, 给定一个待加工工件集, 每个工件在到达之后, 可以被选择安排到$m$台同类平行机器中的某一台机器上进行加工, 也可以被选择拒绝加工, 但需支付一定的拒绝惩罚费用。目标函数是最小化接受工件集的最大完工时间与拒绝工件集的总拒绝费用之和。当$m$为固定常数时, 设计了一个伪多项式时间动态规划精确算法; 当$m$为任意输入时, 设计了一个近似算法, 当接受工件个数大于$(m-1)$时, 该算法近似比为3, 当接受工件个数小于$(m-1)$时, 该算法近似比为$(2+\rho)$, 其中$\rho$为机器加工速度最大值和最小值的比值。最后通过算例演示了算法的运行。

关键词: 同类机排序, 工件可拒绝, 动态规划, 近似算法

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.

Key words: uniform parallel machine scheduling, job rejection, dynamic programming, approximation algorithm

中图分类号:

O221.7

毕春燕, 万龙, 罗文昌. 工件有到达时间及可拒绝下的同类平行机排序问题的近似算法[J]. 运筹学学报, 2022, 26(2): 73-82.

Chunyan BI, Long WAN, Wenchang LUO. Approximation algorithm for uniform parallel machine scheduling with release dates and job rejection[J]. Operations Research Transactions, 2022, 26(2): 73-82.

图/表 5

表1

表2

表3

表4

图1

参考文献 10

1	Bartal Y , Leonardi S , Spaccamela A M , et al. Multi-processor scheduling with rejection[J]. SIAM Journal on Discrete Mathematics, 2000, 13, 64- 78. doi: 10.1137/S0895480196300522
2	Min X , He Y . On-line uniform machine scheduling with rejection[J]. Computing, 2000, 65, 1- 12. doi: 10.1007/PL00021409
3	Hoogeveen H , Skutella M , Woeginger G J . Preemptive scheduling with rejection[J]. Mathematical Programming, 2003, 94, 361- 374. doi: 10.1007/s10107-002-0324-z
4	Engels D W , Karger D R , Kolliopoulos S G , et al. Techniques for scheduling with rejection[J]. Journal of Algorithms, 2003, 49, 175- 191. doi: 10.1016/S0196-6774(03)00078-6
5	Zhang L Q , Lu L F , Yuan J J . Single machine scheduling with release dates and rejection[J]. European Journal of Operational Research, 2009, 198, 975- 978. doi: 10.1016/j.ejor.2008.10.006
6	Lu L F , NG C T , Zhang L Q . Optimal algorithms for single-machine scheduling with rejection to minimize the makespan[J]. International Journal of Production Economics, 2011, 130, 153- 158. doi: 10.1016/j.ijpe.2010.12.003
7	Ma R , Yuan J J . On-line scheduling on a single machine with rejection under an agreeable condition to minimize the total completion time plus the total rejection cost[J]. Information Processing Letters, 2013, 130, 153- 158.
8	Zhang L Q , Lu L F . Parallel machine scheduling with release dates and rejection[J]. Quarter Journal Operational Research, 2016, 14, 165- 172.
9	Graham R L , Lawler E L , Lenstra J K , et al. Optimization and approximation in deterministic sequencing and scheduling: A survey[J]. Annals of Discrete Mathematics, 1979, 5, 236- 287.
10	Lawler E L . Optimal sequencing a single machine subject to precedence constraints[J]. Management Science, 1973, 19, 544- 546. doi: 10.1287/mnsc.19.5.544

工件$J_j$	$J_1$	$J_2$	$J_3$	$J_4$	$J_5$	$J_6$	$J_7$	$J_8$	$J_9$	$J_{10}$
到达时间$r_{j}$	2	3	3	4	5	5	6	7	7	9
加工时间$p_{j}$	124	79	180	38	12	15	20	58	88	45
拒绝费用$w_{j}$	11	8	15	3	10	1	5	7	10	6

工件$J_j$	$J_{11}$	$J_{12}$	$J_{13}$	$J_{14}$	$J_{15}$	$J_{16}$	$J_{17}$	$J_{18}$	$J_{19}$	$J_{20}$
到达时间$r_{j}$	9	9	9	10	10	10	11	11	13	15
加工时间$p_{j}$	66	100	136	50	110	168	70	152	105	144
拒绝费用$w_{j}$	5	3	3	3	9	13	1	6	7	9

$J_j$	$J_1$	$J_2$	$J_{11}$	$J_8$	$J_{14}$	$J_{10}$	$J_4$	$J_7$	$J_6$	$J_{5}$
$r_{j}$	2	3	9	7	10	9	4	6	5	5
$p_{j}$	124	79	66	58	50	45	38	20	15	12
$w_{j}$	11	8	5	7	3	6	3	5	1	10

	$C_{1j}$	$C_{2j}$	$C_{3j}$	$C_{4j}$	$C_{5j}$	$C_{sj}$	$M_s$
$J_{1}$	72	$51\frac{1}{3}$	$30\frac{2}{3}$	$34\frac{4}{5}$	$25\frac{1}{2}$	$25\frac{1}{2}$	$M_5$
$\vdots$	$\vdots$	$\vdots$	$\vdots$	$\vdots$	$\vdots$	$\vdots$	$\vdots$
$J_{8}$	39	$29\frac{1}{3}$	$32\frac{5}{6}$	$34\frac{4}{5}$	$32\frac{3}{4}$	$29\frac{1}{3}$	$M_2$
$J_{14}$	35	46	$31\frac{1}{2}$	$33\frac{1}{5}$	$31\frac{3}{4}$	$31\frac{1}{2}$	$M_3$
$J_{10}$	$32\frac{1}{2}$	$44\frac{1}{3}$	39	$32\frac{1}{5}$	$31\frac{1}{8}$	$31\frac{1}{8}$	$M_5$
$J_{4}$	29	42	$37\frac{5}{6}$	$30\frac{4}{5}$	$35\frac{7}{8}$	29	$M_1$
$\vdots$	$\vdots$	$\vdots$	$\vdots$	$\vdots$	$\vdots$	$\vdots$	$\vdots$
$J_{5}$	35	$33\frac{1}{3}$	$33\frac{1}{2}$	$32\frac{3}{5}$	$32\frac{5}{8}$	$32\frac{3}{5}$	$M_4$

$J_j$	$J_1$	$J_2$	$J_3$	$J_4$	$J_5$	$J_6$	$J_7$	$J_8$	$J_9$	$J_{10}$
$Z(\pi(t_j))$	$108\frac{3}{5}$	$123\frac{7}{8}$	$90$	$126\frac{3}{4}$	$ 131\frac{1}{2}$	$131$	$127\frac{1}{2}$	$118$	$101\frac{4}{5}$	$116\frac{2}{3}$

$J_j$	$J_{11}$	$J_{12}$	$J_{13}$	$J_{14}$	$J_{15}$	$J_{16}$	$J_{17}$	$J_{18}$	$J_{19}$	$J_{20}$
$Z(\pi(t_j))$	$114\frac{1}{3}$	$101\frac{4}{5}$	$90$	$117$	$97 \frac{1}{8}$	$84\frac{1}{8}$	$101\frac{4}{5}$	$89\frac{2}{3}$	$89\frac{2}{3}$	$83\frac{1}{5}$

[1]	袁藩, 徐大川, 张冬梅. k-均值问题的差分隐私算法综述[J]. 运筹学学报, 2022, 26(3): 1-16.
[2]	张安, 陈永, 陈光亭, 陈占文, 舒巧君, 林国辉. 优先序约束的排序问题：基于最大匹配的近似算法[J]. 运筹学学报, 2022, 26(3): 57-74.
[3]	王冬, 李刚刚, 罗文昌. 工件具有任意尺寸的混合分批平行机排序问题的近似算法[J]. 运筹学学报, 2022, 26(3): 133-142.
[4]	李建平, 蔡力健, 李陈筠然, 潘鹏翔. 限制性多源点偏心距增广问题[J]. 运筹学学报, 2022, 26(1): 60-68.
[5]	陈婳, 张国川. 经典一维装箱问题近似算法的研究进展[J]. 运筹学学报, 2022, 26(1): 69-84.
[6]	刘文杰, 张冬梅, 张鹏, 邹娟. 带惩罚μ-相似Bregman散度k-均值问题的初始化算法[J]. 运筹学学报, 2022, 26(1): 99-112.
[7]	剧嘉琛, 刘茜, 张昭, 周洋. 带惩罚的相同容量k-均值问题的局部搜索算法[J]. 运筹学学报, 2022, 26(1): 113-124.
[8]	李小玮, 成夏炎, 李荣珩. 带有线性惩罚的鲁棒k-种产品设施选址问题的近似算法[J]. 运筹学学报, 2021, 25(4): 31-44.
[9]	余山杉, 金苗苗, 罗文昌. 工件延误和可拒绝下的单机重新排序问题的近似方案[J]. 运筹学学报, 2021, 25(2): 104-114.
[10]	包晓光, 路超, 黄冬梅, 余炜. 混合图上最小-最大圈覆盖问题的近似算法[J]. 运筹学学报, 2021, 25(1): 107-113.
[11]	任建峰, 田晓云. 带有异常点的平方度量设施选址问题[J]. 运筹学学报, 2021, 25(1): 114-122.
[12]	张玉忠. 工件可拒绝排序问题综述[J]. 运筹学学报, 2020, 24(2): 111-130.
[13]	刘晓霞, 余山杉, 罗文昌. 工作有到达时间且拒绝工件总个数受限的单机平行分批排序问题的近似算法[J]. 运筹学学报, 2020, 24(1): 131-139.
[14]	王翼展, 张安, 陈永, 陈光亭. 堆取料机调度问题的一个近似算法[J]. 运筹学学报, 2020, 24(1): 147-154.
[15]	张国川, 陈林. 负载均衡问题[J]. 运筹学学报, 2019, 23(3): 1-14.

工件有到达时间及可拒绝下的同类平行机排序问题的近似算法

Approximation algorithm for uniform parallel machine scheduling with release dates and job rejection

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 5

参考文献 10

相关文章 15

编辑推荐

Metrics

本文评价