Scheduling linearly shortening jobs under precedence constraints
Journal
Applied Mathematical Modelling
Journal Volume
35
Journal Issue
4
Pages
2005-2015
Date Issued
2011
Author(s)
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(nlog. n) time, where n denotes the number of the jobs. © 2010 Elsevier Inc.
SDGs
Type
journal article