A dynamic programming algorithm for the single-machine scheduling problem with release dates and deteriorating processing times (Q1014305)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 5547525
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | A dynamic programming algorithm for the single-machine scheduling problem with release dates and deteriorating processing times |
scientific article; zbMATH DE number 5547525 |
Statements
A dynamic programming algorithm for the single-machine scheduling problem with release dates and deteriorating processing times (English)
0 references
27 April 2009
0 references
The problem of minimizing the makespan on one machine is considered. Each job has a release date. The processing time of each job depends on the starting time linearly. For this strongly NP-hard problem an exact optimization algorithm with exponential worst-case complexity is presented. Polynomial solvable subproblems and upper and lower bounds to the makespan are described. Two different sets of experiments are performed. The first set of experiments is aimed at studying how the time consumption of the algorithm depends on the data. The second set of experiments compares different search policies.
0 references
combinatorial optimization
0 references
dynamic programming
0 references
scheduling
0 references
0 references
0.8577167987823486
0 references
0.8530215620994568
0 references
0.8512982130050659
0 references
0.8489741086959839
0 references
0.8455362319946289
0 references
