General multiprocessor task scheduling
研究了一类多机并行处理单任务的调度问题，为两机和三机问题设计了伪多项式算法，并推广到一般m机情形，对制造和资源规划有参考价值。
Most papers in the scheduling field assume that a job can be processed by only one machine at a time. Namely, they use a one-job-on-one-machine model. In many industry settings, this may not be an adequate model. Motivated by human resource planning, diagnosable microprocessor systems, berth allocation, and manufacturing systems that may require several resources simultaneously to process a job, we study the problem with a one-job-on-multiple-machine model. In our model, there are several alternatives that can be used to process a job. In each alternative, several machines need to process simultaneously the job assigned. Our purpose is to select an alternative for each job and then to schedule jobs to minimize the completion time of all jobs. In this paper, we provide a pseudopolynomial algorithm to solve optimally the two-machine problem, and a combination of a fully polynomial scheme and a heuristic to solve the three-machine problem. We then extend the results to a general m-machine problem. Our algorithms also provide an effective lower bounding scheme which lays the foundation for solving optimally the general m-machine problem. Furthermore, our algorithms can also be applied to solve a special case of the three-machine problem in pseudopolynomial time. Both pseudopolynomial algorithms (for two-machine and three-machine problems) are much more efficient than those in the literature. © 1999 John Wiley & Sons, Inc. Naval Research Logistics 46: 57–74, 1999