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

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.