Parallel-batch scheduling with rejection: Structural properties and approximation algorithms

doi:10.1016/j.ejor.2023.04.019

Parallel-batch scheduling with rejection: Structural properties and approximation algorithms

2023-11-01

7

PRE

AI

DOI：10.1016/j.ejor.2023.04.019

Original

Original request for help

Save

Abstract

En 中文

In this paper, we consider a parallel-batch machine scheduling (PBMS) model that unifies several existing scheduling models in the extant literature. In our scheduling model, a given set of jobs with different release dates are scheduled onto a machine that can process multiple jobs simultaneously in a batch. However, the number of jobs in a batch is limited. Each job can be rejected subject to a job-dependent penalty cost, but the total penalty cost of the jobs rejected is required to be no greater than a given bound. The objective is to minimize the weighted sum of the makespan of accepted jobs and the to-tal rejection penalty of rejected jobs. We provide some important structural properties and develop fast approximation algorithms. We also present an efficient polynomial time approximation scheme (EPTAS) with near-linear-time complexity. Our results significantly improve both the time complexities and per-formance bounds of several existing algorithms and approximation schemes.& COPY; 2023 Elsevier B.V. All rights reserved.

Keywords:

Scheduling

Parallel -batch

Rejection

Approximation algorithm

Worst -case analysis

Parallel-batch scheduling with rejection: Structural properties and approximation algorithms

Abstract

Journal

Organization