High multiplicity in earliness-tardiness scheduling
成果类型：
Article
署名作者：
Clifford, JJ; Posner, ME
署名单位：
CNA (The Center for Naval Analyses); University System of Ohio; Ohio State University
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.48.5.788.12405
发表日期：
2000
页码：
788-800
关键词：
摘要：
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 identicaljobs. 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 identicaljobs 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.