Exact and approximate algorithms for high-multiplicity parallel machine scheduling

摘要

In many scheduling applications, a large number of jobs are grouped into a comparatively small number of lots made of identical items. It is then sufficient to give, for each lot, the number of jobs it involves plus the description of one single job. The resulting high-multiplicity input format is much more compact than the standard one. As a consequence, in order to be efficient, standard solution methods must be modified.rnWe consider high-multiplicity parallel machine scheduling problems with identical, uniform, and unrelated machines, and two classic objectives: minimum sum of completion times and minimum makespan. For polynomially solvable cases, we provide exact algorithms, while for hard cases we provide approximate, asymptotically exact algorithms. The exact algorithms exploit multiplicities to identify and fix a partial schedule, consisting of most jobs, that is contained in an optimal schedule, and then solve the residual problem optimally. The approximate algorithms use the same approach, but in their case neither it is guaranteed that the fixed partial schedule is contained in an optimal one nor the residual problem is optimally solved. All proposed algorithms are polynomial and easy to implement for practical purposes.