COMMON DUE-WINDOW SCHEDULING

In this paper, we solve common due-window scheduling problems within the just-in-time window concept, i.e., scheduling problems including both earliness and tardiness penalties. We assume that jobs share the same due window and incur no penalty as long as they are completed within the due window. We further assume that the earliness and tardiness penalty factors are constant and that the size of the window is a given parameter. For cases where the location of the due window is a decision variable, we provide a polynomial algorithm with complexity O(n * log (n)) to solve the problem. For cases where the location of the due window is a given parameter, we use dynamic programming with pseudopolynomial complexity to solve the problem.