Single-Machine Lot Scheduling with Order Rejection

This study investigates the single-machine lot scheduling problem with order rejection. Each order may either be entirely processed in a single lot, or split into two segments to be processed in two consecutive lots. The aim is to construct a feasible schedule that minimizes the sum of the scheduling criterion of the accepted orders and the total rejection cost of the rejected orders. Two scheduling criteria are considered: the makespan and the total completion time. We analyze the computational complexity of both problems. For the case that the scheduling criterion is the makespan, we present an approximation algorithm with a worst-case performance ratio of [Formula: see text], along with a pseudo-polynomial time dynamic programming algorithm and a fully polynomial-time approximation scheme (FPTAS) for this problem. For the case that the scheduling criterion is the total completion time, we present an efficient pseudo-polynomial time algorithm to solve the problem optimally.