Parallel machine scheduling with high multiplicity |
| |
Authors: | John J. Clifford Marc E. Posner |
| |
Affiliation: | (1) Center for Naval Analysis, 4825 Markcenter Drive, Alexandria, VA 22311-1850, USA, US;(2) The Ohio State University, Industrial Engineering, 1971 Neil Avenue, Columbus, Ohio 43210-1271, USA, US |
| |
Abstract: | In high-multiplicity scheduling problems, identical jobs are encoded in the efficient format of describing one of the jobs and the number of identical jobs. Similarly, identical machines are efficiently encoded in the same manner. We investigate parallel-machine, high-multiplicity problems, where there are three possible machine speed structures: identical, proportional, or unrelated. For the objectives of minimizing the sum of job completion times and minimizing the makespan, we consider both nonpreemptive and preemptive problems. For some problems, we develop polynomial time algorithms. For several problems, we demonstrate that the recognition versions can be solved in polynomial time, while the optimization versions require pseudo-polynomial time. We also show that changing from standard binary encoding to high-multiplicity encoding does not affect the complexity class of NP-complete problems. Received: April 1996 / Accepted: July 2000?Published online January 17, 2001 |
| |
Keywords: | : sequencing – deterministic – parallel machine – high multiplicity – computational complexity |
本文献已被 SpringerLink 等数据库收录! |
|