Minmax scheduling with acceptable lead-times: Extensions to position-dependent processing times, due-window and job rejection

In this paper we study several extensions of the minmax DIF model. First, we consider general position-dependent job processing times. Then we extend the model to a setting of a due-window for acceptable lead-times. Here, the assumption is that a time interval exists, such that due-dates assigned to be within this interval are not penalized. The last extension of the DIF model is to a setting allowing job-rejection. This option reflects many real-life situations, where the scheduler may decide to process only a subset of the jobs, and the rejected jobs are penalized. The first two extensions are shown to be polynomially solvable: we introduce solution algorithms requiring O(n3) and O(n4) time, respectively, where n is the number of jobs. The last extension (assuming job-rejection) is proved to be NP-hard in the ordinary sense, and an efficient pseudo-polynomial dynamic programming algorithm is introduced.