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

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

Abstract

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

CLC Number:

O221.7

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.

Figures/Tables 5

References 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]	ZHANG An, CHEN Yong, CHEN Guangting, CHEN Zhanwen, SHU Qiaojun, LIN Guohui. Maximum matching based approximation algorithms for precedence constrained scheduling problems [J]. Operations Research Transactions, 2022, 26(3): 57-74.
[2]	WANG Dong, LI Ganggang, LUO Wenchang. Approximation algorithm for mixed batch scheduling on identical machines for jobs with arbitrary sizes [J]. Operations Research Transactions, 2022, 26(3): 133-142.
[3]	Jianping LI, Lijian CAI, Junran LICHEN, Pengxiang PAN. The constrained multi-sources eccentricity augmentation problems [J]. Operations Research Transactions, 2022, 26(1): 60-68.
[4]	Hua CHEN, Guochuan ZHANG. A survey on approximation algorithms for one dimensional bin packing [J]. Operations Research Transactions, 2022, 26(1): 69-84.
[5]	Wenjie LIU, Dongmei ZHANG, Peng ZHANG, Juan ZOU. The seeding algorithm for $\mu$-similar Bregman divergences $k$-means problem with penalties [J]. Operations Research Transactions, 2022, 26(1): 99-112.
[6]	Jiachen JU, Qian LIU, Zhao ZHANG, Yang ZHOU. A local search analysis for the uniform capacitated $k$-means problem with penalty [J]. Operations Research Transactions, 2022, 26(1): 113-124.
[7]	Xiaowei LI, Xiayan CHENG, Rongheng LI. An approximation algorithm for Robust k-product facility location problem with linear penalties [J]. Operations Research Transactions, 2021, 25(4): 31-44.
[8]	Shanshan YU, Miaomiao JIN, Wenchang LUO. Approximation scheme for rescheduling on a single machine with job delay and rejection [J]. Operations Research Transactions, 2021, 25(2): 104-114.
[9]	Xiaoguang BAO, Chao LU, Dongmei HUANG, Wei YU. Approximation algorithm for min-max cycle cover problem on a mixed graph [J]. Operations Research Transactions, 2021, 25(1): 107-113.
[10]	Jianfeng REN, Xiaoyun TIAN. Squared metric facility location problem with outliers [J]. Operations Research Transactions, 2021, 25(1): 114-122.
[11]	ZHANG Yuzhong. A survey on job scheduling with rejection [J]. Operations Research Transactions, 2020, 24(2): 111-130.
[12]	LIU Xiaoxia, YU Shanshan, LUO Wenchang. Approximation algorithms for single machine parallelbatch scheduling with release dates subject to the number of rejected jobs not exceeding a given threshold [J]. Operations Research Transactions, 2020, 24(1): 131-139.
[13]	WANG Yizhan, ZHANG An, CHEN Yong, CHEN Guangting. An approximation algorithm for reclaimer scheduling [J]. Operations Research Transactions, 2020, 24(1): 147-154.
[14]	ZHANG Guochuan, CHEN Lin. The load balancing problem [J]. Operations Research Transactions, 2019, 23(3): 1-14.
[15]	XU Weijun, YU Canbin, XU Zhongyue. Multi-stage active portfolio management with multiple constraints and its empirical study [J]. Operations Research Transactions, 2018, 22(4): 57-68.

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

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 5

References 10

Related Articles 15

Recommended Articles

Metrics

Comments