Convex resource allocation for minimizing the makespan in a single machine with job release dates

Convex resource allocation for minimizing the makespan in a single machine with job release dates

0.00 Avg rating0 Votes
Article ID: iaor2005500
Country: United Kingdom
Volume: 31
Issue: 9
Start Page Number: 1481
End Page Number: 1489
Publication Date: Aug 2004
Journal: Computers and Operations Research
Authors: ,
Keywords: combinatorial analysis, optimization
Abstract:

We consider the problem of scheduling jobs on a single machine where job-processing times are controllable through the allocation of a common limited resource. The release dates are known and the job-processing time is described by a convex decreasing resource consumption function. Our objective is to simultaneously determine the optimal job permutation and the resource allocation, such that the maximal completion time is minimized. We provide an O(n) time optimization algorithm for the case of identical job release dates, and an O(n2) time optimization algorithm for the case of non-identical job release dates.

Reviews

Required fields are marked *. Your email address will not be published.