Minmax scheduling problems with common due-date and completion time penalty

We study the well-known common due-date assignment and scheduling problem and focus on minmax objective functions with position-dependent processing times. In due-date assignment problems, the objective is to find simultaneously the optimal job sequence and due-date that minimize the total earliness, tardiness and due-date related costs. Based on the solution of the problem with position-independent processing times, positional-weights are provided that lead to a simple solution procedure. Two extensions of the basic problem are discussed and solved to optimality. First, we generalize the results of the due-date to the setting of due-window assignment. Second, we study the common due-date problem with completion time penalty. The latter problem is studied with position-independent and position-dependent processing times as well as optional job rejection. For all studied problems, except the last, we introduce efficient polynomial time solutions. In respect to the last problem, considering job-rejection, we prove that it is NP-hard in the ordinary sense and provide an efficient pseudo-polynomial dynamic programming algorithm and extensive numerical study.