Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
1705232 | Applied Mathematical Modelling | 2015 | 11 Pages |
Abstract
We consider the problem of scheduling a set of dependent jobs on a single machine with the maximum completion time criterion. The processing time of each job is variable and decreases linearly with respect to the starting time of the job. Applying a uniform approach based on the calculation of ratios of expressions that describe total processing times of chains of jobs, we show basic properties of the problem. On the basis of these properties, we prove that if precedence constraints among jobs are in the form of a set of chains, a tree, a forest or a series–parallel digraph, the problem can be solved in O(n log n) time, where n denotes the number of the jobs.
Related Topics
Physical Sciences and Engineering
Engineering
Computational Mechanics
Authors
Stanisław Gawiejnowicz, Tsung-Chyan Lai, Ming-Huang Chiang,