The maximum deviation just-in-time scheduling problem Original Research Article

This note revisits the maximum deviation just-in-time (MDJIT) scheduling problem previously investigated by Steiner and Yeomans. Its main result is a set of algebraic necessary and sufficient conditions for the existence of a MDJIT schedule with a given objective function value. These conditions are used to provide a finer analysis of the complexity of the MDJIT problem. The note also investigates various special cases of the MDJIT problem and suggests several questions for further investigation.