This study investigates a single-machine throughput maximization problem (TMP), in which each job is characterized by a processing time, ready date, due date, and weight, and must be completed within its time window to yield profit. The objective is to select and schedule a subset of jobs to maximize the total weight of completed jobs. While existing studies primarily focus on special cases or heuristic approaches, this paper develops a unified exact solution framework for the general TMP. The main contribution is a job-sorting-based approach in which dominance rules are derived from structural properties induced by a partial ordering, while a complete ordering based on time-window midpoints is used to guide job sequencing. Based on this framework, several solution approaches are developed, including implicit enumeration (IE) methods, branch-and-bound (B&B) methods enhanced with linear programming (LP) relaxation, and a mixed-integer programming (MIP) model. A heuristic method is also proposed to generate high-quality initial solutions that accelerate exact methods. Computational experiments are conducted on a comprehensive set of instances. The results demonstrate that the proposed job sorting and dominance rules significantly improve computational efficiency, leading to substantial reductions in solution time compared with baseline methods.
Hung et al. (Sat,) studied this question.