Scheduling job classes on uniform machines

作者：Gerstl Enrique; Mosheiov Gur^*

来源：Computers & Operations Research, 2012, 39(9): 1927-1932.

DOI：10.1016/j.cor.2011.08.004

• Scheduling
• Uniform machines
• Earliness-tardiness
• Minmax
• Heuristics

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.

• 出版日期2012-9