Due window scheduling for parallel machines

Abstract

Just-In-Time concepts are of increasing importance in today's competitive manufacturing environment. Concerning problem settings with earliness and tardiness penalties, researchers have studied a variety of problems where jobs incur no penalty for completion at a certain point in time. In practice, however, a job completion is acceptable without penalty rather for a time interval, which we call due window. We therefore extend recent work concerning due window scheduling from the single machine case to the parallel machine case.

We show that even the unit weight case is NP-complete for parallel machines, provide a dynamic programming algorithm for the two machine case as well as a heuristic with absolute error bound. The heuristic and its error bound are extended to the general case. As the number of jobs increase, the relative error bound vanishes.