An earliness and tardiness problem in single machine scheduling with a common due window

This paper considers the following scheduling problem: (P):n jobs demand to be processed on the same machine and there exists a common due window for each job. If a job finishes its processing ahead of the common due window, it will be a weighted early job, and if a job finishes its processing after the common due window, then it will be a weighted tardy job. The task is to schedule the n jobs and determine a location of the common due window such that the weighted number of early and tardy jobs is minimized. This paper proves the NP-hardiness of the problem, and gives a pseudopolynomial branch algorithm, that is to say it is an ordinary NP-hand problem and not a strong NP-hard one.