High Multiplicity in Earliness-Tardiness Scheduling

John J. Clifford () and Marc E. Posner ()
Additional contact information
John J. Clifford: Center for Naval Analyses, Alexandria, VA 22302
Marc E. Posner: The Ohio State University, Department of Industrial, Welding and Systems Engineering, 1971 Neil Avenue, Columbus, Ohio 43210-1271

Operations Research, 2000, vol. 48, issue 5, 788-800

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

Keywords: 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 (search for similar items in EconPapers)
Date: 2000
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.48.5.788.12405 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:48:y:2000:i:5:p:788-800

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().