document: Minimizing weighted number of early and tardy jobs with a common due window involving location penalty Studies a single machine scheduling problem to minimize the weighted number of early and tardy jobs with a common due window . There are n non-preemptive and simultaneously available jobs . Each job will incur an early -LRB- tardy -RRB- penalty if it is early -LRB- tardy -RRB- with respect to the common due window under a given schedule . The window size is a given parameter but the window location is a decision variable . The objective of the problem is to find a schedule that minimizes the weighted number of early and tardy jobs and the location penalty . We show that the problem is NP-complete in the ordinary sense and develop a dynamic programming based pseudo-polynomial algorithm . We conduct computational experiments , the results of which show that the performance of the dynamic algorithm is very good in terms of memory requirement and CPU time . We also provide polynomial time algorithms for two special cases
doc_bio_tags: O O O O O O B I O O B I I O B I O O B I I I O O O O O O O O B I O O B I I O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O B I I O O O O O O O O O O O O O O O O O O B I O O O O O O O O O O O O O O O O O O O B I O O B I O O O O O O O O O O O O O O O B I O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O