06106556

j

06106556 Gerstl, Enrique Mosheiov, Gur Scheduling job classes on uniform machines. Comput. Oper. Res. 39, No. 9, 1927-1932 (2012). 2012 Elsevier Science Ltd. (Pergamon), Oxford EN scheduling uniform machines earliness tardiness minmax heuristics

doi:10.1016/j.cor.2011.08.004

Summary: 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.