Number of Tardy Jobs of Single Machine Scheduling Problem with Variable Processing Time

The number of tardy jobs of the single machine scheduling problem with a variable processing time is studied in accordance with the published instances of traffic transportation management engineering. It is proved by 3-partition problem that if the problem is of ready time and common deadline-constrained, its complexity is NP-hard in the strong sense. Finally, a polynomial algorithm for solving unit processing time and common deadline problems is proposed.