This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Clifford, J. J. Articles by Posner, M. E. Search for Related Content

High Multiplicity in Earliness-Tardiness Scheduling

Center for Naval Analyses, Alexandria, VA 22302
The Ohio State University, Department of Industrial, Welding and Systems Engineering, 1971 Neil Avenue, Columbus, Ohio 43210-1271
cliffoj{at}cna.org
posner.1{at}osu.edu

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 sub jobs 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.

Subject classifications: Production/scheduling, Deterministic Sequencing, Single machine: High multiplicity problems with an Earliness-Tardiness objective; Production/scheduling, Approximations/heuristic: disaggregate and then use high multiplicity methods.
History: Received April 1997; revision received May 1998; accepted January 1999.