Order acceptance and scheduling with weighted makespan

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.