Scheduling with step learning and job rejection

被引：0

作者：

Song, Jiaxin ^{[1
,2
]}

Miao, Cuixia ^{[1
]}

Kong, Fanyu ^{[3
]}

机构：

[1] Qufu Normal Univ, Sch Math Sci, Qufu 273165, Shandong, Peoples R China

[2] Nanjing Univ Informat Sci & Technol, Sch Management Sci & Engn, Nanjing 210044, Jiangsu, Peoples R China

[3] Qufu Normal Univ, Inst Operat Res, Rizhao 276826, Shandong, Peoples R China

来源：

OPERATIONAL RESEARCH | 2025年 / 25卷 / 01期

关键词：

Scheduling; Step learning; Rejection penalty; Pseudo-polynomial time algorithm; Fully polynomial-time approximation scheme; Approximation algorithm; SINGLE-MACHINE; RELEASE DATES; TIME; ALGORITHMS;

D O I：

10.1007/s12351-024-00887-w

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

This paper focuses on job scheduling with step learning and job rejection. The step learning model aims to reduce the processing time for jobs starting after a specific learning date. Our objective is to minimize the sum of the maximum completion time of accepted jobs and the total rejection penalty of rejected jobs. We examine special cases of processing times for both single-machine and parallel-machine scenarios. For the former, we design a pseudo-polynomial time algorithm, a 2-approximation algorithm and a fully polynomial-time approximation scheme (FPTAS) based on data rounding. For the latter, we present a fully polynomial-time approximation scheme achieved by trimming the state space. Additionally, for the general case of the single-machine problem, we propose a pseudo-polynomial time algorithm.

引用

页数：18