Polynomial time algorithm for minmax scheduling with common due-window and proportional-linear shortening processing times.

ABSTRACT

This article deals with common due-window assignment and single-machine scheduling with proportional-linear shortening processing times. Objective cost is a type of minmax, that is, the maximal cost among all processed jobs is minimized. Our goal is to determine an optimal schedule, the optimal starting time, and size of due-window that minimize the worst cost, which consist of four parts earliness, tardiness, starting time and length of the due-window. Optimal properties of the problem are given, and then an optimal polynomial algorithm is proposed to solve the problem.