High multiplicity in earliness–tardiness scheduling

When a production shop has a large number of identical parts, the parts are often recorded by a part description and quantity. This differs from the type of description used by standard scheduling problems, which assume that all parts or jobs are unique. In high-multiplicity scheduling problems, identical jobs are encoded in an efficient format similar to that of the production shop. The input describes one of the jobs and the number of such identical jobs. We consider single-machine, high-multiplicity problems with earliness and tardiness weights. We investigate three categories of weights: unit, common, and job-specific. For the unit and common weights problems, a polynomial time algorithm is developed. The algorithm takes advantage of identical jobs and finds solutions faster than by standard methods. We provide a new method for creating a lower bound for the standard encoding of the job-specific weights problem, which is NP-complete. We disaggregate each job into identical subjobs with unit processing times. Then, using high-multiplicity encoding for this disaggregated problem, we create a lower bound on the optimal objective function value of the original problem in polynomial time. Heuristic solutions are generated using a randomized rounding technique on the lower bound solution. These results are used in a branch-and-bound solution method. Analytical and computational results are presented. Our combination of disaggregation and high-multiplicity encoding provides a new method for creating lower bounds on the objective functions of NP-complete problems.