Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
427324 | Information Processing Letters | 2014 | 4 Pages |
Abstract
•We study two serial batch scheduling problems on uniform machines.•The objectives are to minimize total completion time and total rejection penalty.•We provide two polynomial time algorithms.
We consider two scheduling problems on m uniform serial batch machines where m is fixed. In the first problem, all jobs have to be scheduled and the objective is to minimize total completion time. In the second problem, each job may be either rejected or accepted to be scheduled and the objective is to minimize the sum of total completion time and total rejection penalty. A polynomial time procedure is presented to solve both problems with the time complexity O(m2nm+2)O(m2nm+2) and O(m2nm+5)O(m2nm+5), respectively.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Song-Song Li, Yu-Zhong Zhang,