Scheduling job classes on uniform machines

We study a scheduling problem with job classes on parallel uniform machines. All the jobs of a given class share a common due‐date. General, non‐decreasing and class‐dependent earliness and tardiness cost functions are assumed. Two objectives are considered: (i) minmax, where the scheduler is required to minimize the maximum earliness/tardiness cost among all the jobs and (ii) minmax‐minsum, where the scheduler minimizes the sum of the maximum earliness/tardiness cost in all job classes. The problem is easily shown to be NP‐hard, and we focus here on the introduction of simple heuristics. We introduce LPT (Largest Processing Time first)‐based heuristics for the allocation of jobs to machines within each class, followed by a solution of an appropriate non‐linear program, which produces for this job allocation an optimal schedule of the classes. We also propose a lower bound, based on balancing the load on the machines. Our numerical tests indicate that the heuristics result in very small optimality gaps.