Single-Machine Schedule to Minimize the Number of Early and Tardy Jobs About Due Windows

摘要

This paper is concerned with the scheduling problems on a single machine. The just-in-time (JIT) concept has had a great impact on Chinese industry in the last decade. The philosophy emphasizes on-time delivery of sub-assemblies and final products. Early or tardy the due window of the job are highly discouraged and will incur earliness or tardiness penalty. The penalty is a fixed cost for each job if a job is completed without its due window, however early/tardy it is. The objective is minimize the total cost incurred for all penalized jobs. An time-polynomial algorithm is presented to find the optimal schedule. Finally, an example is shown to illustrate how the algorithm is used.