Minmax scheduling with job-classes and earliness–tardiness costs

We address scheduling problems with job-dependent due-dates and general (possibly nonlinear and asymmetric) earliness and tardiness costs. The number of distinct due-dates is substantially smaller than the number of jobs, thus jobs are partitioned to classes, where all jobs of a given class share a common due-date. We consider the settings of a single machine and parallel identical machines. Our objective is of a minmax type, i.e., we seek a schedule that minimizes the maximum earliness/tardiness cost among all jobs. We introduce a nonlinear program that needs to be solved in order to obtain an optimal solution for the single-machine case. The case of parallel identical machines is NP-hard even for two machines, linear costs and a single common due-date. We introduce an LPT-based (largest processing time first) heuristic and a simple lower bound on the optimal cost. Both the heuristic and the lower bound are asymptotically accurate under very general conditions. Our numerical tests indicate that the heuristic produces very close-to-optimal schedules in all settings.