Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
1703319 | Applied Mathematical Modelling | 2015 | 9 Pages |
Abstract
The paper is devoted to some single-machine scheduling problems with variable job processing times. The objectives are to minimize the makespan (i.e., the maximum completion time of all jobs), and to minimize the total completion time. For some special cases, we show that these problems can be solved in polynomial time. For some another special cases of the makespan and the total completion time minimization problems, we prove that an optimal schedule has an V-shape property in terms of processing times. We also propose a heuristic algorithm by utilizing the V-shape property.
Related Topics
Physical Sciences and Engineering
Engineering
Computational Mechanics
Authors
Yuan-Yuan Lu, Jian-Jun Wang, Xue Huang,