Scheduling problems with rejection to minimize the k-th power of the makespan plus the total rejection cost

Lingfa Lu () and Liqi Zhang
Additional contact information
Lingfa Lu: Zhengzhou University
Liqi Zhang: Henan Agricultural University

Journal of Combinatorial Optimization, 2023, vol. 46, issue 1, No 9, 17 pages

Abstract: Abstract In this paper, we consider several scheduling problems with rejection on $$m\ge 1$$ m ≥ 1 identical machines. Each job is either accepted and processed on the machines, or it is rejected by paying a certain rejection cost. The objective is to minimize the sum of the k-th power of the makespan of accepted jobs and the total rejection cost of rejected jobs, where $$k>0$$ k > 0 is a given constant. We also introduce the conception of “job splitting" in our problems. First, we consider the single machine scheduling problem, i.e., $$m=1$$ m = 1 . When job splitting is allowed, we propose an $$O(n\log n)$$ O ( n log n ) -time optimal algorithm for the problem. When job splitting is not allowed, we show that this problem is polynomially solvable when $$k\in (0,1]$$ k ∈ ( 0 , 1 ] and it becomes binary NP-hard when $$k>1$$ k > 1 . Furthermore, for the NP-hard problem, we propose a pseudo-polynomial dynamic programming algorithm and a fully polynomial-time approximation scheme (FPTAS). Finally, we also extend our problems and some results to $$m\ge 2$$ m ≥ 2 identical parallel machines.

Keywords: Scheduling with rejection; NP-hard; Dynamic programming; FPTAS (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-023-01074-x Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:46:y:2023:i:1:d:10.1007_s10878-023-01074-x

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-023-01074-x

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().