Back to Search
Start Over
Application of Submodular Optimization to Single Machine Scheduling with Controllable Processing Times Subject to Release Dates and Deadlines.
- Source :
-
INFORMS Journal on Computing . Winter2016, Vol. 28 Issue 1, p148-161. 14p. - Publication Year :
- 2016
-
Abstract
- In this paper, we study a scheduling problem on a single machine, provided that the jobs have individual release dates and deadlines, and the processing times are controllable. The objective is to find a feasible schedule that minimizes the total cost of reducing the processing times. We reformulate the problem in terms of maximizing a linear function over a submodular polyhedron intersected with a box. For the latter problem of submodular optimization, we develop a recursive decomposition algorithm and apply it to solving the single machine scheduling problem to achieve the best possible running time. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 10919856
- Volume :
- 28
- Issue :
- 1
- Database :
- Academic Search Index
- Journal :
- INFORMS Journal on Computing
- Publication Type :
- Academic Journal
- Accession number :
- 114699381
- Full Text :
- https://doi.org/10.1287/ijoc.2015.0660