STRONGLY POLYNOMIAL ALGORITHMS FOR THE HIGH MULTIPLICITY SCHEDULING PROBLEM
成果类型：
Article
署名作者：
HOCHBAUM, DS; SHAMIR, R
署名单位：
Rutgers University System; Rutgers University New Brunswick
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.39.4.648
发表日期：
1991
页码：
648-653
关键词：
摘要：
A high multiplicity scheduling problem consists of many jobs which can be partitioned into relatively few groups, where all the jobs within each group are identical. Polynomial, and even strongly polynomial, algorithms for the standard scheduling problem, in which all jobs are assumed to be distinct, become exponential for the corresponding high multiplicity problem. In this paper, we study various high multiplicity problems of scheduling unit-time jobs on a single machine. We provide strongly polynomial algorithms for constructing optimal schedules with respect to several measures of efficiency (completion time, lateness, tardiness, the number of tardy jobs and their weighted counterparts). The algorithms require a number of operations that are polynomial in the number of groups rather than in the total number of jobs. As a by-product, we identify a new family of nxn transportation problems which are solvable in O(n log n) time by a simple greedy algorithm.