In this paper, we consider high-multiplicity scheduling with rejection on parallel machines. It schedules k job types on m unrelated parallel machines, where each job type <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$J_{\kappa }$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>J</mi> <mi>κ</mi> </msub> </math></EquationSource> </InlineEquation> consists of <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$n_{\kappa }$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>n</mi> <mi>κ</mi> </msub> </math></EquationSource> </InlineEquation> identical jobs with the same processing time and rejection penalty. Each job type is either accepted, in which case all jobs must be processed and each job incurs a cost, or rejected, which incurs a rejection penalty. The goal is to minimize the makespan of accepted jobs and the total rejection penalty of rejected job types, subject to the total processing cost no greater than a given threshold. First, we obtain a bi-criteria (<InlineEquation ID="IEq3"> <EquationSource Format="TEX">$\frac{2e-1}{e-1}$</EquationSource> <EquationSource Format="MATHML"><math> <mfrac> <mrow> <mn>2</mn> <mi>e</mi> <mo>-</mo> <mn>1</mn> </mrow> <mrow> <mi>e</mi> <mo>-</mo> <mn>1</mn> </mrow> </mfrac> </math></EquationSource> </InlineEquation>,<InlineEquation ID="IEq4"> <EquationSource Format="TEX">$\frac{e}{e-1}$</EquationSource> <EquationSource Format="MATHML"><math> <mfrac> <mi>e</mi> <mrow> <mi>e</mi> <mo>-</mo> <mn>1</mn> </mrow> </mfrac> </math></EquationSource> </InlineEquation>)-approximation for this problem. Then, we design an exact algorithm for a special case of this problem where the number of jobs is polynomially bounded, the number of job types is a constant, and the target makespan is given. Finally, we also consider this problem on identical parallel machines and design a 2-approximation algorithm.

Exact and approximate algorithms for high-multiplicity scheduling with rejection on parallel machines

期刊论文
发表日期：

2026年7月31日

查看全文

Ruiqing Sun

摘要

In this paper, we consider high-multiplicity scheduling with rejection on parallel machines. It schedules k job types on m unrelated parallel machines, where each job type $J_{\kappa }$ $J_{κ}$ consists of $n_{\kappa }$ $n_{κ}$ identical jobs with the same processing time and rejection penalty. Each job type is either accepted, in which case all jobs must be processed and each job incurs a cost, or rejected, which incurs a rejection penalty. The goal is to minimize the makespan of accepted jobs and the total rejection penalty of rejected job types, subject to the total processing cost no greater than a given threshold. First, we obtain a bi-criteria ( $\frac{2e-1}{e-1}$ $\frac{2 e - 1}{e - 1}$ , $\frac{e}{e-1}$ $\frac{e}{e - 1}$ )-approximation for this problem. Then, we design an exact algorithm for a special case of this problem where the number of jobs is polynomially bounded, the number of job types is a constant, and the target makespan is given. Finally, we also consider this problem on identical parallel machines and design a 2-approximation algorithm.