Premium
COMMON DUE‐WINDOW SCHEDULING
Author(s) -
KRÄMER FRANZJOSEF,
LEE CHUNGYEE
Publication year - 1993
Publication title -
production and operations management
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 3.279
H-Index - 110
eISSN - 1937-5956
pISSN - 1059-1478
DOI - 10.1111/j.1937-5956.1993.tb00102.x
Subject(s) - tardiness , computer science , window (computing) , scheduling (production processes) , dynamic programming , mathematical optimization , time complexity , job shop scheduling , algorithm , mathematics , computer network , routing (electronic design automation) , operating system
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.