Order acceptance and scheduling with weighted makespan

Lingfa Lu (), Lili Zuo (), Liqi Zhang () and Jinwen Ou ()
Additional contact information
Lingfa Lu: Zhengzhou University
Lili Zuo: Zhengzhou University
Liqi Zhang: Henan Agricultural University
Jinwen Ou: Jinan University

4OR, 2025, vol. 23, issue 3, No 2, 247-267

Abstract: Abstract In this paper, we study eight order acceptance and scheduling (OAS) problems by considering job splitting, a fixed number of distinct processing times, weights or rejection costs, and position-dependent processing times, weights or rejection costs, respectively. In each OAS problem in consideration, each job is either accepted and processed on a single machine, or rejected by paying a rejection cost, and the objective is to minimize the weighted makespan (maximum weighted completion time) of the accepted jobs plus the total rejection cost of the rejected jobs. We show that three of the eight OAS problems can be solved in polynomial time, another three of the eight OAS problems are NP-hard, but the computational complexities of the remaining two OAS problems are open. For each of those three NP-hard problems, we propose a pseudo-polynomial-time dynamic programming algorithm and an efficient approximation algorithm. Based on the vector trimming technique, we also obtain a fully polynomial time approximation scheme (FPTAS) for each of those NP-hard problems.

Keywords: Scheduling; Rejection; Weighted makespan; NP-hardness; Algorithm design; 90B35 (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10288-025-00586-y 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:aqjoor:v:23:y:2025:i:3:d:10.1007_s10288-025-00586-y

Ordering information: This journal article can be ordered from
https://www.springer ... ch/journal/10288/PSE

DOI: 10.1007/s10288-025-00586-y

Access Statistics for this article

4OR is currently edited by Yves Crama, Michel Grabisch and Silvano Martello

More articles in 4OR from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().