The prize-collecting single machine scheduling with bounds and penalties

Guojun Hu (), Pengxiang Pan (), Suding Liu (), Ping Yang () and Runtao Xie ()
Additional contact information
Guojun Hu: Yunnan Normal University
Pengxiang Pan: Yunnan University
Suding Liu: Yunnan University
Ping Yang: Yunnan University
Runtao Xie: Yunnan University

Journal of Combinatorial Optimization, 2024, vol. 48, issue 2, No 1, 13 pages

Abstract: Abstract This study investigates the prize-collecting single machine scheduling with bounds and penalties (PC-SMS-BP). In this problem, a set of n jobs and a single machine are considered, where each job $$J_j$$ J j has a processing time $$p_{j}$$ p j , a profit $$\pi _{j}$$ π j and a rejection penalty $$w_{j}$$ w j . The upper bound on the processing number is U. The objective of this study is to find a feasible schedule that minimizes the makespan of the accepted jobs and the total rejection penalty of the rejected jobs under the condition that the number of the accepted jobs does not exceed a given threshold U while the total profit of the accepted jobs does not fall below a specified profit bound $$\varPi $$ Π . We first demonstrate that this problem is NP-hard. Then, a pseudo-polynomial time dynamic programming algorithm and a fully polynomial time approximation scheme (FPTAS) are proposed. Finally, numerical experiments are conducted to compare the effectiveness of the two proposed algorithms.

Keywords: Scheduling; Rejection; Bounds; Dynamic programming; Fully polynomial time approximation scheme; 90B35; 05C90 (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-024-01203-0 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:48:y:2024:i:2:d:10.1007_s10878-024-01203-0

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

DOI: 10.1007/s10878-024-01203-0

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 ().